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

[Yadryara]

Уже сказал, но вот теперь подчеркну:

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

И обнаружил, что прерывание срабатывает, но только один раз. Где-то это надо настроить.

Вот здесь сработало:

2

ТАЙМ-АУТ! (лимит 300000 mks, потрачено 300388 mks)

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

[wrest]

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

Вот здесь сработало:

Вы в этом убедились э... с секундомером в руках, что первый раз в натуре срабатывает?

[Yadryara]

Ну я же уже много раз тестировал, засекая время другим способом через strtime(getwalltime()-t0).

Так что срабатывает. Потому и факторы не показывает. Но потом, после первого срабатывания уже почему-то не срабатывает.

[wrest]

[del]

Yadryara
Промт для Квен:

Цитата:

В чём может быть причина того, что при нескольких вызовах функции gp_safe_factor прерывание по таймеру срабатывает только первый раз, а при последующих вызовах факторизация продолжается сверх лимита времени?

[Yadryara]

wrest
Правильный вопрос Завтра, начиная с трёх ночи по Москве будет очередная сессия.

Мылодав, мылодав... А без мылодава мы уже мыло выдавить не можем

[wrest]

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

Мылодав, мылодав... А без мылодава мы уже мыло выдавить не можем

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

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

[Yadryara]

Ну вот я в последнее время очень сильно зауважал не только wrestа, но и Квена.

Справился он с немалыми трудностями. И я более-менее приблизился к тому чтобы делать то что хотел.

Вот как проверяются две цепочки, 544-я и 557-я, которые дошли до этой проверки:

544.   Лимит 99000 mks

1.  Успел за 25823 mks   27 ms   Факторов найдено: 2   [2447717, 1; 10211591281326496801271995742858327154092969, 1]
2.  ТАЙМ-АУТ! Потрачено 99653 mks   100 ms
6.  ТАЙМ-АУТ! Потрачено 99317 mks   100 ms
7.  ТАЙМ-АУТ! Потрачено 99774 mks   100 ms
10. ТАЙМ-АУТ! Потрачено 99251 mks    99 ms
12. Успел за 54024 mks   86 ms   Факторов найдено: 3   [805196267, 1; 205749007463276909, 1; 43721807138401711635661, 1]
13. Успел за 23459 mks   25 ms   Факторов найдено: 2   [6895337, 1; 41595230661298818460765685654906500949070997, 1]
16. ТАЙМ-АУТ! Потрачено 99561 mks   100 ms
18. ТАЙМ-АУТ! Потрачено 99545 mks   100 ms
20. ТАЙМ-АУТ! Потрачено 99319 mks   100 ms

557.   Лимит 99000 mks

3.  Успел за 59973 mks   89 ms   Факторов найдено: 4   [52245241, 1; 5149633837, 1; 51994261351, 1; 2192933582048978471, 1]
12. Успел за 62842 mks   95 ms   Факторов найдено: 4   [14202821, 1; 1153891699, 1; 23469769787239619, 1; 51038476897282463, 1]
13. Успел за 97849 mks  165 ms   Факторов найдено: 3   [63148997, 1; 39395625389309484307, 1; 30339080272408581253469, 1]
16. Успел за 98852 mks  167 ms   Факторов найдено: 2   [155798789141, 1; 1003169244574137510646322420773664700943, 1]
20. Успел за 65121 mks  100 ms   Факторов найдено: 3   [187026311, 1; 56170216747, 1; 863531798359089875451983295254171, 1]

В подходящих цепочках факторов на этих местах должно быть ровно два. Один быть не может, это проверено ранее.

Видим что для 544-й имеется 10 мест, с числами подходящими для этой проверки. Ну вот он проверяет места под номерами 1, 2, 6, 7, ..., 20 и показывает результат.

И выигрыш во времени должен быть в том, что хоть он и не успевает проверить места 2, 6, 7 и 10, зато 13-е место комп проверить успевает и находит 3 фактора. А это больше двух. Всё. Проверку на этом можно закончить — всю цепочку можно отбросить.

557-я цепочка скучнее, он успевает проверить все 5 её мест. Ну и после проверки первого же места, которое под номером 3, всю цепочку можно отбросить, потому что комп успел найти аж 4 фактора.

И, по идее, её можно отбросить ещё раньше, как только стало понятно, что 3 фактора уже найдены.

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

[wrest]

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

Справился он с немалыми трудностями. И я более-менее приблизился к тому чтобы делать то что хотел.

Поздравляю с первой самостоятельной победой в нелёгком деле кастомизации opensource

Рекомендую ясно (для вас) конспектировать что и как, ведь вы когда-то обновите pari/gp, захотите развернуть на другом компе и т.п.

Ну и если вы доведёте новую функцию "до ума", опишете как её получить и как пользоваться в различных ситуациях (например толлько интерпретатор, или скомпилированный в gp2c скрипт), как она работает если запущено несколько потоков через parfor, или несколько инстансов gp на одном ядре ОС и т.п., то думаю было бы неплохо поделиться с общественностью. Не ровён час, Dmitriy40 и EUgeneUS таки решатся переходит на линукс для pari/gp, а тут такая хорошая функция для отсева цепочек.

В качестве развития темы, предлагаю подумать о следующем.
Для конкретного паттерна, вероятно, существует такое время отсечки, которое максимизирует быстродействие. Сформулируйте критерии оптимальности времени отсечки, ведите в программе статистику и корректируйте время отсечки "на ходу", скажем по первой тысяче цепочек.

