Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 48
Найдите логическую ошибку в коде выше.
while( i < j )
{
while ( i < j && vec[i].first + vec[j].first > e5 ) j--;
if ( vec[i].first + vec[j].first == e5 )
{
bla bla = bla;
}
i++;
}
Я правильно понимаю, что во втором случае условие выглядит так:
while ( 1 && vec[i].first + vec[j].first > e5 ) j--;
А ещё, не замедляет ли решение printf, как было в одной из предыдущих статей на эту тему?
Там же происходит j--, поэтому в процессе выполнения цикла условие i < j может нарушиться.
По хорошему, i < j надо вставить еще в следующий if, но когда это не выполняется, будет i=j и, в принципе, индекс массива j остается валидный.
По хорошему, i < j надо вставить еще в следующий if, но когда это не выполняется, будет i=j и, в принципе, индекс массива j остается валидный.
Да, точно. Не увидел сразу, что весь цикл одной строчкой.
Ещё я не силён в порядке операций — сравнение на > e5 будет самым последним?
Почему используется &&, а не &?
Ещё я не силён в порядке операций — сравнение на > e5 будет самым последним?
Почему используется &&, а не &?
Скажите, а есть примеры практического применения данного уравнения?
У вас во вложенных циклах считаются gcd. Разве этот вспомогательный алгоритм не увеличивает сложность вычисления?
gcd там нужен чисто для отбраковки решений, в которых параметры имеют общий делитель. Поскольку решений, для которых нам нужно сделать такую проверку, очень мало, то сложность gcd можно не учитывать. Но если смотреть с формальной точки зрения — то да, надо везде домножить на логарифм. И решение #10 тогда получается со сложностью O(n5log n) (ouch!).
Неплохая работа, идея с дискретным корнем весьма интересна.
В частности, рекомендую пользоваться gcc или clang — там есть встроенная поддержка __uint128_t.
Еще у меня есть дикая идея проверить все n вплоть до миллиона. Ожидаемое время проверки, в принципе, реальное — около миллиона ядрочасовИмхо, рано ещё, лучше потратить несколько часов (или десятков) на улучшение алгоритма и оптимизацию кода и сэкономить сотни тысяч часов обогрева комнаты на cpu (или gpu) ;)
В частности, рекомендую пользоваться gcc или clang — там есть встроенная поддержка __uint128_t.
С другой стороны — если не будет дополнительных ресурсов — то и оптимизировать особо смысла нет. Не думаю, что там можно более чем в 10 раз ускорить.
А так да, конечно, при возможной ресурсной поддержке — засяду оптимизировать насколько это возможно, опыт подобных расчетов есть (правда, «всего» на 55000 ядрочасов). Ну и не сразу миллион, а шажками: сначала 200000, потом 500000, а потом можно и за 1000000 взяться.
А так да, конечно, при возможной ресурсной поддержке — засяду оптимизировать насколько это возможно, опыт подобных расчетов есть (правда, «всего» на 55000 ядрочасов). Ну и не сразу миллион, а шажками: сначала 200000, потом 500000, а потом можно и за 1000000 взяться.
Не думаю, что там можно более чем в 10 раз ускорить.Для 10000:
real 4m35.773s
user 4m33.321s
sys 0m2.459s
Думаю, у меня получится ещё разогнать.
1 ядро, 8ГБ памяти, алго O(N^3) по cpu и O(N^2) по памяти, по сути, аналог Вашего №5. Память — проблемное место, когда она заканчивается, то асимптотика по cpu выходит на O(N^4).
Ну так я свое #5 даже и не пытался ускорять дальше из-за того, что оно квадрат памяти требует. То есть насчет него — я согласен, что может и больше, чем в 10 раз ускорится. Ну а толку от него, если оно в память не лезет?
Эту версию ускорять уже смысла нет, согласен.
Надо работать над последней версией. Вполне может быть, что из-за маленького использования памяти она хорошо ляжет на GPU — ускорение будет в сотни раз.
Из дополнительных возможностей для оптимизации — сейчас множество вычислений повторяются многократно, их кешировать, хотя бы частично. Например, сохранить отсортированный список для каждого остатка, можно даже в файл.
Надо работать над последней версией. Вполне может быть, что из-за маленького использования памяти она хорошо ляжет на GPU — ускорение будет в сотни раз.
Из дополнительных возможностей для оптимизации — сейчас множество вычислений повторяются многократно, их кешировать, хотя бы частично. Например, сохранить отсортированный список для каждого остатка, можно даже в файл.
Пишут, что известны три решения:
Euler's conjecture was disproven by L. J. Lander and T. R. Parkin in 1966 when, through a direct computer search on a CDC 6600, they found a counterexample for k = 5. A total of three primitive (that is, in which the summands do not all have a common factor) counterexamples are known:
27^5 + 84^5 + 110^5 + 133^5 = 144^5 (Lander & Parkin, 1966),
(−220)^5 + 5027^5 + 6237^5 + 14068^5 = 14132^5 (Scher & Seidl, 1996), and
55^5 + 3183^5 + 28969^5 + 85282^5 = 85359^5 (Frye, 2004).
Если «вывернуть на изнанку» циклы, можно получить сортированный вектор сразу на этапе инициализации.
В этом можно убедиться на примере однострочника на баше:
Я полагаю это может убавить заметное время выполнения.
В этом можно убедиться на примере однострочника на баше:
# с использованием сортировки
for a in $(seq 1 9); do for b in $(seq $(($a+1)) 10); do echo -n "$a^5+$b^5 = "; echo "$a^5+$b^5" | bc; done; done | sort -n -k3
# без использования сортировки
for a in $(seq 2 10); do for b in $(seq 1 $((a-1))); do echo -n "$a^5+$b^5 = "; echo "$a^5+$b^5" | bc; done; done
Я полагаю это может убавить заметное время выполнения.
Если я верно понял, но у Вас для 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 раза больше второго.
Да, я это обнаружил сразу после отправки комментария (об этом я отписался в личку, поскольку нет прав на редактирование).
Все же я провел некоторые тесты. В случае с «вывернутым» заполнением время сортировки уменьшается в разы, поскольку происходит меньше перестановок во время сортировки. Плюс немного уменьшил некоторое количество вычислений. С тестом можно ознакомиться по ссылке и рядом лежит файлик с результатами прогона:
https://github.com/theg4sh/experiments/blob/master/filling_loop_sortless.cpp
Все же я провел некоторые тесты. В случае с «вывернутым» заполнением время сортировки уменьшается в разы, поскольку происходит меньше перестановок во время сортировки. Плюс немного уменьшил некоторое количество вычислений. С тестом можно ознакомиться по ссылке и рядом лежит файлик с результатами прогона:
https://github.com/theg4sh/experiments/blob/master/filling_loop_sortless.cpp
Это все действительно интересно и я, на самом деле, немного думал об ускорении сортировки в этом направлении. Если n достаточно мало, то массив действительно получается почти отсортированным и я пробовал его сортировать его вставками. К сожалению, с ростом n эта частичная отсортированность пропадает. Попробуйте померить вашим кодом случай, когда n порядка 10000.
Я провел тест и честно говоря ожидал увидеть цифры порядка нескольких минут. Сказать, что я был приятно удивлен — ничего не сказать. Смотрите сами:
Я уменьшил количество прогонов для n=10000, но все же это какое-то… «безумие» :)
Насколько я понял, получается, что время заполнения вектора можно не учитывать при больших значениях n и это при одном потоке.
P/S Для сравнения, добавил результаты прогона для n=500 при 100 повторений в список. Так же поправил старые результаты из-за некорректного формата вывода времени.
repeats: 100
count: 10000
filling_origin x 100: 586.399347237
filling_minopt x 100: 585.032718914
filling_alloc x 100: 533.968311924
filling_lesssort x 100: 0.045311705
filling_lesssort_precalc x 100: 0.054538855
filling_lesssort_alloc x 100: 0.045214453
Я уменьшил количество прогонов для n=10000, но все же это какое-то… «безумие» :)
Насколько я понял, получается, что время заполнения вектора можно не учитывать при больших значениях n и это при одном потоке.
P/S Для сравнения, добавил результаты прогона для n=500 при 100 повторений в список. Так же поправил старые результаты из-за некорректного формата вывода времени.
Тут явно или что-то меряется, что-то сортится, или что-то выводится не так.
В разрыв по времени в 10 раз я может и поверю, но не в 10000 раз.
Ибо в каждом куске кода мы всегда как минимум создаем вектор за линейное время.
В разрыв по времени в 10 раз я может и поверю, но не в 10000 раз.
Ибо в каждом куске кода мы всегда как минимум создаем вектор за линейное время.
У вас в коде
ЭТО создает линейное число элементов вместо квадрата
for (int a=2; a<=n; a++) {
for (int b=a-1; b<a; b++) {
ЭТО создает линейное число элементов вместо квадрата
Верно. Прошу прощения за невнимательность и спасибо, что нашли ошибку. Человеческий фактор, чтоб его.
Действительно, прирост в производительности небольшой:
Я сделал некоторые оптимизации, связанные с пропущенным оператором break для условия (a5+b5<n5), логично предположить, что последующие итерации с увеличением b приведут к аналогичному результату.
Это дало ощутимый прирост:
Код лежит там же на github`е
Действительно, прирост в производительности небольшой:
filling_lesssort x 100: 552.314313408 1 iter avg 5.523143134
filling_lesssort_precalc x 100: 540.896136543 1 iter avg 5.408961365
filling_lesssort_alloc x 100: 497.780295379 1 iter avg 4.977802953
Я сделал некоторые оптимизации, связанные с пропущенным оператором break для условия (a5+b5<n5), логично предположить, что последующие итерации с увеличением b приведут к аналогичному результату.
Это дало ощутимый прирост:
filling_lesssort_alloc_break x 100: 159.098596131 1 iter avg 1.590985961
Код лежит там же на github`е
У вас filling_lesssort_alloc_break криво сумму считает:
sa5b5 будет равно a5 + 0 + 1 + 2^5 + 3^5 +… + b5
sa5b5 будет равно a5 + 0 + 1 + 2^5 + 3^5 +… + b5
Точно! Спасибо Deosis, поправил.
А нельзя было попытаться хардкорно оптимизировать №8?
Может я глупость скажу но нет ли смысла попробовать погонять алгоритм для чисел отличных от простых? Я просто на бумажке накидал: 27^5+84^5+110^5+133^5=144^5 если разложить числа на простые множители то получим:
27 = 3^3
84 = 2^2 * 3 * 7
110 = 2 * 5 * 7
133 = 7 * 19
144 = 2^4 * 3^2
т.е. все числа не простые. Аналогично я проверил для решения 55^5 + 3183^5 + 28969^5 + 85282^5 = 85359^5. Все числа так же раскладываются на простые множители.
Из этого я делаю «громкое» заключение что числа должны быть не простыми!
А теперь немного здравого смысла: если верить этому источнику, то от 1 до 3000 мы имеем 430 простых чисел — 14%. Итого эффективность алгоритма может возрасти примерно на 14 %))
27 = 3^3
84 = 2^2 * 3 * 7
110 = 2 * 5 * 7
133 = 7 * 19
144 = 2^4 * 3^2
т.е. все числа не простые. Аналогично я проверил для решения 55^5 + 3183^5 + 28969^5 + 85282^5 = 85359^5. Все числа так же раскладываются на простые множители.
Из этого я делаю «громкое» заключение что числа должны быть не простыми!
А теперь немного здравого смысла: если верить этому источнику, то от 1 до 3000 мы имеем 430 простых чисел — 14%. Итого эффективность алгоритма может возрасти примерно на 14 %))
Хотя сейчас начал проверять для 2682440^4 + 15365639^4 + 18796760^4 = 20615673^4.и обнаружил что 15365639 само является простое. Так что возможно моя теория потерпит фиаско.
Число простых с ростом n растет как n / ln n, т.е. для n=1000000 их уже всего всего 7%… Но если это утверждение хотя бы доказать — то тогда вполне можно добавить.
110 = 2 * 5 * 7Это в какой алгебре?
С ростом N простые числа будут встречаться все реже и реже. На одних проверках простоты потеряем больше.
При этом нет никаких гарантий, что следующее решение не будет содержать простых чисел.
a^5+b^5 = (a+b)(a^4-a^3b+a^2b^2-ab^3+b^4)
Вдруг это поможет для нового метода :)
Вдруг это поможет для нового метода :)
У нас есть два сервера для всяких расчетов. Один (Xeon E7-4850 — 4 CPUs, 40 cores, 128 Gb memory) сейчас свободен, поетому я решил поставить погонять эту программу.
С использованием OpenMP — 40 threads, 100% CPU:
#10:
n=20000 — 783 sec = чуть больше, чем 10 мин, т.е. примерно в 5 раз быстрее, чем в статье.
Я поставил для n=100000, завтра утром будет готово (у нас сейчас вечер)
У нас есть второй сервер (прям щас занят), в котором 48 «взрослых» cores и, кажется, 192 Гб.
Так, что если кому-то надо, то свистите, я могу на выходние поставить — кидайте код.
С использованием OpenMP — 40 threads, 100% CPU:
#10:
n=20000 — 783 sec = чуть больше, чем 10 мин, т.е. примерно в 5 раз быстрее, чем в статье.
Я поставил для n=100000, завтра утром будет готово (у нас сейчас вечер)
У нас есть второй сервер (прям щас занят), в котором 48 «взрослых» cores и, кажется, 192 Гб.
Так, что если кому-то надо, то свистите, я могу на выходние поставить — кидайте код.
Интересно. 40 ядер старенького Westmere на 2,1 ГГц в 4,4 раза быстрее, чем 6 новых ядер на 3,4.
Это даже лучше, чем прирост мегагерцев (4,1раз)
Значит задача отлично паралелится и не оптимизирована под новые инструкции.
Хотелось бы уточнить у автора, на чем именно запускались 1 6 16 потоков (процессоры 8+12потоков)
Это даже лучше, чем прирост мегагерцев (4,1раз)
Значит задача отлично паралелится и не оптимизирована под новые инструкции.
Хотелось бы уточнить у автора, на чем именно запускались 1 6 16 потоков (процессоры 8+12потоков)
Спасибо за предложение, я может до выходных еще оптимизаций на #10 повешу.
Я ничего не оптимизировал. Просто взял #10 код, вставил во внешнем цикле "#pragma omp parallel for" и выделил память под массивы vec1, vec2 внутри цикла
компилил MSVC12, GCC 5.3
Никаких принципиальных отличий MS — GCC не нашел
будет новый вариант — свистите громко. Хорошо бы до НГ, мы гуляем 3 дня, на работу 2-го.
После этого — придется гонять по ночам, серверы используются днем
компилил MSVC12, GCC 5.3
Никаких принципиальных отличий MS — GCC не нашел
будет новый вариант — свистите громко. Хорошо бы до НГ, мы гуляем 3 дня, на работу 2-го.
После этого — придется гонять по ночам, серверы используются днем
для 100 тыщ время было около 20 часов, посколку сервер был занят основной работой. Время процессора я не подумал пропечатать, только полное время
Второй сервер попроще, Xeon E5 2690, 2.9 GHz, 32 cores
зато памяти побольше — 256 ГБ
можно раскидать между двумя кампутерами
Второй сервер попроще, Xeon E5 2690, 2.9 GHz, 32 cores
зато памяти побольше — 256 ГБ
можно раскидать между двумя кампутерами
Артем, спасибо за текст. Вдохновляет. А гипотезу Била уже решили? Там хотя бы миллион можно получить)
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
10 новых сказок о потерянном времени