Как писать быстрые программы

[wrest]

Yadryara в сообщении #1720808 писал(а):

Только я её сознательно не отключал.

Наверное Qwen подкузьмил
В интерпетаторе все параметры можно посмотреть метакомандой \d
Конкретно параметр как много сообщать в консоль о памяти, называется debugmem, его значение можно посмотреть командой \gm

-- 21.03.2026, 16:31 --

Yadryara
В обработке цепочек вроде некому потребля память, по крайней мере у меня не потребляется.
Самое большое это таблицы простых и остатков.
Но у вас же всё в куче там, подготтвка паттерна с КТО и прочее - там наверное память и уходит.

-- 21.03.2026, 16:34 --

Yadryara в сообщении #1720812 писал(а):

То есть все фильтрации, начиная с 4-й, для всё меньшего количества предпростых ожидаемо выполняются хуже, кроме самой последней. Чудеса какие-то...

Этот абзац непонятен.

[Yadryara]

wrest в сообщении #1720814 писал(а):

В обработке цепочек вроде некому потребля память,

"Неприличными словами не выражаться!"

wrest в сообщении #1720814 писал(а):

Этот абзац непонятен.

Ну вот новая стата подоспела:

16   [0, 6967296, 2634638, 151997, 4555, 271, 0]                9min,    109 ms
17   [0, 6967296, 2634638, 110429, 2673, 184, 0]                8min, 58,533 ms
18   [0, 6967296, 2634638,  81282, 1556, 124, 1]               10min,  1,922 ms
19   [0, 6967296, 2634638,  60716,  903,  86, 1]               12min,  2,107 ms
20   [0, 6967296, 2634638,  45801,  533,  66, 1]               15min, 11,192 ms

21-ю степень 2-ки уж не стал смотреть и так понятно что будет.

Что тут непонятного...

Чем больше предпростых тем лучше фильтрация на этом 4-м этапе. Наглядно это и видим в 4-х элементах векторов: количество оставшихся цепочек всё меньше и меньше: 151, 110, 81, 60, 45 тысяч. И дальше этот статус-кво вроде сохраняется. А вот самая последняя фильтрация ведёт себя ровно наоборот — лучше фильтрует при меньшем количестве предпростых. И этому есть объяснение.

Ещё буду детально разбираться.

Здорово, что и время сильно снижается при переходе от 20-й степени к 16-17-й.

[wrest]

Yadryara в сообщении #1720815 писал(а):

Что тут непонятного...

Ничего. Какие-то столбцы цифр...
Что такое "предпростое"?

Yadryara в сообщении #1720815 писал(а):

количество оставшихся цепочек всё меньше и меньше: 151, 110, 81, 60, 45 тысяч.

А что такое "151, 110, 81, 60, 45 тысяч." - это вошло/вышло? Откуда/куда?
Суммы по векторам разные везде..

-- 21.03.2026, 18:37 --

Yadryara в сообщении #1720815 писал(а):

Здорово, что и время сильно снижается при переходе от 20-й степени к 16-17-й.

Это наоборот, не здорово. Это значит что фильтр по таблице простых у вас работает не очень хорошо, если я правильно понял о чем речь.

[Dmitriy40]

Это просто значит что таблица простых слишком велика и тратит слишком много времени без ощутимого эффекта - выгоднее не таблицу увеличивать, а пропускать больше цепочек на следующие этапы проверок.

-- 21.03.2026, 19:17 --

Функция времени работы от размера таблицы имеет минимум, и при уменьшении и при увеличении размера время растёт, при уменьшении из-за ухудшения фильтрации и более частого запуска следующих проверок, при увеличении из-за слишком длительного перебора таблицы. Судя по данным оптимум около 2^16..17.
Разумеется оптимум зависит от вида/качества дальнейших проверок, чем они лучше и быстрее, тем меньше нужна таблица.

[Yadryara]

wrest в сообщении #1720817 писал(а):

Yadryara в сообщении #1720815 писал(а):

Что тут непонятного...

Ничего.

Ничего непонятного. То есть всё понятно.

wrest в сообщении #1720817 писал(а):

Что такое "предпростое"?

Предвычисленное простое. Если в крайнем левом столбце 20, значит степень 2-ки 20-я. Значит предпростые, грубо говоря, берутся до миллиона.

wrest в сообщении #1720817 писал(а):