[wrest]

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

но и Квена.

Справился он с немалыми трудностями.

Я заметил, что если Qwen начал тупить, то получить результат становится затруднительно. Ну например, Qwen иногда делает вложенные скобки {} или вложенные функции, что не поддерживается в pari/gp. После замечания исправляет, но через три-четыре поста в том же чате забывает и опять делает вложенные скобки.
Тогда надо или начинать новый чат или обращаться к deepseek.

Давеча, для задачи из «Множества и подмножества в PARI» Qwen упёрся в то, что нужна рекурсия и передача переменных между функциями по ссылкам, либо глобальные переменные. Настаивал, что это единственный способ. Пришлось переключиться на DeepSeek, который написал сразу всё инкапсулировано в одной функции, без рекурсий и глобальных переменных. Потом я показал Qwen-у результат работы DeepSeek на что Qwen заявил типа как круто, действительно можно же и так и т.п.

[Yadryara]

Спасибочки.

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

а тут такая хорошая функция для отсева цепочек.

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

Видели мой длинный список фильтраций? Я недавно в очередной раз поразился: если перейти на поиск без простых и в нём выбросить второй пункт и заменить в 3-м пункте фильтрацию по ispseudoprime на фильтрацию по numdiv, то работает в 850 раз медленнее!

А numdiv обычно работает примерно с той же скоростью что и factor.

[Dmitriy40]

wrest
Рекурсивные функции в PARI допустимы.
А в коде той функции рекурсия организована "руками", на stack[], что обычно лишь усложняет и запутывает код (правда и чуточку убыстряет).

[wrest]

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

Рекурсивные функции в PARI допустимы.

Да, но внутри одной пари-шной функции объявить другую функцию и при том рекурсивную - мягко говоря не просто. Не только лишь все умеют это делать. :)
Я это пытался сделать когда хотел чтобы рекурсия использовала мемоизацию, и всё в одной функции, без глобальных переменных. Запускаешь функцию - она создаёт локальную для функции карту, рекурсивно считает, сверяясь с картой, и при выходе карта уничтожается, память освобождается. Пришлось переписываться с разрабами для этого :)

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

А в коде той функции рекурсия организована "руками", на stack[], что обычно лишь усложняет и запутывает код (правда и чуточку убыстряет).

Да, поскольку задание DeepSeek-у сразу было конкретное: сделать одну функцию, а не набор. Такой вот "пунктик" :) А из двух функций Qwen-у написать решение удалось, но переделать его в одну инкапсуляцию уже не удалось.
Ну и Qwen почему-то иногда бывает уверен, что переменные в pari передаются в замыкание (функцию) ссылками а не копиями, из-за чего возникают проблемы.

-- 10.03.2026, 14:32 --

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

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

Странно, вы же писали:

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

Сейчас ситуация такая, что прогресс в такой проверке может стать очень важным, потому что есть хорошая серия с нулевым количеством простых и полупростых. Шаг в 100 с лишним раз меньше.

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

Заметно ускорит, конечно. Особенно для длинных цепочек.

Я это понял так, что ускорение должно быть существенное.

[Yadryara]

Шаг-то я уменьшил в 9800 раз. То есть числа теперь 58-значные, а не 62-значные, как раньше. Но скорость по любому упала в 3-4 раза. И очень похоже, что спуском с гор это замедление не оправдать.

Поэтому была надежда ещё и на идею с ограничением времени. Пока что по примитивным тестам она даёт ускорение всего лишь на 11%. Это если сравнивать порог в 0.15-0.16 секунды с порогом в 1 секунду.

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

Я это понял так, что ускорение должно быть существенное.

Да, я надеялся на большее, хотя бы на 30-процентное ускорение. Данная фильтрация стоит в конце очереди и на общее время влияет слабо. Можно ли её использовать на более ранней стадии? Сомнительно.

Ну и есть ещё куча всяких обстоятельств.

Если бы все мечты сбывались, было б скучновато

[wrest]

Dmitriy40
Я тут подумал, насчёт прерывания по таймеру.
А что, если факторизацию чисел цепочки делать parfor-ом, и прерывать parfor если какое-то факторизовалось не как надо? Тогда, вроде бы, и таймер не нужен. И для венды будет работать. И проверяться будет до конца (в смысле, гарантированный отсев/прохождение). Какое-то одно вредное число или пара застрянут в своих потоках, но зато остальные быстренько пролетят и какое-то прервёт процесс.

-- 10.03.2026, 16:43 --

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

Да, я надеялся на большее, хотя бы на 30-процентное ускорение.

Ну это такое... Бороться стоит за следующий порядок. А это $\log_{10}0,5 \approx 30,1$% ...Шутка
Но да, 30% кажется маловато для борьбы. С другой стороны, найти число не за 100 дней а за 70 круто канеш.

[Yadryara]

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

Бороться стоит за следующий порядок.

Борьба идёт ещё и за скилы. Порой даже в первую очередь за них.

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

Но да, 30% кажется маловато для борьбы. С другой стороны, найти число не за 100 дней а за 70 круто канеш.

Обсуждали уже. С Дмитрием спорили. Моё мнение не изменилось. 70 дней вместо 100 — это ускорение почти на 43%, а не на 30%. А у вас другое мнение или это просто небрежность/пофигизм?