Comments 86
> в исполнении clang 3.1
А почему не 3.2?
А почему не 3.2?
Можно использовать ассемблерные вставки?
Можно юзать pthread?
Можно ли использовать С++11?
Сделал в студии — надеюсь прокатит и скомпилится.
OpenMP/TBB можно использовать?
Вопрос, в приведенном пример учитывалось общее время работы программы вместе с вводом данных или только цикла расчета ???
Конечно, с вводом. Да и вообще, какая разница? Мы же читаем только одно число и пишем одно число
Ну как вам сказать, ввод числа руками, ввод из файла и константа это разные по времени обработки методы ввода. Например константа вообще не требует обработки, ввод из файла зависит от скорость диска и т.п. ввод руками вообще зависит от пользователя, (что если я пойду чайку хлебнуть а интер не нажму)
А время как мы видем идет на миллисекунды, это важно, надо либо обозначить как именно все должны делать ввод данных либо ваша time неочем.
А время как мы видем идет на миллисекунды, это важно, надо либо обозначить как именно все должны делать ввод данных либо ваша time неочем.
Ввод в данном случае не важен, т.к. важно время, занятое у ЦП (колонка user у time).
Напишите параметры, с которыми вы компилируете.
Судя по ограничениям, можно использовать готовый массив простых чисел, если уложиться в 1024 байт?
Начнём с однопоточного решета. На Core i5 430UM 1200 Mhz в минуту уложился.
Хм, у меня тест Миллера-Рабина на 2 в 30-ой степени в минуту не помещается.
Для 230-1?
UFO just landed and posted this here
> Побеждает тот, кто напишет самое быстрое решение
Время оценивается какое? Wall clock?
Время оценивается какое? Wall clock?
UFO just landed and posted this here
UFO just landed and posted this here
Маньячина, а теперь разархивированную версию ;-)
Я паковал 8 чисел, взаимно простых с 30 (от 30k+1 до 30k+29) в 1 байт. Выбивал числа так же умножая только на взаимно простые с 30, да еще запоминал таблицу умножения данного простого на числа 1..29 в системе счисления «сдвиг — бит». Плюс борьба с тем, чем массив c решетом не вмещался в кэш.
На i5 2.67МГц для N=10^9 время 0.65 сек.
Но это если решение вообще работает.
На i5 2.67МГц для N=10^9 время 0.65 сек.
Но это если решение вообще работает.
И даже на тесте 268588319 укладывается в секунду? ;)
UFO just landed and posted this here
результат такой же, время 0.156 s (на i5)
UFO just landed and posted this here
А в нечитаемом можно посмотреть? :)
Ещё мне кажется, что для i == 0 можно просто начать с res = (-1) + 2 + 3 + 5 + 7 + 11 + 13; и сэкономить немало байтов кода, например для бОльшей таблицы предподсчета.
Да и саму таблицу можно сделать эффективнее, вместо лестницы if-ов используя массив и цикл.
Ещё мне кажется, что для i == 0 можно просто начать с res = (-1) + 2 + 3 + 5 + 7 + 11 + 13; и сэкономить немало байтов кода, например для бОльшей таблицы предподсчета.
Да и саму таблицу можно сделать эффективнее, вместо лестницы if-ов используя массив и цикл.
Ещё можно избавиться от относительно дорогого деления, заранее подсчитав:
И после просеивания
Не уверен, что улучшит, но вдруг :)
И ещё — просеивание можно делать до sqrt(i), а не до
k[j] = start_from / primes[j];
И после просеивания
k[j] -= block_size;
Не уверен, что улучшит, но вдруг :)
И ещё — просеивание можно делать до sqrt(i), а не до
j < primes_count;Ну и распараллелить должно быть несложно.
Хотя ради этого придётся уменьшить таблицу, что в итоге может оказаться невыгодным.
Хотя ради этого придётся уменьшить таблицу, что в итоге может оказаться невыгодным.
gcc — это вообще другой разговор. Почти всё на gcc будет чуть быстрее. Зачем Вы спрашивали ключи компиляции тогда?
Просто на 268588319 у меня Ваше решение работает больше секунды (на 3,6ГГц) и раза в 3 медленнее, чем 2^30 — 1 (на clang 3.2 в linux x64 с флагом -O3) — из-за предподсчёта.
Просто на 268588319 у меня Ваше решение работает больше секунды (на 3,6ГГц) и раза в 3 медленнее, чем 2^30 — 1 (на clang 3.2 в linux x64 с флагом -O3) — из-за предподсчёта.
написал так:
1) считаем простые числа в диапазоне от 1 до sqrt(n)
2) так как чисел всего 2^31, определяет рабочий интервал, для которого уже просчитана сумма чисел в предыдущем интервале. интервалов 16, в среднем надо просчитать от начала интервала до его середины. итого 1/32
3) считаем сумму оставшихся простых чисел в рабочем интервале, блочным решетом эратосфена с примитивными оптимизациями чётных значений.
блочное решето с примитивными оптимизациями работает на значениях 2^29 около 0,5 секунд. С предпросчётом от 0,01 до 0,05
1) считаем простые числа в диапазоне от 1 до sqrt(n)
2) так как чисел всего 2^31, определяет рабочий интервал, для которого уже просчитана сумма чисел в предыдущем интервале. интервалов 16, в среднем надо просчитать от начала интервала до его середины. итого 1/32
3) считаем сумму оставшихся простых чисел в рабочем интервале, блочным решетом эратосфена с примитивными оптимизациями чётных значений.
блочное решето с примитивными оптимизациями работает на значениях 2^29 около 0,5 секунд. С предпросчётом от 0,01 до 0,05
Совсем не понял зачем там G, D, F. Если их убрать, код уменьшится на 59 байт.
Какие прогнозы на лучшее время?
Думаю, 0.3-0.5 сек на тест.
Думаю, 0.3-0.5 сек на тест.
Да, про явные формулы я забыл. Хакеры-математики, конечно, непобедимы.
Нет-нет, формул тут никаких нет, кроме китайской теоремы об остатках (она максимум даст ускорение в 2-3 раза).
Я бы оценивал по суммарному результату на N случайных числах (одинаковых для всех), двоичные логарифмы которых (с плавающей точкой) распределены равномерно в интервале [20,30]
А потом, для десятки лучших на ещё бОльшем количестве тестов.
Можно спросить почему Вы бы оценивали иначе? И где можно прочитать про метод подборки входных тестовых данных, вамиприведенный?
Дело в том, что заранее зная тесты, можно написать программу, эффективную именно для этого.
Например, программа, печатающая 454396537 независимо от ввода, победит в конкурсе программ, которые будут тестироваться только числом 100000.
Например, программа, печатающая 454396537 независимо от ввода, победит в конкурсе программ, которые будут тестироваться только числом 100000.
Нет, лучше, чтобы равномерно были распределены сами числа. Иначе половина примеров окажется меньше 2^25, а там время практически нулевое.
Ещё интересным был бы рейтинг «по худшему времени» — подозреваю, что после обфускации большинство решений легко укладываются в 1024 байта, поэтому для дальнейшего ускорения логично использовать таблицу предварительно вычисленных значений.
Тесты на небольшом наборе вводов могут легко превратиться в лотерею — и победит тот, кто лучше угадает с таблицей.
А вот если отсортировать участников по лучшему «худшему времени» на одном вводе и потом тщательно проверять лучших, найдя худшее время каждого.
Тесты на небольшом наборе вводов могут легко превратиться в лотерею — и победит тот, кто лучше угадает с таблицей.
А вот если отсортировать участников по лучшему «худшему времени» на одном вводе и потом тщательно проверять лучших, найдя худшее время каждого.
Sign up to leave a comment.
Новогоднее хабра-соревнование по программированию-2013 (C++)