Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 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?
> Побеждает тот, кто напишет самое быстрое решение
Время оценивается какое? Wall clock?
Время оценивается какое? Wall clock?
Маньячина, а теперь разархивированную версию ;-)
Я паковал 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 укладывается в секунду? ;)
результат такой же, время 0.156 s (на i5)
А в нечитаемом можно посмотреть? :)
Ещё мне кажется, что для 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 байта, поэтому для дальнейшего ускорения логично использовать таблицу предварительно вычисленных значений.
Тесты на небольшом наборе вводов могут легко превратиться в лотерею — и победит тот, кто лучше угадает с таблицей.
А вот если отсортировать участников по лучшему «худшему времени» на одном вводе и потом тщательно проверять лучших, найдя худшее время каждого.
Тесты на небольшом наборе вводов могут легко превратиться в лотерею — и победит тот, кто лучше угадает с таблицей.
А вот если отсортировать участников по лучшему «худшему времени» на одном вводе и потом тщательно проверять лучших, найдя худшее время каждого.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Новогоднее хабра-соревнование по программированию-2013 (C++)