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

[Yadryara]

Спасибо, примерно так и думал.

Ну вот кстати у меня в новом поиске (D(96,7)) довольно характерная картинка нарисовалась. Я считал 12 однотипных комплектов по предпростым до 2^14. Размер стека всё увеличивался. И вот, когда он в начале 10-го комплекта достиг уже очень солидной величины, уже больше 8ГБ, рост времени счёта стал прям очень заметен.

Ограничение уже видимо достигло почти предельной величины — около 15-16 ГБ.

.   [768678, 0, 352460, 131390, 5645, 4050, 62]         1min, 470 ms
.   [768678, 0, 352489, 131130, 5658, 4097, 80]         1min, 1,527 ms
.   [768678, 0, 352486, 131088, 5618, 4012, 72]         1min, 748 ms
.   [768678, 0, 352475, 131229, 5619, 4053, 74]         59,920 ms
.   [768678, 0, 352509, 131198, 5496, 3895, 76]         59,751 ms
.   [768678, 0, 352497, 131448, 5507, 3960, 82]         1min, 107 ms
.   [768678, 0, 352472, 131394, 5572, 3955, 91]         1min, 267 ms
.   [768678, 0, 352473, 131490, 5598, 3933, 85]         59,996 ms
9.  [768678, 0, 352492, 131107, 5527, 3950, 67]         1min, 2,730 ms    до 4 и 8 ГБ
10. [768678, 0, 352473, 131097, 5553, 3951, 79]         1min, 16,359 ms   до 16000 МБ
11. [768678, 0, 352506, 130903, 5503, 3983, 74]         1min, 30,920 ms
12. [768678, 0, 352492, 131321, 5459, 3850, 56]         1min, 48,435 ms

И из-за этого фильтрация по предпростым до 2^14 в итоге проиграла 2^13 по скорости счёта, хотя по первым 9-ти комплектам выигрывала:

Серия            2^     Комплектов       Счёт     Найдено      Время       Скорость
                         посчитано    от 0 до     D(96,7)     секунд    D(96,7)/час
0-0-5-2-0-3!     13     2! * 3! 12       1e24         355        808           1582
0-0-5-2-0-3!     14     2! * 3! 12       1e24         355        822           1555

[wrest]

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

Размер стека всё увеличивался. И вот, когда он в начале 10-го комплекта достиг уже очень солидной величины, уже больше 8ГБ, рост времени счёта стал прям очень заметен.

Надо смотреть на код -- эти "комплекты" у вас в одном цикле?
Если бы, скажем, обсчётом "комплекта" зарималась функция, то по её завершению стек должен освобождаться добровольно-принудительно. То есть вся память, что утекала внутри функции, должна бы вернуться.

А если сразу запустить 9-й "комплект" пропустив предыдущие?

[Yadryara]

От функции я уже давным-давно отказался. И вроде как по нескольким причинам.

Считать 96 делителей это довольно сложная затея. Так что в данном случае было 4 вложенных цикла. Только стартовые строки этих циклов:

forperm( numtoperm (#rp1, strass1), rassrp1, 
forperm( numtoperm (#rp2, strass2), rassrp2,
forperm( numtoperm (#spichis4, strass4), minirass4,
for(i:small = starti, starti + koli - 1, 

Внешние два цикла — это расстановка простых чисел по первому и 2-му спискам соответственно. Затем расстановка квадратов простых чисел по 4-му списку. Ну и самый внутренний цикл — тот самый цикл по i, который раньше был в функции, где и идёт проверка конкретной цепочки.

В данном случае под комплектом я имел в виду два внутренних цикла. То есть внешние циклы выполняются $2!\cdot3! = 12$ раз, что и было написано выше

Уменьшив количество комплектов с 12-ти до 4-х, я сумел посчитать как надо.

Можно ведь не все перестановки делать:

if(permtonum(rassrp2)  == strass2 + 2, break);

-- 06.04.2026, 14:52 --

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

А если сразу запустить 9-й "комплект" пропустив предыдущие?

Можно конечно. О чём вопрос?

[Dmitriy40]

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

Внешние два цикла — это расстановка простых чисел по первому и 2-му спискам соответственно. Затем расстановка квадратов простых чисел по 4-му списку. Ну и самый внутренний цикл — тот самый цикл по i, который раньше был в функции, где и идёт проверка конкретной цепочки.

Вот самый внутренний цикл и вынести в отдельную функцию. Если ей много параметров (т.е. мегабайты) не передавать, она ведь видит все переменные родительской функции и глобальные, то её вызов будет быстрым (по сравнению с временем выполнения самого внутреннего цикла) и потеря скорости пренебрежимой. А по завершению функции (одного выполнения внутреннего цикла) стек будет очищен - и соответственно не будет расти до посинения.

[Yadryara]

Раньше-то этот внутренний цикл и был в отдельной функции. Но вроде бы переполнения стека всё равно были.

А вот батники, позволявшие перезапускать программу каждые 10-15 минут, обсчитывая каждый раз всё новые и новые комплекты, эту проблему решали. Но каждую минуту запускать, пожалуй, не стоит.

[wrest]

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

Можно конечно. О чём вопрос?

Вопос в том утекает ли память постепенно, или 9-й комплект особенный.

-- 06.04.2026, 20:02 --

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

Ну и самый внутренний цикл — тот самый цикл по i, который раньше был в функции, где и идёт проверка конкретной цепочки.

Одной цепочки? Чему обычно равно koli в
for(i:small = starti, starti + koli - 1, ?

[Yadryara]

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

Вопос в том утекает ли память постепенно, или 9-й комплект особенный.

Конечно постепенно. Это же уже давным-давно выяснено. Внутри серии комплекты однотипные. Поэтому батники и работали в своё время. Правда, для некоторых комплектов изредка всё-таки получалось переполнение и пришлось мне уменьшить размер обсчитываемого при каждом запуске программы куска с 40 до 25 единиц. Но зато этот новый размер уже обсчитывался всегда, без переполнения.

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

Одной цепочки? Чему обычно равно koli в
for(i:small = starti, starti + koli - 1, ?

Ну нет конечно, не одной цепочки. koli как раз и показывает сколько будет проверяться цепочек этими самыми многочисленными фильтрациями, начиная с терапевтики.

А вот говорить о том, чему обычно равно koli, как раз трудно. Это внутри серии цепочки однотипные. А при переходе от серии к серии ещё как отличаются — koli то больше миллиона, а то норовит оказаться меньше тысячи.

Вот, кстати, очередное сравнение серий между собой:

Серия            2^     Комплектов       Счёт     Найдено      Время       Скорость
                         посчитано    от 0 до     D(96,7)     секунд    D(96,7)/час
0-0-5-2-0-3!     13     2! * 3! 12       1e24         355        808           1582
0-0-5-2-0-3!     14     2! * 3! 12       1e24         355        822           1555

0-0-5-2-0-3!     13     2! * 2!  4       1e24         121        263           1656
0-0-5-2-0-3!     14     2! * 2!  4       1e24         121        245           1778 best
0-0-5-2-0-3!     15     2! * 2!  4       1e24         121        250           1742

0-0-6-1-0-3!     13     2! * 2!  4       1e25          72         89           2912
0-0-6-1-0-3!     14     2! * 2!  4       1e25          72         83           3123 best
0-0-6-1-0-3!     15     2! * 2!  4       1e25          72         84           3086

0-0-7-0-0-3!     14     2! * 3! 12       1e26          81         69           4226
0-0-7-0-0-3!     15     2! * 3! 12       1e26          81         67           4352 best
0-0-7-0-0-3!     16     2! * 3! 12       1e26          81         67           4352 best
0-0-7-0-0-3!     17     2! * 3! 12       1e26          81         80           3645

0-1-6-0-0-3!     15     2! * 5! 24       1e27         100         52           6923
0-1-6-0-0-3!     16     2! * 5! 24       1e27         100         51           7059 best
0-1-6-0-0-3!     17     2! * 5! 24       1e27         100         57           6315

То есть для верхней серии (0-5-2), где величина n не превышала 1e24, koli = 128113.
Для второй серии (0-6-1) koli = 128113*10/37 = 34626.
Для третьей серии (0-7-0) koli = 128113*100/37/41 = 8446.
Для четвёртой серии (1-6-0) koli = 128113 * 1000/37/41/43 = 1964.

А ведь ещё одну серию надо посчитать. Но тогда получится слишком маленькое koli. И, видимо, придётся опять пересчитывать предыдущую серию, увеличив интервал по n в 10 раз. А значит и koli надо поднять в 10 раз, до 19640. Тогда для последней серии koli = 128113 * 100000/37/41/43/47 = 4179

[Yadryara]

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

Мне не очевидно!

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

Ну вот вы начали искать цепочку 19-252. Вы попытались прикинуть сколько времени в среднем займёт поиск. Допустим, оценили в 3 месяца. А сколько цепочек собрались за 90 дней найти? Допустим, одну. Разве это не то же самое, что сказать:

ожидаю среднюю скорость нахождения цепочек 0.00046 в час?

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

К тому же имея мат.ожидание легко пересчитать эту скорость в скорость нахождения решений или требуемое время до нахождения n решений.

А уверенность в этом матожидании откуда возьмётся? Вот мы с вами считали вероятности в пента-теме. Вы считали прямым способом, я — обратным. Результаты сошлись. Разве это не лучше, разве это не добавляет уверенности, когда разными способами оценки получены.

Вот мы считали мат. ожидание кортежей, предложенным мной способом, с предварительным подсчётом затравки. Он был сложный, но оценки были получены. Затем посчитали другим способом, по HL1. И тоже результаты сошлись.

Разве это не здорово.

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

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

Возможно, придётся. Но я вот пока намеренно их не ускоряю.

"выходной поток далеко не нулевой" — вот именно. Это и позволяет надёжнее стоять на земле, а не витать в ожиданиях, пусть и математических.

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

[Dmitriy40]

Yadryara
Программа быстрее других находящая тысячу D(96,6) может оказаться не самой быстрой для D(96,8) и тем более для D(96,15). И чем длиннее искомая цепочка, тем больше будет разница. Я на это натолкнулся когда стал своей программой для длинных цепочек искать короткие - она страшно тормозила потому что слишком часто проваливалась в поздние долгие проверки.
Потому оптимизация скорости на коротких цепочках не обязательно даст выигрыш на длинных цепочках.
Например слишком короткие цепочки выгоднее искать решетом (Эратосфена или аналогичными). Но для длинных цепочек это на много порядков медленнее.
А короткие цепочки не интересны. И оптимизация скорости под них тоже не слишком интересна.

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

Ну вот вы начали искать цепочку 19-252. Вы попытались прикинуть сколько времени в среднем займёт поиск. Допустим, оценили в 3 месяца.

И как же это оценили? Лично я оценивал по скорости перебора, а не по скорости нахождения цепочек (которых не было!).
И как Вы будете оценивать требуемое время не имея величины "среднюю скорость нахождения цепочек 0.00046 в час"? Откуда её возьмёте? Из более коротких цепочек? Так не факт что она сохранится. А скорость перебора можно замерить прямо на нужной цепочке. В том числе за секунды, что позволяет легко перетестировать много разных вариантов оптимизаций.

-- 07.04.2026, 16:48 --

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

Я не отказываюсь посчитать мат. ожидание другим способом,

А я вообще не про мат.лжидание! Даже имея мат.ожидание величины искомой цепочки что Вы будете с ним делать-то? Как время получить? Для этого же некая скорость нужна - откуда её получите? Вот пусть мат.ожидание цепочки 21-360 будет 1e28 - ну и сколько на неё надо времени? Как для неё получить Вашу 0.0046 цепочек/ч (или любую другую конкретную цифру)?

[Yadryara]

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

Программа быстрее других находящая тысячу D(96,6) может оказаться не самой быстрой для D(96,8) и тем более для D(96,15). И чем длиннее искомая цепочка, тем больше будет разница.

Банальности, да.

Я смотрю тенденции, постепенно переходя от коротких цепочек к длинным. Как и для кортежей. Интересную особенность 96 делителей уже отметил.

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

И как же это оценили?

Я не помню как вы оценили. И не помню в три месяца или во сколько. Я же специально сказал: допустим. И мой вопрос в том, являются ли оценки 1 цепочка за 90 дней и 0.00046 цепочек в час эквивалентными?

[Dmitriy40]

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

Я не помню как вы оценили.

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

[Yadryara]

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

Вот пусть мат.ожидание цепочки 21-360 будет 1e28 - ну и сколько на неё надо времени?

Указывать мат. ожидание, не указывая интервал, это как писать на деревню дедушке

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

Как для неё получить Вашу 0.0046 цепочек/ч (или любую другую конкретную цифру)?

Ну вот например, по HL1 я посчитал мат. ожидание для центральных 15-к для интервала $0-61\#$. Оно оказалось равно примерно 1139 кортежей.

Я знал что для полного обсчёта всего $0-61\#$ мне понадобится 11 месяцев счёта. Ну вот взяв 333 дня и разделив одно на другое, можно получить среднюю скорость нахождения 0.1425 кортежей в час.

Что тут сложного? Почему вы об этом спрашиваете?

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

По скорости перебора, конечно же.

Так я не спрашивал как вы оценили. Я спрашивал, являются ли формулировки эквивалентными.

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

А по скорости нахождения цепочек оценить время можно только постфактум, когда цепочки уже найдены.

Нет конечно, если известны тенденции, то можно экстраполировать их, учтя найденные ранее скорости.

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

А когда цепочка найдётся - скорость станет уже не нужной.

Нужной. Как раз для анализа тенденций и экстраполяции в случае их выявления. Я ведь так и делал в кортежной теме.

[Dmitriy40]

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

Указывать мат. ожидание, не указывая интервал, это как писать на деревню дедушке

Подразумевалось что в этом интервале есть одна цепочка. Т.е. мат.ожидание интервала, не количества цепочек.

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

Я знал что для полного обсчёта всего $0-61\#$ мне понадобится 11 месяцев счёта.

Откуда Вы это знали?! Как получили цифру 11 месяцев? Сколько центральных 15-к для этого нашли и за какое время?

Что-то в своих примерах Вы с ног на голову всё перевернули. Сначала говорили для оценки времени нужна средняя скорость нахождения кортежей (с чем я и стал спорить), теперь оказывается всё наоборот, среднюю скорость вычисляете как известное непонятно откуда время делить на мат.ожидание количества кортежей.
Нет уж, давайте по честному, как говорили, из мат.ожидания количества кортежей (1 кортеж на интервал 1e28) и неизвестной средней скорости нахождения кортежей (ни один ещё не найден) получите ожидаемое время.

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

Нет конечно, если известны тенденции, то можно экстраполировать их, учтя найденные ранее скорости.

Не работает. Или слишком грубо.

-- 07.04.2026, 20:00 --

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

Нет уж, давайте по честному, как говорили, из мат.ожидания количества кортежей (1 кортеж на интервал 1e28) и неизвестной средней скорости нахождения кортежей (ни один ещё не найден) получите ожидаемое время.

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

[wrest]

Можно ещё заниматься нумерологией, считая сколько из миллионаа (вариант - триллиона) генерируемых цепочек получаются с 5-ю дырками, сколько с 4-мя и т.п. И как-то "экстраполировать" сколько их будет с нулём дырок Чем не метод?

[Dmitriy40]

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

Чем не метод?

Этим тоже занимались при поиске 19-252, да и пентадекатлона тоже.
Но это не даёт метода оценки эффективности оптимизаций. Даже выше были примеры когда лучшая фильтрация оказывается более медленной и потому невыгодной.

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