Yadryara в сообщении #1720815 писал(а):

количество оставшихся цепочек всё меньше и меньше: 151, 110, 81, 60, 45 тысяч.

А что такое "151, 110, 81, 60, 45 тысяч." - это вошло/вышло? Откуда/куда?

Мне не очень нравится вошло/вышло. Хотя можно и так.

Вот есть запись:

16   [0, 6967296, 2634638, 151997, 4555, 271, 0]

Если в крайнем левом столбце 16, значит степень 2-ки 16-я. То есть 4-е значение 151997 — это количество цепочек оставшихся после 4-й фильтрации (до $2^{16})$.
4555 — количество цепочек оставшихся после 5-й фильтрации.
271 — количество цепочек оставшихся после 6-й фильтрации.
0 — количество цепочек оставшихся после 7-й фильтрации.

Далее в том же интервале с другой настройкой:

17   [0, 6967296, 2634638, 110429, 2673, 184, 0]

Если в крайнем левом столбце 17, значит степень 2-ки 17-я. То есть 4-е значение 110429 — это количество цепочек оставшихся после 4-й фильтрации (до $2^{17})$.
2673 — количество цепочек оставшихся после 5-й фильтрации.
184 — количество цепочек оставшихся после 6-й фильтрации.
0 — количество цепочек оставшихся после 7-й фильтрации.

Количество цепочек оставшихся после 4-й фильтрации всё меньше и меньше: 151 и 110 тысяч соответственно.


А, ну вот, Дмитрий понял правильно.

[wrest]

Мои данные, на миллионе цепочек.
"Терапевтика" отбрасывает 727 857, на этап проверки по таблице простых остается 272 143
Из этих 272 143, в зависимости от величины таблицы, отбрасывается:

2^  отброшено прошло дальше 
24  272127         16
23  272126         17
22  272120         23
21  272103         40
20  272090         53
19  272064         79
18  272029         114
17  271949         194
16  271831         312
15  271617         526
14  271178         965

[Dmitriy40]

wrest
По этим данным оптимум не определить - рассмотрим две крайние ситуации:
1. дальнейшие проверки моментальны - оптимум будет вообще без таблицы;
2. дальнейшие проверки очень долгие или отсутствуют - оптимум будет при максимально большой таблице.
При реальных временах следующих проверок оптимум будет где-то в промежутке, но в зависимости от соотношения времён проверки таблицы и следующих.
Предположительно около 2^16..18.

Т.е. нет смысла бороться за качество фильтрации в отрыве от дальнейших проверок, нас же волнует оптимизация общего времени (т.е. скорость перебора), а не отдельных его частей (если они не независимы, а тут это очевидно не так).

[wrest]

Dmitriy40 в сообщении #1720831 писал(а):

Т.е. нет смысла бороться за качество фильтрации в отрыве от дальнейших проверок, нас же волнует оптимизация общего времени (т.е. скорость перебора), а не отдельных его частей (если они не независимы, а тут это очевидно не так).

Согласен, но как я говорил, из-за тротлинга не очень доверяю времени.
Получилось так:

2^ скорость цепочек в секунду
24 220994
23 200722
22 201857
21 204834
20 197472
19 192566
18 205212
17 193610
16 202020
15 191204
14 172087

тут общая скорость - включая все стадии отсева (но не включая формирование паттерна)

[Dmitriy40]

Ну если не обращать внимания на выбросы, то вижу скачок скорости на 2^15 и потом в общем почти стабильно.
Считать ли скорость при 2^24 выбросом это вопрос, может и правда следующий скачок. Или ошибка измерений.
Если про 2^24 забыть, то нет большого смысла делать таблицу больше 2^15. Хотя если ничему не мешает, то можно и максимально большую, раз уж до торможения не добрались.

С другой стороны, при достаточно хорошей фильтрации размер таблицы начиная с некоторой пороговой величины роли уже не играет - она никогда не перебирается до конца, всегда обрывается до того. Но тогда и последующие проверки уже не нужны. Если не точно всегда, а почти всегда, но следующие проверки не слишком медленные и уже почти не влияют на общее время - тоже нет смысла увеличивать размер таблицы. Что похоже и наблюдаем.
И нет, это не противоречит моим предыдущим словам про минимум времени - это оптимизация по двум разным переменным и неудивительно что результат разный.