интерактивный курс: введение в программирование на PARI/GP

[gris]

пробую создать множество всех множеств
Ну начать с множества векторов.
v1=vector(3,i,1);v2=vector(3,j,2); s=Set(v1);print(s);
[1]
Не получается сет даже из одного вектора
Задача такая: есть векторы одной длины
(двадцать-сорок) из небольших натуральных чисел, меньших 999, возрастающие.
[4,6,36,454,333]
Векторов немного, миллион-два.
Надо выкинуть повторяющиеся векторы и отсортировать.
Я сейчас кодирую каждый вектор так:
1 004006036454333 (первая единичка всегда для выравнивания).
Загоняю это дело в Set и при надобности раскодирую обратно. А не проще ли было делать вектор из векторов или даже множество векторов?

[Dmitriy40]

gris
Зачем такие сложности? Засуньте все свои векторы в новый вектор и скормите его Set-у, он выделит только уникальные вектора:

? Set([ [1,2,3], [2,3], [3,4,5], [1,2,4], [1,2,3], [4,5], [2,3] ])
%1 = [[2, 3], [4, 5], [1, 2, 3], [1, 2, 4], [3, 4, 5]]

[gris]

Dmitriy40 спасибо, получилось:
{s=Set();
for(i=1,12,
s=setunion(s,Set([vector(3,j,4*j+random(2))]))
); print(s)}

[[4, 8, 12], [4, 8, 13], [5, 8, 12],
[5, 8, 13], [5, 9, 12], [5, 9, 13]]

не знал, что Set из векторов надо записывать с квадратными скобками. Set([v1,v2,v4])
Кстати, а setunion тоже медленно работает, как concat ?

[Dmitriy40]

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

? Set([ [1,2,3], [3,2,1] ])
%1 = [[1, 2, 3], [3, 2, 1]]
? Set([ Set([1,2,3]), Set([3,2,1]) ])
%2 = [[1, 2, 3]]
? Set([ "123", 123 ])
%3 = [123, "123"]

gris в сообщении #1623441 писал(а):

Кстати, а setunion тоже медленно работает, как concat ?

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

-- 22.12.2023, 16:40 --

Ещё способ преобразовать вектор в множество (отсортировать и удалить дубликаты): v=vecsort(v,,8) - сортировка с удалением дубликатов, аналог Set. Сортировка может быть и быстрее если там использованы продвинутые алгоритмы (не в курсе). Плюс сортировку можно сделать косвенной (выдающей список не элементов, а их индексов), что для сложных объектов тоже может быть быстрее (а обрабатывать их потом не столь существенно, прямо или косвенно).

[gris]

Это я помню. Поэтому у меня векторы строго возрастающие. Для них равенство как векторы и как множества равносильны.
А вот насчёт удаления дубликатов: через множества не так муторно, как помещение всех векторов в один вектор, его сортировка и просмотр с удалением.
Наверное, есть в библиотеках, но как сегодня сказали, проще самому написать несложную программку, чем её разыскивать и прилаживать
++ Ой, уже вы написали. Ну значит я в правильном направлении думаю! Только вчера использовал vecsort(v,,4)

(Оффтоп)

А кстати вот как:
Надо было не только удалить дубликаты, но и отсортировать их по количеству дубликатов. Вот я и при кодировании вектора впереди вместо единички подставлял количество дубликатов (увеличенное на 10). А потом ещё раз сортировал. Ну это уж оффтопик.
Увлёкся

[gris]

Интересны средства PARI/GP с точки зрения простоты кода, а не эффективности на огромных числах и размерах векторов.
Имеем случайный вектор с небольшими натуральными числами. Надо отсортировать элементы по количеству повторений.
Получилось как-то занудно. Как покороче?

