Я запускал 20000 в 6 потоков на 4-ядерном i7-3770 3.4GHz (каждый поток замедляется из-за гипертрединга, но общее время улучшается). 50000 и 100000 я запускал так: 6 потоков на 4-ядерном i7-3770 3.4GHz, 10 потоков на 6-ядерном i7-5820K 3.3GHz.
Ну, сейчас, вызовов этого gcd — O(n) с малой константой (около 1/144). Но доказать, что эта оценка справедлива при любом n, наверно, не проще, чем найти третье решение уравнения.
Тут явно или что-то меряется, что-то сортится, или что-то выводится не так.
В разрыв по времени в 10 раз я может и поверю, но не в 10000 раз.
Ибо в каждом куске кода мы всегда как минимум создаем вектор за линейное время.
Число простых с ростом n растет как n / ln n, т.е. для n=1000000 их уже всего всего 7%… Но если это утверждение хотя бы доказать — то тогда вполне можно добавить.
Это все действительно интересно и я, на самом деле, немного думал об ускорении сортировки в этом направлении. Если n достаточно мало, то массив действительно получается почти отсортированным и я пробовал его сортировать его вставками. К сожалению, с ростом n эта частичная отсортированность пропадает. Попробуйте померить вашим кодом случай, когда n порядка 10000.
Ну тогда я буду ускорять потихоньку. Сейчас вот экспериментировал в заменой сортировки с указателями на хэш-таблицу, и… получил двукратное ускорение и решение за O(N^3). Т.е. почти полностью вырезал все то время, который жрал лишний логарифм.
Ну так я свое #5 даже и не пытался ускорять дальше из-за того, что оно квадрат памяти требует. То есть насчет него — я согласен, что может и больше, чем в 10 раз ускорится. Ну а толку от него, если оно в память не лезет?
Если я верно понял, но у Вас для n=20 в случае без сортировки после (a=19 b=18) будет идти (a=20 b=1). Но ведь 19^5+18^5 = 4365667 > 3200001 = 20^5+1^5. То есть, если для n=10 оно вроде работает, то потом, с ростом n, при переходе от (a (a-1)) к ((a+1) 1) получаем, что первое число будет где-то в 2 раза больше второго.
С другой стороны — если не будет дополнительных ресурсов — то и оптимизировать особо смысла нет. Не думаю, что там можно более чем в 10 раз ускорить.
А так да, конечно, при возможной ресурсной поддержке — засяду оптимизировать насколько это возможно, опыт подобных расчетов есть (правда, «всего» на 55000 ядрочасов). Ну и не сразу миллион, а шажками: сначала 200000, потом 500000, а потом можно и за 1000000 взяться.
gcd там нужен чисто для отбраковки решений, в которых параметры имеют общий делитель. Поскольку решений, для которых нам нужно сделать такую проверку, очень мало, то сложность gcd можно не учитывать. Но если смотреть с формальной точки зрения — то да, надо везде домножить на логарифм. И решение #10 тогда получается со сложностью O(n5log n) (ouch!).
Конкретно тут вроде неважно в каком порядке идут сравнения, но, скажем, в аналогичных циклах позже нужно будет сначала проверить, что j>=0, а только потом посмотреть что лежит в массиве по индексу j.
&& — это И для типа bool, & — логическое И для целочисленной маски.
Там же происходит j--, поэтому в процессе выполнения цикла условие i < j может нарушиться.
По хорошему, i < j надо вставить еще в следующий if, но когда это не выполняется, будет i=j и, в принципе, индекс массива j остается валидный.
сорян, я немного вклинюсь в ваш диалог
> вектора из модели word2vec — 300 действительных чисел
но ведь слов любого языка всего порядка 50000 и их можно закодировать 16 битами
Интересно. К сожалению, больше информации по этому проекту нагуглить не могу.
Зато я нагуглил информацию по другому проекту. Они другим алгоритмом через BOINC подтвердили результаты, которые я привел в тексте перевода. Вот ссылки: раздва.
Впрочем, я припоминаю подобную историю с проверкой нулей зета-функции Римана. Вроде из-за этого закрыли проект ZetaGrid, поскольку они там всей толпой распределенными вычислениями проверили меньше нулей, чем один математик на своем десктопе…
ЭТО создает линейное число элементов вместо квадрата
В разрыв по времени в 10 раз я может и поверю, но не в 10000 раз.
Ибо в каждом куске кода мы всегда как минимум создаем вектор за линейное время.
А так да, конечно, при возможной ресурсной поддержке — засяду оптимизировать насколько это возможно, опыт подобных расчетов есть (правда, «всего» на 55000 ядрочасов). Ну и не сразу миллион, а шажками: сначала 200000, потом 500000, а потом можно и за 1000000 взяться.
&& — это И для типа bool, & — логическое И для целочисленной маски.
По хорошему, i < j надо вставить еще в следующий if, но когда это не выполняется, будет i=j и, в принципе, индекс массива j остается валидный.
> вектора из модели word2vec — 300 действительных чисел
но ведь слов любого языка всего порядка 50000 и их можно закодировать 16 битами
Зато я нагуглил информацию по другому проекту. Они другим алгоритмом через BOINC подтвердили результаты, которые я привел в тексте перевода. Вот ссылки: раз два.