2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу Пред.  1 ... 3, 4, 5, 6, 7
 
 Re: Al Zimmermann's: Statue of Liberty
Сообщение23.05.2020, 11:38 
Аватара пользователя


01/06/12
1011
Adelaide, Australia
Jarek is back on top - what a true champion!

 Профиль  
                  
 
 Re: Al Zimmermann's: Statue of Liberty
Сообщение24.05.2020, 08:03 


18/11/10
75
:D :D :D
Frankly, I do not expect to win this one. My guess is that I will finish third with the score of 23.02+.

 Профиль  
                  
 
 Re: Al Zimmermann's: Statue of Liberty
Сообщение21.06.2020, 13:06 


06/04/20
4
Seems like most people are stuck now, not much new is happening :-(

Any fresh ideas here to test? Or hints/tips? Haha.

 Профиль  
                  
 
 Re: Al Zimmermann's: Statue of Liberty
Сообщение23.06.2020, 10:25 


20/01/13
62
"High-density subset sum problem" and "0-1 knapsack problem" didn't lead to anything useful :-(

royvanrijn в сообщении #1469969 писал(а):
Seems like most people are stuck now, not much new is happening :-(

Any fresh ideas here to test? Or hints/tips? Haha.

 Профиль  
                  
 
 Re: Al Zimmermann's: Statue of Liberty
Сообщение28.07.2020, 13:47 


07/06/16
39
Омск
Почему-то никто опять не пишет отчётов, а ведь это тоже интересно. В таких случаях принято начинать с себя, поэтому начну.
Собственно, задача решалась мной самым тупым образом - перебором, а оптимизации делались только для того, чтобы поднять скорость перебора. Ни одной умной идеи не удалось довести до ума, поэтому можно считать мой результат - верхом того, чего можно было достичь тупым ремесленным подходом.
А достичь удалось 15-го места, и первого из тех, у кого в графе страна стояло "Россия". Это самое высокое место, которое мне удавалось взять в конкурсах Al Zimmerman's. Поэтому, с одной стороны я рад, с другой - огорчён отсутствием плодотворных идей в моей голове. Хотя Herbert в июне уже разжевал для таких как я интересные подходы, я их не стал использовать, отчасти из-за нехватки времени, отчасти из-за того что не увидел насколько это сузит перебор.
До начала конкурса я немного подготовился.
Во-первых, попытался написать среду для запуска потоков с расчётной задачей. Но потом понял что это неправильный подход. Нужна простая база данных с заданиями, пусть даже в виде текстового файла, и независимые программные модули, которые не завершают работу сами, а берут и берут задания из базы. Нет заданий - выбирают его случайно. Таким способом можно избежать длительного простоя, который может составлять до 30% времени.
Во-вторых, я купил процессор Ryzen 5 2600, который при цене в 6300 руб. на момент покупки, прекрасно держит многопоточную нагрузку в 12 потоков.
Начало конкурса удачно выпало на время, когда у меня было по 4-5 часов, которые я мог посвящать задаче.
Первая моя версия программы на Java с использованием библиотеки java.math.BigInteger для работы с большими числами. Как выяснилось, она потребляла массу памяти и работала крайне медленно. Стало понятно что проблем две: 1 - при работе с BigInteger Java постоянно создаёт новые объекты, а неиспользуемые копятся в памяти; 2 - неоптимальные функции работы с большими числами очень тормозят программу.
Ассемблерный код основных функций я написал за минут 20, но последующие 2 дня попыток вставить ассемблерный блок в современные студии для программ на C/C++ не увенчались успехом.
Пришлось согласиться на компромиссный вариант, программу на C#, в которой числа хранились в двух 64-разрядных полях, а вычисления делались с помощью 64-разрядной арифметики C#.
Это сразу решило проблему memory leak и подняло быстродействие примерно до 50% от оптимизированного по скорости ASM/C++ аналога.
Сам алгоритм перебора был довольно простым, я бы сказал интуитивным. Вычислялось N^K, а затем, начиная с N-1 проверялось, если остаток больше I^K, то отнимаем от остатка I^K. Затем идём обратно и, если элемент J при исключении из решения оставляет остаток меньше чем сумма всех чисел от 1 до J-1 в степени K, то считаем это новым базовым решением, и запускаем алгоритм снова "вниз". И так пока не дойдём до N.
Естественно, сразу использовались оптимизации в виде массивов частичных сумм.
Большие степени я не просчитывал, так как это было практически бессмысленно, а вот со степенями 16..21 я поработал.
Через некоторое время стало понятно что если все суммы записать в память в отсортированном виде, то решение можно найти за очень маленькое время. Проблема была только в том, что столько памяти нет ни у одного суперкомпьютера. Тогда решено было использовать разбиение на блоки по 22..25 числа, чьи суммы в порядке возрастания вполне умещались в ОЗУ. Поиск по такому упорядоченному массиву занимал на первое число чуть больше времени чем просто перебор, но поиск последующих чисел становился не нужным - достаточно было брать числа из блока по возрастанию индекса. Таким способом быстродействие удалось поднять ещё в несколько раз.
Легко заметить, что самые маленькие числа в степени K возрастают быстрее чем сумма степеней K чисел 1..(K-1). Это означало что нижние K чисел не нужно было брать в блок, так как это только уменьшало скорость перебора. Но алгоритм был уже написан, и я не стал его переписывать ещё раз. Теоретически такая оптимизация могла дать выигрыш в скорости ещё до 1.5 раз.
Были попытки поиграться с разложением степеней вида $(N+1)^K-N^K-(N-1)^K+(N-2)^K,$ но стало понятно что для понижении степени на 2 нужно добавлять минимум по 4 числа. Теоретически это могло привести к некоторым оптимизациям или даже решениям, но не привело. :)
Также я тщательно анализировал каждое найденное приближённое решение, стараясь уловить в них закономерности. Выяснилось что некоторые числа присутствуют в решениях с большой вероятностью, а некоторые с очень маленькой. Также видно как у двух приближённых решений для одного N и одинакового максимального члена (N-M) остальные слагаемые устраивают массовые перестановки, которые кажутся не совсем хаотическими, но меняется почти каждое число.
Достаточно многое дал анализ решений для низших степеней (4..15). Стало понятно что с увеличением степени для одинакового N число вариантов перебора меньше, причём в разы.
Также сформулровалась гипотеза что у первого найденного точного решения N взаимнопросто с (K+1), которую, к сожалению, не удалось проверить. Но и приближённых решений у таких N также субъективно больше.
Если рассматривать процесс поиска с точки зрения теории вероятностей, то ситуация такая. Увеличение N на 1 даёт число вариантов для перебора в SQRT(2) раз больше. Что, в свою очередь, даёт более близкое решение на в среднем LN(SQR(2)).
Маленькие N обсчитывались очень быстро. Например, для степени 16 первые 80 чисел обсчитываются за несколько минут. А если взять слишком большое N, например 150, то прямой алгоритм перебора может не закончиться за время вашей жизни.
В любом случае, я получил свою порцию эмоций от этой задачи, и преклоняюсь перед интеллектом тех, кто смог найти хотя бы одно точное решение, чего мне, к сожалению, не удалось.

 Профиль  
                  
 
 Re: Al Zimmermann's: Statue of Liberty
Сообщение05.11.2020, 06:43 


07/06/16
39
Омск
Знаете, оказалось что мой способ решения не самый тупой. :)
Я тут попробовал перебор по-другому. Например, записываем в очередь число N^K. Затем, для степени K-1, читаем очередь в 2 потока и выбираем большее из прочитанного из очереди A1 и A2-N^(K-1). Естественно, отбрасываем то, что больше частичных сумм всех степеней меньше K-1 и что меньше нуля. И так до нулевой степени.
Оказывается этот способ медленнее, причём порядка на 2-3.

-- 05.11.2020, 09:55 --

И ещё один момент.
В письме от 28.07 я описывал свой алгоритм перебора и писал про компоновку частичных сумм в блоки, из которых бинарным поиском я находил подходящие.
Оказалось что скорость работы программы имеет минимум при размере блока от 2^13 до 2^17 на тех N и K, которые я проверял. Это очень странный эффект, который был неочевиден для меня. Мне казалось что скорость должна увеличиваться с увеличением размера блока. Но, судя по низкой скорости перебора по полному буферу, о котором я написал в предыдущем письме, всё подтверждается. И у меня пока нет объяснения этим фактам.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 96 ]  На страницу Пред.  1 ... 3, 4, 5, 6, 7

Модераторы: maxal, Toucan, PAV, Karan, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group