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

[wrest]

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

*** at top-level: init_Rab_41()
*** ^-------------
*** init_Rab_41: the PARI stack overflows !
current stack size: 4000002048 (3814.699 Mbytes)
[hint] you can increase 'parisizemax' using default()

У вас эта проблема ещё осталась?

Память утекает постепенно или резко именно на этом числе?
За памятью можете следить при помощи btop :)

Это я так понимаю 41-й "поток"? Как вы запускаете счёт с того места (ну или плюс-минус скажем минута) на котором остановились (например из-за переполнения стека)?

-- 15.11.2025, 21:09 --

Прикольные штуки попадаются. Например переменная z0 (вектор) упоминается в коде три раза.

   Строка  40:   z, z0, nu,
   Строка 180:                   z0 = [1..#v];
   Строка 232:                     foreach(z0, d,

Т.е. вектор z0 из последовательных чисел начиная с 1, создаётся только для того, чтобы поучаствовать потом в foreach.

Почему не

Строка  40:   my(z0:small)
   Строка 180:                   z0 = #v;
   Строка 232:                     for(d=1, z0,  

В Си это foreach транслируется так:

                                                          l47 = glength(z0);
                                                          {
                                                            pari_sp btop = avma;
                                                            long l51;
                                                            GEN d = gen_0;
                                                            for (l51 = 1; l51 <= l47; ++l51)
                                                            {
                                                              d = gcopy(gel(z0, l51));

То есть всё равно организуется цикл for

[Dmitriy40]

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

Т.е. вектор z0 из последовательных чисел начиная с 1, создаётся только для того, чтобы поучаствовать потом в foreach.

Для универсальности кода. И краткости (foreach часто более понятен чем for с лишней переменной и постоянными индексами в теле цикла). Это в данном случае z0 именно такой и нужен один раз, а с другим паттерном он может стать и иным.
Хотя, если очень хочется, его можно заменить на битовую маску (длиной #v, т.е. пару десятков битов, влезает в int) плюс for плюс bittest, на PARI это наверняка будет медленнее, зато на С - так же наверняка быстрее.

[Yadryara]

wrest, так это я у вас хотел спросить. Вы же теперь тестировать начали.

А я, ожидая результатов вашего теста, пока вернулся к старому способу. Почти за сутки обсчитал замену 53 на 59. Теперь вот считаю паттерн 2-13-5-8!

У вас все 80 расстановок успешно посчитались?

Вот что я написал о результатах моего последнего тестирования:

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

Это только для одного потока. А как для 12-ти? Я это не выяснил до сих пор. В новом запуске тоже не хватило памяти. Правда, это случилось позже, то есть счёт прошёл дальше, прежде чем прерваться:

14.   1 1   1 2   1 6     13 8   17 5   19 16
15.   1 1   1 2   1 7     13 8   17 5   19 18
3528990856474405723050249827738486681269123540        1 111  11 1 111111 1             14

16.   1 1   1 2   1 8     13 8   17 5   19 19
17.   1 1   1 3   1 1     13 8   17 12   19 2
18.   1 1   1 3   1 2     13 8   17 12   19 3
  ***   at top-level: init_Rab_41()
  ***                 ^-------------
  *** init_Rab_41: the PARI stack overflows !
  current stack size: 536870912 (512.000 Mbytes)
  [hint] set 'parisizemax' to a nonzero value in your GPRC

  ***   Break loop: type 'break' to go back to GP prompt
break>

Подальше, потому что показана уже не 15-я, а 18-я расстановка.

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

Память утекает постепенно или резко именно на этом числе?
За памятью можете следить при помощи btop :)

Понятия не имею. И не умею следить при помощи btop.

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

Это я так понимаю 41-й "поток"?

Откуда возьмётся 41-й поток, если их всего 12 и нумерация от 0 до 11 ??

Нет, конечно, Rab-41.gp это название рабочей программы. Полоса паттерна стартует с 4-го числа, поэтому и название начинается с 4-ки.

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

Как вы запускаете счёт с того места (ну или плюс-минус скажем минута) на котором остановились (например из-за переполнения стека)?

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

У вас все 80 расстановок успешно посчитались?

[wrest]

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

У вас все 80 расстановок успешно посчитались?

У меня нет компа который может считать много часов. Есть ноутбук, который я беру в руки (довольно редко) чтобы что-то поделать. Потом его закрываю, кладу на полку.

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

Никак не запускаю. Пока жду результатов тестирования от вас.

Я запустил на час, у меня всё хорошо было. На 10 часов или сутки я запустить не могу. Каждый инстанс за час просчитал 6 расстановок (если я правильно понимаю терминологию) - логи я вам присылал. Итого 24 расстановки за час. Много это или мало я не знаю.

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

Ну тогда было бы логично писать в лог какие-то параметры, скажем раз в 10 минут, по которым вы можете возобновить счёт с этого места. И предусмотреть в коде такую возможность (возобновления).
Вот на моём ноуте кстати примерно раз в 10 минут и возникает запись в логе.
Вот например.

2     1.
2     2.
2     3.
2     4.
2     5.
2     6.

Считаем что "2 5." досчиталось. Как продолжить счёт с "2 6."?

Тут вам надо решить существенно это для вас или нет - готовы вы ваше время потратить или нет.
Я точно не готов :) Я постарался дать вам в руки инструмент, который ускорит ваши вычисления, пользуйтесь :)

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

Откуда возьмётся 41-й поток, если их всего 12 и нумерация от 0 до 11 ?

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

[Yadryara]

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

Я запустил на час, у меня всё хорошо было.

И вы сказали мне о том, что прервали тестирование? Нет. Логично было считать, что тестирование продолжается? Да.

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

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

Вот опять тот же самый интересный вопрос. Почему люди говорящие на одном и том же русском языке ухитряются не понимать друг друга?

Я рассказывал о том, с какого места я продолжил? Сказал. Дважды сказал или единожды? Приводить цитату?

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

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

Я сказал, что один лог для прогресса, а другой для находок? Сказал. Приводить цитату?

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

Каждый инстанс за час просчитал 6 расстановок (если я правильно понимаю терминологию) - логи я вам присылал.

И в логах это записано, не так ли? То есть уже сделано ровно то, что вы советуете выше. Если 6 расстановок записаны в лог за час, то есть за 60 минут, то разве это не означает запись 1 раз в 10 минут, о которой вы только что сказали??

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

Я постарался дать вам в руки инструмент, который ускорит ваши вычисления, пользуйтесь :)

Ещё раз Большое Спасибо.

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

Это вопрос риторический, я же вам говорил, что погружаться не хочу,

Да, говорили. И Дмитрий тоже в своё время не хотел погружаться, и впс тоже. Однако же настроения у людей меняются и люди порой начинают разбираться в вопросе лучше чем те, кто их этим вопросом увлёк.

А про то, что потоки нумеруются от 0 до 11 я тоже говорил. Стало быть никакого 41-го пока что нет.

Так что версия у меня прежняя — люди хотят себя слушать, а не других. Мало ли что собеседник говорил. Сожалею, что это так.

[Yadryara]

Решил сам проявить внимательность к словам собеседника. Увидел что вы дописали:

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

Считаем что "2 5." досчиталось. Как продолжить счёт с "2 6."?

Стартовать сразу с 6-й расстановки. Я знаю как именно, но вам вроде подробности были неинтересны. К ускорению счёта это вроде не имеет отношения.

Если человек мне помогает и не знает как продолжить, то вопрос решается просто: я сам досчитываю хвост в этом прерванном интервале, а человек считает новый интервал.

[wrest]

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

Стартовать сразу с 6-й расстановки. Я знаю как именно, но вам вроде подробности были неинтересны. К ускорению счёта это вроде не имеет отношения.

Имеет в том смысле, что можно параллельно считать не только "потоки" но и "расстановки" внутри потоков.

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

Если человек мне помогает и не знает как продолжить, то вопрос решается просто: я сам досчитываю хвост в этом прерванном интервале,

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

[Yadryara]

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

Имеет в том смысле, что можно параллельно считать не только "потоки" но и "расстановки" внутри потоков.

Не понял что это значит.

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

то я бы посоветовал писать так, чтобы в программу без её перекомпиляции и корректировки, можно было просто передать параметрами что считать.

А, ну это конечно логично. Я же писал, что программу предполагается улучшать многократно.

[wrest]

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

Не понял что это значит.

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

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

А, ну это конечно логично. Я же писал, что программу предполагается улучшать многократно.

Тут вопрос, скажем так, проектирования.
То есть вы говорите -- ну вот, у нас есть модуль подготовки данных (всё что до forstep()и модуль счёта (всё что в forstep()). Сейчас наша программа прямо в коде содержит какие-то вектора типа [4, 5, 8, 12, 14, 16] или [23, 29, 31, 37, 41, 43, 47, 53] и магические числа типа 19620, 3360 и подобные. Давайте подумаем:
- будут ли эти параметры меняться для последующего счёта
- зависит ли алгоритм и код от конкретных значений в этих параметрах
Если ответ "будут меняться, алгоритм не зависит", то тогда спросим себя: а почему бы нам не передавать все эти параметры или их часть (какую?) в программу вместо того, чтобы вписывать их в программу хардкодом?

[Yadryara]

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

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

Всё равно не понял. Ведь и так идёт параллельный счёт разных расстановок, ведь потоков не 1, а 12.

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

Сейчас наша программа прямо в коде содержит какие-то вектора типа [4, 5, 8, 12, 14, 16] или [23, 29, 31, 37, 41, 43, 47, 53] и магические числа типа
19620, 3360 и подобные. Давайте подумаем:
- будут ли эти параметры меняться для последующего счёта
- зависит ли алгоритм и код от конкретных значений в этих параметрах

Чего тут думать, это же банальные вещи, разумеется эти числа, которые временно заданы руками, можно считать автоматически, как и многие-многие другие которые уже считаются автоматически.

Например, 3360 это попросту 8!/12.

[wrest]

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

Чего тут думать, это же банальные вещи,

Ok, значит наверное допишете когда-нибудь.

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

Всё равно не понял. Ведь и так идёт параллельный счёт разных расстановок, ведь потоков не 1, а 12.

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

[Dmitriy40]

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

[Yadryara]

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

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

А можно цитату? Я разве где-то говорил, что считаю это нормой? Пока это так.

И похоже, что сейчас надо будет перезатачивать программу на поиск D(48,22). И важно не ошибиться, чтоб она считала то что надо, а на многие вещи придётся Пока забить.

[wrest]

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

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

И то и то. Если распилить код на части, то можно сосредоточиться на том, что потребляет больше всего времени. Монолитный код трудно корректировать...

Мне (лично мне) трудно вникать в написанный код. Нет комментариев, неясно что там делается соответственно неясно и как переделать чтобы работало быстрее.
Я вот например заметил, что там многократно переливается из одного вектора в другой - это действительно надо делать?

   Строка  88:   v = bolv;
   Строка 117:     v = bolv;
   Строка 119:     v1 = v;
   Строка 122:         v = v1; 
   Строка 125:         v2 = v;
   Строка 128:             v = v2; 
   Строка 132:             v3 = v;
   Строка 135:                 v = v3; 
   Строка 147:                 v4 = v;
   Строка 150:                   v = v4;

[Dmitriy40]

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

Я вот например заметил, что там многократно переливается из одного вектора в другой - это действительно надо делать?

Так как обсуждаемого кода у меня нет, то могу лишь предположить: да, надо, потому что это не переливание, а разные вектора, в каждом вложенном цикле свой, а v[] просто временный для чего-то, например чтобы код дальше был одинаков в каждом вложенном цикле, а не каждый раз с другим номером вектора (т.е. фактически v[] это просто алиас для другого вектора для удобства). Вектора небольшие, копирование быстрое, если оно вообще физически копируется а не просто добавляется ссылка на тот же кусок памяти (есть технология copy-on-write, когда физически объект копируется лишь при записи в него, а до того используется лишь ссылкой на предыдущий, а в v[] тут наверняка ничего не пишется после v=vXX).
При этом все верхние уровни (кроме 1-2 самых глубоких, и не обязательно этих) на скорость не влияют и потому оптимизировать (пока) излишне, удобство программиста важнее.
И скорее всего все эти вложенные циклы вообще можно совместить в один более сложный, всё равно там глубже ещё должны быть циклы где и делается 99% работы.

-- 16.11.2025, 18:05 --

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

Если распилить код на части, то можно сосредоточиться на том, что потребляет больше всего времени.

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

-- 16.11.2025, 18:10 --

wrest
А проверить где тратится основное время легко: ставите перед любой строкой next и всё ниже до конца текущего цикла выполняться не будет, запускаете и сравниваете время. По идее (как и должно быть) 99% времени должно уходить на самый глубоко вложенный цикл перебора кортежей, в котором вычисляется n по n0 и m и потом куча проверок подходит ли такое n (циклы проверок за уровни вложенности не считаю).