{v=vector(12,i,random(4)+1); print(v);
v=vecsort(v); print(v);
vmk=[];
n=v[1];
k=1;
km=1;
for( i=1,#v-1,
  if( n==v[i+1],k++
  , vmk=concat(vmk,1000*k+n); km++; k=1; n=v[i+1]);
);
vmk=concat(vmk,1000*k+n);

vmk=vecsort(vmk,,4);
for( i=1,#vmk, printf("%d: %d times\n", vmk[i]%1000,vmk[i]\1000));
}

[2, 1, 1, 2, 3, 1, 2, 4, 4, 2, 2, 2]
[1, 1, 1, 2, 2, 2, 2, 2, 2, 3, 4, 4]
2: 6 times
1: 3 times
4: 2 times
3: 1 times

[Dmitriy40]

? v=[2, 1, 1, 2, 3, 1, 2, 4, 4, 2, 2, 2];
? s=vecsort(v, , 8)
%2 = [1, 2, 3, 4] -- только уникальные элементы
? k=vector(#s,n, #select(x->x==s[n],v))
%3 = [3, 6, 1, 2] -- по сколько штук их каждого
? q=vecsort(k, , 5)
%4 = Vecsmall([2, 1, 4, 3]) -- вектор перестановок по уменьшению количества повторов
? s=vecextract(s, q)
%5 = [2, 1, 4, 3] -- переставляем список уникальных элементов
? k=vecextract(k, q)
%6 = [6, 3, 2, 1] -- переставляем количество их повторов
? for(i=1,#s, print(s[i],": ",k[i]," times"); ); \\вывод
2: 6 times
1: 3 times
4: 2 times
3: 1 times

Переставлять векторы s,k не обязательно, можно просто идти по векторам в порядке q:

? v=[2, 1, 1, 2, 3, 1, 2, 4, 4, 2, 2, 2];
? s=vecsort(v, , 8)
%2 = [1, 2, 3, 4] -- только уникальные элементы
? k=vector(#s,n, #select(x->x==s[n],v))
%3 = [3, 6, 1, 2] -- по сколько штук их каждого
? q=vecsort(k, , 5)
%4 = Vecsmall([2, 1, 4, 3]) -- вектор перестановок по уменьшению количества повторов
? foreach(Vec(q),i, print(s[i],": ",k[i]," times"); ); \\вывод, foreach кажется не гарантирует перебор в порядке увеличения, зато удобно и на практике работает
2: 6 times
1: 3 times
4: 2 times
3: 1 times

При этом никакие вектора не портятся, все остаются в исходном состоянии. Если дальше сортировка по количеству повторов не используется, то вектор q можно не сохранять и переставить его вычисление прямо в foreach.
Вместо for и foreach можно использовать и vector (но вектор q придётся сохранять) (гарантирует ли vector перебор в порядке увеличения индекса я не в курсе):

? vector(#q,i, print(s[q[i]],": ",k[q[i]]," times")) \\косвенное обращение
2: 6 times
1: 3 times
4: 2 times
3: 1 times
%1 = [0, 0, 0, 0] -- здесь критично отсутствие символа ; после vector, а нули вернул каждый print

Ещё способ перебора без сохранения q (и наверное тоже без гарантии порядка):

? apply(i->print(s[i],": ",k[i]," times"), Vec(q)) \\i перебирается по содержимому q
2: 6 times
1: 3 times
4: 2 times
3: 1 times
%1 = [0, 0, 0, 0] -- здесь критично отсутствие символа ; после apply, а нули вернул каждый print

[gris]

Dmitriy40, спасибо. Не угомонюсь никак.
Есть простой в изготовлении поток миллиарда натуральных чисел t. Хочется посчитать сколько чисел делится на заданные делители. Задаю делители в векторе f, в векторе kf считаю случаи.
Как-то громоздко и долго И правильно ли?

{f=[1000,29,31,37,41,43,47,53,59,61,67,71]; lf=#f;
kf=vector(lf);
for( j=1,1 000 000,
    t=random(10000)+13;
    vd=divisors(t);
    for( fi=1,lf,
        if( vecsearch(vd,f[fi])>0,kf[fi]++ ); 
    );
); 
printf("%d numbers were tested for sick divisors\n",1000000);
printf(" %5d\n", f);printf(" %5d\n", kf); 
}

1000000 numbers were tested for sick divisors
 [ 1000,   29,   31,   37,   41,   43,   47,   53,   59,   61,   67,   71]
 [  980,34510,32345,27065,24410,23524,21161,18754,16860,16390,14985,14055]
time = 4,914 ms.

[wrest]

gris в сообщении #1625852 писал(а):

И правильно ли?

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

[gris]

wrest, величина чисел ожидается порядка 1E14.
Попробовал сравнить по времени

...  if( vecsearch(vd,f[fi])>0,kf[fi]++ );...

1 000 000 numbers were tested for sick divisors
 [    37,    41,    43,    47,    53,    59,    61,    67,    71,    73]
 [ 27029, 24044, 23387, 21248, 18652, 16929, 16482, 14950, 14237, 13799]
time = 1min, 54,302 ms.

и

... if( t%f[fi]==0,kf[fi]++ );  ...

1000000 numbers were tested for sick divisors
 [    37,    41,    43,    47,    53,    59,    61,    67,    71,    73]
 [ 27202, 24185, 23414, 21146, 18799, 17179, 16285, 14975, 14198, 13658]
time = 2,685 ms.

Во как... Спасибо!
У меня были соображения, что числа на самделе не случайные, а делителей у них меньше 37 вообще нет, а меньше 100 меньше двух. Но да, все делители искать излишне.

[wrest]

gris в сообщении #1625870 писал(а):

... if( t%f[fi]==0,kf[fi]++ ); ...

Небольшой лайфхак. Если переписать это как
if( t%f[fi],,kf[fi]++ );
То будет непонятнее, но процентов на 10-15 быстрее.

[gris]

Проверка .
time = 1,873 ms. = 70% ( time = 2,685 ms.)
Замечательный лайфхак!
Про две запятых я понимаю Это else А вдруг нет

[wrest]

gris в сообщении #1625879 писал(а):

Это else А вдруг нет

Да, это он. If воспринимает ноль как ложь, не ноль как истину.

[Dmitriy40]

gris
Возможно Вам не нужно знать на все ли делители делится число, а достаточно лишь первого обнаруженного делителя, тогда в пару к kf[fi]++ стоит поставить next(2).
И тогда стоит упорядочить f[] по возрастанию, больше чисел будет отбраковываться раньше.
Больше ничего полезного не придумывается, взятие остатка уже достаточно быстрое.

PS. Проверять время в несколько секунд не слишком надёжно/точно, слишком много случайного шума, лучше секунд в 20-60.

[gris]

Dmitriy40, учту.
Никак не мог быстро находить максимальный простой делитель не очень больших чисел. Слепил:

m=5624; 
forstep( j=m,1,-1, 
   if( m%j==0 && ispseudoprime(j), d=j;break) 
); 
print(m," ",d);
5624 37

Нет ли прямой функции?
И ещё: не грешно ли изменять внутри цикла переменную цикла? Например, вместо break или next(3)?