Цитата: evatutin от 29.04.2022, 00:20

Надеюсь внезапно возникшие проблемы с добавлением Wu'шек будут оперативно решены, пока сделаю анонс того, что планируется сделать в самое ближайшее время...

Итак, к концу подходят два эксперимента, связанные с построением спектров числа диагональных трансверсалей в ДЛК порядков N=12 и N=15. Вроде бы одно и то же, только размерность задачи разная, на самом деле — нет. Проблема здесь в том, что с ростом размерности N алгоритмы, которые более менее нормально работали ранее, начинают работать неприемлимо долго и приходится думать над тем, как их менять на менее вычислительно сложные или распараллеливать. В данном случае для размерности N=12 применялись алгоритмы поквадратного построения спектра (фактически отталкиваясь от каждого квадрата в исходном спектре происходит построение нового спектра, при постобработке данные новые спектры объединяются) и поквадратная диагонализация (те самые WU'шки, которые считаются по нескольку суток для тяжелых квадратов). Для размерности N=15 поквадратное построение спектра потребует нескольких сотен лет расчетов в проекте при текущей реальной производительности, диагонализация потребует еще раз в 100 больше времени, поэтому был применен другой алгоритм, основанный на частичной диагонализации и обработке 1-окрестностей для заданных квадратов. В результате для N=15 на данный момент получен довольно большой спектр, который в ходе постобработки был разбит на 5 частей по миллиону значений в каждой:

1-я часть — {15510, 15669, 16210, 16296, 16403, ..., 999996, 999997, 999998, 999999, 1000000}, 933061 элемент;
2-я часть — {1000001, 1000002, 1000003, 1000004, 1000005, ..., 1999972, 1999974, 1999990, 1999995, 1999996}, 915174 элемента;
3-я часть — {2000032, 2000050, 2000057, 2000058, 2000061, ..., 2916155, 2916625, 2917501, 2918550, 2954593}, 104096 элементов;
4-я часть — {}, 0 элементов;
5-я часть — {4588133, 4588962, 4589048, 4589133, 4589188, ..., 4608497, 4613052, 4616090, 4617772, 4620434}, 6587 элементов,

итого 933061 + 915174 + 104096 + 0 + 6587 = 1958918 элементов, что позволяет наложить новое нижнее ограничение на мощность соответствующего спектра, но... В полученных результатах я уверен не до конца, т.к. попадались сбойные результаты, в одном случае даже пришлось блокировать пользователя с потоком глючных результатов, поэтому подготовлено примерно 10 тыс. WU'шек эксперимента exp1063 для их проверки. WU'шки короткие, примерно по 10 минут счета, считать их планируется с кворумом 2 (спектр долго строить, но быстро проверить его корректность, ранее это удавалось сделать на моей машине, теперь спектр большой и требуется помощь проекта, на моей машине данная проверка будет идти несколько месяцев). Подобная схема (долгий расчет с кворумом 1, быстрая проверка с кворумом 2) требует от меня ряда дополнительных действий, однако работает быстрее, чем организация исходного расчета с кворумом 2. После завершения проверки я выложу точное нижнее ограничение на мощность спектра (значение 1958918 пока будем считать предварительным) и сами спектры (значения с подтверждающими квадратами), которые на данный момент весят 438 МБ. По моим ощущениям данный спектр еще можно расширить процентов на 10-20, но для этого будут нужны другие алгоритмы, чем мы займемся чуть позже... Для порядков N=16 и выше построение полных спектров будет еще более тяжелой задачей: спектры будут включать в своем составе несколько миллионов элементов, подтверждающие файлы будут весить по нескольку ГБ, пока решение данной задачи "в лоб" мне представляется нецелесообразным, поэтому скорее всего в перспективе в данном вопросе придется немного схитрить и задача будет декомпозирована...

PS. Анонс результатов по спектру для N=12 выложу отдельно после завершения счета хвостов из 9 долгих WU'шек.

PPS. Ну и немного технических деталей, если это интересно кому-то кроме меня...

1. Без разбиения на части построение спектра (постобработка) выполнялось очень долго, десятки часов, пришлось переписывать код...
2. В ходе переписывания выяснилось, что при построении спектра заранее неизвестного и довольно большого размера (несколько сотен тысяч элементов) из-за серии realloc'ов возникает неприятная ситуация, скорее всего связанная с фрагментацией кучи, когда при выделении примерно 300 МБ динамической памяти все либо начинает страшно тормозить, либо вообще выдается сообщение о нехватке динамической памяти, хотя это даже близко не так. Постобработку пришлось делать по сути в 3 этапа: объединение результатов из проекта (мелкие файлы спектров) в крупные файлы по 300 тыс. значений, затем объединение крупных файлов в один большой файл спектра, а уже затем его раскладка по частям с непосредственно постобработкой (сортировка, поиск новых элементов, добавление новых в существующий спектр, формирование на их основе новых WU'шек, добавление в проект).
3. Работа со спектрами неотсортированных значений для данной размерности выполняется неприемлимо долго. Сортировка и последующий бинарный поиск ситуацию выправляют, но не сильно. Пришлось вспомнить о том, что есть алгоритмы сортировки за время быстрее O(N * log(N)), что вроде бы запрещено теорией, но они есть... Кто в этом сомневается, либо ко мне в презентацию http://evatutin.narod.ru/evatutin_edu_01_sorting.pdf, либо на предстоящую лекцию по программированию в следующий четверг, тематика как раз совпадает по странному стечению обстоятельств :). В данном вопросе есть тонкость, объясняющая, все-таки можно или нельзя быстрее N * log(N) ... Так вот, на базе алгоритма сортировки распределением удалось сделать программную реализацию объединения спектров и поиска новых элементов, которая работает почти мгновенно для спектров мощностью по миллиону элементов (до оптимизации на это требовалось более часа времени на каждую часть спектра). При этом правда требуется много памяти, но ее в данном случае ее хватает.

Незаметная фоновая работа, отнимающая крохи доступного времени, но ведущая к получению новых результатов, что не может не радовать :). На какой-либо из предстоящих конференций будет о чем рассказать...