Comments 29
> Не смотря на то, что распараллеливается он плохо
Отлично распараллеливается, причём на нескольких уровнях: как task-based нерегулярный параллелизм на уровне left/right/column подзадач, так и сам distance matrix multiplication.
Отлично распараллеливается, причём на нескольких уровнях: как task-based нерегулярный параллелизм на уровне left/right/column подзадач, так и сам distance matrix multiplication.
Да? Правда интересно, как его можно было распараллелить, чтобы достичь лучших рез-тов, чем от эвристик, которыми все в итоге пользовались? Потому как у нас локально он вроде проигрывал альтернативному (с эвристиками).
Плюс ко всему, забыла упомянуть, обнаружились огромные проблемы с памятью, которой катастрофически не хватало уже на средних матрицах (до больших не дошли).
Хотя может все эти вопросы и решались бы, будь у нас больше времени (поздно вспомнили про конкурс). (=
Плюс ко всему, забыла упомянуть, обнаружились огромные проблемы с памятью, которой катастрофически не хватало уже на средних матрицах (до больших не дошли).
Хотя может все эти вопросы и решались бы, будь у нас больше времени (поздно вспомнили про конкурс). (=
Тот факт, что на этих размерностях Кадан оказался быстрее, не говорит о том, что Такаока плохо распараллеливается.
Мы тоже писали Такаоку bitbucket.org/gribozavr/max_subarray_2d и у нас вот такие результаты на тестах с русскоязычного форума:
> 5000x5000 — 14.8 s на 40 ядрах, 517 s последовательно. маленький и средний — 27.8 s на 40 ядрах, 1092 s последовательно. Huge не пробовали.
Мы тоже писали Такаоку bitbucket.org/gribozavr/max_subarray_2d и у нас вот такие результаты на тестах с русскоязычного форума:
> 5000x5000 — 14.8 s на 40 ядрах, 517 s последовательно. маленький и средний — 27.8 s на 40 ядрах, 1092 s последовательно. Huge не пробовали.
>>Правда интересно, как его можно было распараллелить, чтобы достичь лучших рез-тов, чем от эвристик
Тут проблема была не столько в распараллеливании с целью снижения итоговой сложности в расчете на ядро, а хотя бы в чисто аппаратных вопросах доступа к памяти. Не все знали, а уж тем более учитывали NUMA организацию, «бегая» всеми 40 потоками по матрице. А ведь при «честном» способе и полном хранении матрицы, на нее могло приходиться полгора гигабайта. Кеши, false sharing, тайминги памяти… Не сравнить с решением, которому нужны всего несколько мегабайт (к примеру).
Тут проблема была не столько в распараллеливании с целью снижения итоговой сложности в расчете на ядро, а хотя бы в чисто аппаратных вопросах доступа к памяти. Не все знали, а уж тем более учитывали NUMA организацию, «бегая» всеми 40 потоками по матрице. А ведь при «честном» способе и полном хранении матрицы, на нее могло приходиться полгора гигабайта. Кеши, false sharing, тайминги памяти… Не сравнить с решением, которому нужны всего несколько мегабайт (к примеру).
«В целом алгоритм оказался очень сложным для понимания и реализации и не оправдал своих ожиданий на исключительную скорость(никаких дополнительных оптимизаций не осуществлялось).»
Ты писала какой-нибудь другой алгоритм или в сравнении с чем он «не оправдал ожиданий»? Если был реализован ещё другой алгоритм — было бы интересно посмотреть разницу в папугаях.
Ты писала какой-нибудь другой алгоритм или в сравнении с чем он «не оправдал ожиданий»? Если был реализован ещё другой алгоритм — было бы интересно посмотреть разницу в папугаях.
Был. (= Его писала не я, а мой сокомандник. И по сравнению с тем, который был гораздо проще, но использовал эвристики, связанные со спецификацией строения матриц, Такаока был не пригоден. Его не получилось как следует распараллелить и памяти он «жрал» очень много. )=
Я слышал, что там задача упрощалась по сложности за счёт специфики формирования матриц. Мне кажется, сравнение чистого алгоритма с задаче-специфичным несправедливо.
Не спорю, мне вообще жизнь казалась несправедливой, после потраченного времени (вместо учёбы) и осознания того, что едва ли мой алгоритм можно будет использовать в конкурсе. Но всё-равно разобраться с ним было забавно (=
Зато как удачно ложилась реализация с Каданэ! Сколько там можно было эвристик и оптимизаций воткнуть! (= Жаль только, что времени не хватило.
Зато как удачно ложилась реализация с Каданэ! Сколько там можно было эвристик и оптимизаций воткнуть! (= Жаль только, что времени не хватило.
Да, вместо алгоритма O(n*n*m) и подобных были решения вплоть до O(n*p), где p часто в пределах n*N, с малым натуральным N, а то и вообе меньшим чем m. Т.е. период не более нескольких строк :)
Видимо где-то в ваших словах закралась досадная ошибка, так как если p = n*N, при этом если рассматривать ситуацию обратную «а то и вообе меньшим чем m» (это слово «вообще»?), то получаем, что N может быть больше m. Тогда получаем p = n*(m+c) => O(n*n*(m+c)), что получается даже сложнее изначальной вашей оценки O(n*n*m).
p=m*N. Несколько строк, а не столбцов.
Да, «вообще». Извиняюсь за опечатку.
Да, «вообще». Извиняюсь за опечатку.
Если кому-то будет интересно, тут решения всех команд с их же описаниями решений.
Вообще по Такаока сложилось аналогичное мнение, что алгоритм для матриц «слегка» бОльших, нежели предлагались в конкурсе (максимум 20k на 20k).
Вообще по Такаока сложилось аналогичное мнение, что алгоритм для матриц «слегка» бОльших, нежели предлагались в конкурсе (максимум 20k на 20k).
К сожалению, не могу идентифицировать вас по нику на ISN и вспомнить название вашей команды… Рабочий комп не под рукой, да и прайваси…
Но я верю, что жизнь — справедлива! Мне победитель конкурса говорил, что они потратили с сокомандником на полировку решения 3 (три!) недели в выделенном режиме.
Мы ведь не пытаемся конкурировать с олимпиадным программированием, стараемся поставить во главу угла тонкую оптимизацию решения под конкретные платформы. Таким образом, хорошая стратегия для конкурсантов выглядит примерно так: 1) оценить быстродействие последовательного алгоритма 2) оценить возможности его распараллеливания 3) чем больше времени останется нв профилирование и низкоуровневую оптимизацию — тем лучше!
Теперь посмотрим сюда: только 12 из 66 команд смогли корректно решить все матрицы, без учета скорости. Больше половины не уложились в лимит времени в одном или нескольких тестах. А ведь большинство использовало хорошо известный алгоритм.
В отличие от большинства вы попробовали что-то новенькое, да и «разобраться с ним было забавно» :)
А насчет победы — не переживайте, будут еще конкурсы… С наступившим старым новым годом, кстати.
Но я верю, что жизнь — справедлива! Мне победитель конкурса говорил, что они потратили с сокомандником на полировку решения 3 (три!) недели в выделенном режиме.
Мы ведь не пытаемся конкурировать с олимпиадным программированием, стараемся поставить во главу угла тонкую оптимизацию решения под конкретные платформы. Таким образом, хорошая стратегия для конкурсантов выглядит примерно так: 1) оценить быстродействие последовательного алгоритма 2) оценить возможности его распараллеливания 3) чем больше времени останется нв профилирование и низкоуровневую оптимизацию — тем лучше!
Теперь посмотрим сюда: только 12 из 66 команд смогли корректно решить все матрицы, без учета скорости. Больше половины не уложились в лимит времени в одном или нескольких тестах. А ведь большинство использовало хорошо известный алгоритм.
В отличие от большинства вы попробовали что-то новенькое, да и «разобраться с ним было забавно» :)
А насчет победы — не переживайте, будут еще конкурсы… С наступившим старым новым годом, кстати.
>>Теперь посмотрим сюда: только 12 из 66 команд смогли корректно решить все матрицы, без учета скорости.
Вот лимит по времени работы там все-равно был :) Не успел — не правильно. По сути это и был учет скорости в неявном виде.
Вот лимит по времени работы там все-равно был :) Не успел — не правильно. По сути это и был учет скорости в неявном виде.
Мы в рейтинге заняли кругленькое 10е место.
Трёх недель выделить не получилось, поэтому и не сорвали джекпот ;)
А вообще мне действительно было гораздо интереснее разобраться с этим «неподходящим» алгоритмом, чем с каданэ (который придумали за 10 минут) и всякими изощрёнными оптимизациями — не моё это. Поэтому я позорно дезертировала ковыряться с Такаокой, оставив сокомандника одного париться с эвристиками (=
Главное не победа, а участие (=
Спасибо, вас так же с наступившим (=
Трёх недель выделить не получилось, поэтому и не сорвали джекпот ;)
А вообще мне действительно было гораздо интереснее разобраться с этим «неподходящим» алгоритмом, чем с каданэ (который придумали за 10 минут) и всякими изощрёнными оптимизациями — не моё это. Поэтому я позорно дезертировала ковыряться с Такаокой, оставив сокомандника одного париться с эвристиками (=
Главное не победа, а участие (=
Спасибо, вас так же с наступившим (=
Кто-нибудь может мне объяснить, почему этот алгоритм напомнил мне расстояние Левенштейна?
Правильно ли я понял, что данный алгоритм предназначен для поиска максимальной подматрицы в рядом стоящих столбцах/строках?
Видели ли Вы где-то упоминание о его применении к задаче, когда допускается перестановка строк/столбцов?
Видели ли Вы где-то упоминание о его применении к задаче, когда допускается перестановка строк/столбцов?
Да, вы правильно поняли задачу.
Встречный вопрос: что имеется в виду под вашим «допускается перестановка строк/столбцов»? Если это абсолютно любые перестановки в неограниченном количестве — то так можно переместить любой элемент матрицы на любую позицию, следовательно максимальная подматрица состоит из всех положительных элементов, собранных в прямоугольник. Или я что-то не так поняла?
Встречный вопрос: что имеется в виду под вашим «допускается перестановка строк/столбцов»? Если это абсолютно любые перестановки в неограниченном количестве — то так можно переместить любой элемент матрицы на любую позицию, следовательно максимальная подматрица состоит из всех положительных элементов, собранных в прямоугольник. Или я что-то не так поняла?
По-моему, не всегда это возможно.
Рассмотрим матрицу вида:
|1|1|0|
|1|0|1|
|0|1|1|
Посчитайте ее детерминант, он отличен от нуля. Если бы можно было переставить, получив блок из единиц размером 2x3, то детерминант был бы равен нулю (ибо ранг матрицы был бы 2).
Под перестановкой я имел в виду следующее. Нам дают матрицу. Мы можем сгенерировать любую перестановку(подстановку, permutation) для строк и столбцов, после чего задача в общем-то сводится к подряд стоящим столбцам/строкам. Вот только надо выбрать именно такую перестановку, чтобы последующее решение задачи было максимальным.
Рассмотрим матрицу вида:
|1|1|0|
|1|0|1|
|0|1|1|
Посчитайте ее детерминант, он отличен от нуля. Если бы можно было переставить, получив блок из единиц размером 2x3, то детерминант был бы равен нулю (ибо ранг матрицы был бы 2).
Под перестановкой я имел в виду следующее. Нам дают матрицу. Мы можем сгенерировать любую перестановку(подстановку, permutation) для строк и столбцов, после чего задача в общем-то сводится к подряд стоящим столбцам/строкам. Вот только надо выбрать именно такую перестановку, чтобы последующее решение задачи было максимальным.
Извиняюсь, не нашел в правилах конкурса. Есть ли ограничения на размер используемой памяти?
Sign up to leave a comment.
Алгоритм Тадао Такаока для нахождения максимальной подматрицы или Maximum Subarray Problem