2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу Пред.  1 ... 30, 31, 32, 33, 34, 35, 36 ... 54  След.

А вам пакет PARI/GP интересен?
Да 83%  83%  [ 58 ]
Нет 6%  6%  [ 4 ]
Не уверен(а) 11%  11%  [ 8 ]
Всего голосов : 70
 
 Re: интерактивный курс: введение в программирование на PARI/GP
Сообщение30.10.2022, 12:31 
Заслуженный участник


27/06/08
4062
Волгоград
wrest в сообщении #1568247 писал(а):
По идее, должно идти последовательно и не проверять второе если уже невыполнено первое, но я программистам не доверяю и всегда пишу вложенные if.
Неоднократно проверял. Вложенные if ничуть не быстрее одного if с многими &&

 Профиль  
                  
 
 Re: интерактивный курс: введение в программирование на PARI/GP
Сообщение30.10.2022, 17:10 
Заслуженный участник


20/08/14
11783
Россия, Москва
wrest в сообщении #1568247 писал(а):
По идее, должно идти последовательно и не проверять второе если уже невыполнено первое, но я программистам не доверяю и всегда пишу вложенные if.
И зря, в доке прямо сказано что считается именно ровно слева направо до первого выполненного условия, чтобы можно было применять условия типа if(x!=3 && a/(x-3)>0, ...) или if(j<=#v && v[j]>0, ...). А вложенные if могут быть чуточку медленнее (разбирать отдельный оператор вместо лексемы). Хотя чтобы это заметить ... Сомневаюсь. Зато с длинным условием писанины меньше и логика яснее.
gris в сообщении #1568246 писал(а):
Как считается If c || нескольких условий? Они по очереди проверяются до первого выполнения?
Да, слева направо до первого выполненного, это гарантировано. И для ||, и для && (до первого невыполненного).

-- 30.10.2022, 17:18 --

gris в сообщении #1568246 писал(а):
Это тормозит?
Не знаю что "это". Но обычно тормозит любой добавленный оператор (потому что PARI/GP интерпретатор и каждый раз разбирает код заново). Причём иногда настолько сильно, что оказываются неприменимы стандартные методы оптимизации (типа выноса постоянных вычислений из циклов). Т.е. иногда добавление вроде бы ускоряющего оператора приводит наоборот к замедлению. Я где-то показывал несколько таких примеров. И заранее не угадаешь что пересилит, замедление от лишнего оператора или ускорение от сокращения операций внутри цикла.

 Профиль  
                  
 
 Re: интерактивный курс: введение в программирование на PARI/GP
Сообщение30.10.2022, 20:23 
Заслуженный участник


20/08/14
11783
Россия, Москва
Вот один из примеров, что быстро нашёлся:
Dmitriy40 в сообщении #1540639 писал(а):
Иллюстрация насколько к PARI/GP неприменимы обычные методы оптимизации, в данном случае исключение хвостовой рекурсии:

 Профиль  
                  
 
 Re: интерактивный курс: введение в программирование на PARI/GP
Сообщение31.10.2022, 17:53 
Заслуженный участник
Аватара пользователя


13/08/08
14495
Напугало:
{print(floor(6-30/5));print(floor(6-10*0.6))}
0
-1

 Профиль  
                  
 
 Re: интерактивный курс: введение в программирование на PARI/GP
Сообщение31.10.2022, 18:03 


05/09/16
12067
gris в сообщении #1568451 писал(а):
Напугало:

Ну второе у меня равно -2.350988701644575016 E-38 (количество знаков стоит по умлочанию) если печатать без округления. Целочисленная (и рациональная) арифметика там точная, рациональные числа хранятся в виде несократимой дроби (можно вынуть числитель и знаменатель этой дроби функциями numerator(x) и denominator(x) соответственно). Ну а как только вы ставите десятичную точку, всё становится плавающим, а не точным :) Или если используете иррациональные функции типа синуса или корней. Так что целые, рациональные и вещественные числа - это разные типы там.
Запустите например
print(1/9);print(1/9+0.0)

 Профиль  
                  
 
 Re: интерактивный курс: введение в программирование на PARI/GP
Сообщение31.10.2022, 18:18 
Заслуженный участник


20/08/14
11783
Россия, Москва
gris
Очень далеко не любое дробное десятичное число можно точно представить в формате с плавающей точкой (сколько бы бит там ни было в мантиссе), потому такие числа почти всегда неточные. Хотите точных вычислений - используйте целые или рациональные числа, исключительно. Ещё можно аккуратно округлять дробные числа до целых, но нужно каждый раз внимательно смотреть в какую сторону их округлять в конкретном месте кода, и строго до любых вычислений с ними.

 Профиль  
                  
 
 Re: интерактивный курс: введение в программирование на PARI/GP
Сообщение31.10.2022, 18:23 
Заслуженный участник
Аватара пользователя


13/08/08
14495
Да это неудачная попытка "оптимизации" ограничения для вложенного цикла:
for (k=0, 15*N, for (m=0, floor(3*N-k*3/5),...
А ведь Dmitriy40 предупреждал...
Вовремя опомнился. Буду осторожен.

 Профиль  
                  
 
 Re: интерактивный курс: введение в программирование на PARI/GP
Сообщение03.11.2022, 21:45 
Заслуженный участник
Аватара пользователя


13/08/08
14495
Ещё вопросы, если можно.
Сделал монте-карло по перестановкам элементов вектора $(1,2,3,4,5,6)$. Когда-то делал полный перебор перестановок, но в каких-то скриптах и там всё по-другому. А нет ли в PARI чего-нибудь этакого?
Код:
{S=vector(6);
for ( k=1,200000,
  for ( i=1,6, S[i]=i);
  for ( i=1,5, j=6-random(7-i); D=S[i];S[i]=S[j];S[j]=D);
)}

Нужно ли делать инициализацию массива каждый раз или пусть переставляется? Как делать СВОП элементов массива? $[S[n],S[m]]=[S[m],S[n]]$ почему-то не работало. Ну и вообще, как лучше и просто генерировать перестановку?

+ 22:26
Dmitriy40
wrest
Спасибо! Буду пробовать.
Хотелось скажем генерировать случайные перестановки из большого количества элементов. Я делал последовательными транспозициями всех позиций с начала до конца с последующими. Вроде бы получается равновероятно.

 Профиль  
                  
 
 Re: интерактивный курс: введение в программирование на PARI/GP
Сообщение03.11.2022, 22:05 
Заслуженный участник


20/08/14
11783
Россия, Москва
Есть специальный цикл по всем перестановкам: forperm. Примеры запуска есть в документации к PARI. Ну или вот:
Код:
? forperm([1,2,3],r, print(r); );
Vecsmall([1, 2, 3])
Vecsmall([1, 3, 2])
Vecsmall([2, 1, 3])
Vecsmall([2, 3, 1])
Vecsmall([3, 1, 2])
Vecsmall([3, 2, 1])
?
Но для получения всех перестановок надо непременно указывать массив в возрастающем порядке! Достаточно применить к нему оператор Set() (только он и дубли удалит):
Код:
? forperm([2,3,1],r, print(r); );
Vecsmall([2, 3, 1])
Vecsmall([3, 1, 2])
Vecsmall([3, 2, 1])
? forperm(Set([2,3,1]),r, print(r); );
Vecsmall([1, 2, 3])
Vecsmall([1, 3, 2])
Vecsmall([2, 1, 3])
Vecsmall([2, 3, 1])
Vecsmall([3, 1, 2])
Vecsmall([3, 2, 1])
?

gris в сообщении #1568851 писал(а):
Код:
for ( i=1,6, S[i]=i);
Можно сделать проще и быстрее: S=vector(6,i,i);

gris в сообщении #1568851 писал(а):
$[S[n],S[m]]=[S[m],S[n]]$ почему-то не работало.
Работает:
Код:
? S=[1,2,3,4,5]
[1, 2, 3, 4, 5]
? n=1;m=4;[S[n],S[m]]=[S[m],S[n]]
[4, 1]
? S
[4, 2, 3, 1, 5]
?


-- 03.11.2022, 22:12 --

Кажется я не вполне понял что хотелось ...

 Профиль  
                  
 
 Re: интерактивный курс: введение в программирование на PARI/GP
Сообщение03.11.2022, 22:21 


05/09/16
12067
gris в сообщении #1568851 писал(а):
Ну и вообще, как лучше и просто генерировать перестановку?


numtoperm(n, k)
Generates the k-th permutation (as a row vector of length n) of the numbers 1 to n. The number k is taken modulo n!, i.e. inverse function of permtonum. The numbering used is the standard lexicographic ordering, starting at 0.

-- 03.11.2022, 22:46 --

gris в сообщении #1568851 писал(а):
Хотелось скажем генерировать случайные перестановки из большого количества элементов.

Случайная перестановка из n элементов:
x(n)=numtoperm(n,random(n!))
Но для большого количества (десятки тысяч) элементов может не подойти. Насколько надо большое?

 Профиль  
                  
 
 Re: интерактивный курс: введение в программирование на PARI/GP
Сообщение05.11.2022, 13:22 
Заслуженный участник
Аватара пользователя


13/08/08
14495
Учёл советы при генерации k штук перестановок-беспорядков вектора $(1,2,...,n)$:
{n=22; k=12;
for(ik=1,k,
S=vector(n,i,i);
for(i=1,n-1, j=n-random(n-i); [S[i],S[j]]=[S[j],S[i]]);
print(S);
)}

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

 Профиль  
                  
 
 Re: интерактивный курс: введение в программирование на PARI/GP
Сообщение05.11.2022, 17:38 


05/09/16
12067
gris в сообщении #1568992 писал(а):
Как лучше генерировать беспо перестановки без неподвижных элементов? Размер вектора меньше тысячи.

Мне кажется, что у вас уже все нормально. Спецфункции для генерации случайного беспорядка нет, а значит всё равно нужен цикл по всем элементам.
Единственное, если явно указать что вектор содержит маленькие числа (т.е. 32 битные если ваш pari 32 битный или 64битные если pari 64 битный), это ускоряет перебор:
? n=22;k=1000000;for(ik=1,k,S=Vecsmall(vector(n,i,i));for(i=1,n-1,j=n-i;[S[i],S[j]]=[S[j],S[i]]));
? ##
*** last result computed in 12,964 ms.
? n=22;k=1000000;for(ik=1,k,S=vector(n,i,i);for(i=1,n-1,j=n-i;[S[i],S[j]]=[S[j],S[i]]));
? ##
*** last result computed in 20,915 ms.

Т.е. миллион беспорядков длиной 22 каждый генерируется за 20 секунд, а миллион беспорядков из маленьких чисел за 13 секунд.
Ещё почти две секунды можно выиграть если вынести инициализацию начальной перестановки за внешний цикл:
? n=22;k=1000000;v=Vecsmall(vector(n,i,i));for(ik=1,k,S=v;for(i=1,n-1,j=n-i;[S[i],S[j]]=[S[j],S[i]]));
? ##
*** last result computed in 11,254 ms.

 Профиль  
                  
 
 Re: интерактивный курс: введение в программирование на PARI/GP
Сообщение05.11.2022, 19:43 


05/09/16
12067
gris
Ещё я проверил такой подход. Генерируем случайную перестановку и проверяем является ли она беспорядком, и если нет, то генерируем пока не сгенерируем беспорядок.
Но оказалось, что чтобы сгенерировать $n$ беспорядков надо сгенерировать $ne$ случайных перестановок, и экономия сходит на нет (т.е. получаются те же 11 секунд).

? n=22;k=1000000;for(ik=1,k,until(a,S=numtoperm(n,random(n!));a=1;for(i=1,n,if(S[i]==i,a=0;break))));
? ##
*** last result computed in 10,487 ms.

 Профиль  
                  
 
 Re: интерактивный курс: введение в программирование на PARI/GP
Сообщение05.11.2022, 20:51 


05/09/16
12067
gris в сообщении #1568851 писал(а):
Вроде бы получается равновероятно.

Это кстати вопрос :mrgreen: Вот numtoperm(n,random(n!)) точно даёт случайную перестановку (равновероятно выбирает одну из всех возможных).

 Профиль  
                  
 
 Re: интерактивный курс: введение в программирование на PARI/GP
Сообщение05.11.2022, 21:09 
Заслуженный участник
Аватара пользователя


13/08/08
14495
Попробовал полный перебор по всем 10-значным (без ведущих нулей) натуральным числам с разными цифрами.
{S=Vecsmall(vector(10));D=Vecsmall(vector(10,i,10^(10-i)));kt=0;
forperm([0,1,2,3,4,5,6,7,8,9],S,
if (S[1]!=0,M=0;for(i=1,10,M=M+S[i]*D[i]);kt++;);
);
print(kt);
}
3265920

А как быстро записывать скалярное произведение векторов или ещё как переводить вектор из цифр в число?
Кстати, отметил такую фичу
{S=1;s=2;Ss=3;sS=4; print(S,s,Ss,sS)}
1234

и ещё ошибся с vecsmall. Где критичен регистр букв?
Насчёт (псевдо)случайности потока перестановок задумался.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 810 ]  На страницу Пред.  1 ... 30, 31, 32, 33, 34, 35, 36 ... 54  След.

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group