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

[wrest]

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

Убедился, что 41 строка повторяется. Это успокоило

А откуда берется файл с $3 \cdot 10^6$ строками?
Вообще, сдаётся мне, что линуксовые манипуляторы строками справились бы быстрее 35 секунд, но это не точно. У вас есть код, который генерерует этот файл?

[gris]

Сама программа написана на PARI/GP и примитивна. С помощью nextprime непрерывно набирается круговой вектор длиной 15. Если разница между первым и последним элементом становится равной 228, для вектора подсчитываются многочисленные характеристики. В том числе паттерн, который представляет собой возрастающий от 0 до 228 вектор из 15 элементов с чётными числами.
В выходной файл записывается строка с паттерном. Либо в виде вектора, а для экономии места паттерн кодируется просто числом.
Например,[0,6,24,26, ... ,224,228] кодируется числом 3012013...112114. Это одноразовый эксперимент давший ожидаемый результат. Обнаружение повторов было ошибкой при склеивании разных файлов с небольшими наложениями. При аккуратном формировании файла в 5 млн строк повторов не было обнаружено.
Проблема в том, что при количестве строк в файле 5 млн, даже просто mapput(nf,nn,0); вызывает нехватку памяти при максимальном default(parisizemax,10^9). Но дело в том, что трудность не в обработке даже столь длинного файла, а в его получении. При старте отбора 1Е28 на одну строку в среднем уходит 1 мин .
<Боюсь, что это сообщение чересчур офтопично >

[Dmitriy40]

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

даже просто mapput(nf,nn,0); вызывает нехватку памяти при максимальном default(parisizemax,10^9).

Как я недавно говорил, это ограничение на mapput не влияет.

[wrest]

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

Проблема в том, что при количестве строк в файле 5 млн, даже просто mapput(nf,nn,0); вызывает нехватку памяти при максимальном default(parisizemax,10^9).

Ок, $5 \cdot 10^6$ строк по $15\cdot 3 =45$ символов(цифр) это $2,25 \cdot 10^8$ цифр. Ну с накладными расходами, допустим $3 \cdot 10^8$ и до $10^9$ вроде хороший запас. Значит, накладные расходы больше или дублируется что-то. Так-то в один байт влезает две цифры, а в случае строки только одна, если это конечно строки ascii, utf-8 но не utf-16. Но, видимо, преобразование строк в числа потребляет и память и время.
Итого, если задача именно искать повторы, то преобразовывать [уже имеющиеся в виде файла в файловой системе] строки в числа может оказаться плохой идеей.

[Dmitriy40]

Если стоит задача только обнаружить небольшое количество повторяющихся чисел, то можно обойтись и без сортировки, но за два прохода по исходному массиву. Придумываем хеш-функцию (например остаток от деления на простое втрое большее количества чисел), проходим по массиву и увеличиваем число встреч числа с данным значением хеш-функции в отдельном массиве размера множества значений хеш-функции, при повторном проходе в Map добавляем только те элементы, которые встретились более одного раза, их будет лишь немногим больше реального количества повторяющихся строк (из-за коллизий хеш-функции).
Массив количества повторов можно попробовать объявить как vectorsmall, под gp32 его элементы всего по 4 байта.
Размер можно брать и менее чем втрое больше, даже и менее количества исходных чисел, но тогда растёт количество коллизий.

-- 02.05.2024, 15:23 --

По поводу накладных расходов в Map под gp32:

? m=Map(); mapput(m,x="123456789012345678901234567890123456789012345",0); mapput(m,eval(x)+4,0); mapput(m,1,0);
? foreach(m,x, print(x[1][1],": bytes=",sizebyte(x)); );
123456789012345678901234567890123456789012349: bytes=76
123456789012345678901234567890123456789012345: bytes=100
1: bytes=60
? sizebyte(m)
%1 = 264

Т.е. длинное число заняло 76 байтов (не само число, а элемент Map), строка с таким же числом заняла 100 байтов, короткое число занимает 60 байтов, накладные расходы на саму Map составили 264-100-76-60=28 байтов. Так что преобразование строки в число позволяет засунуть в Map в 100/76=1.3 раза больше элементов.

[gris]

Спасибо за советы и замечания. Суматошность конца апреля не способствовала внимательному и безошибочному применению новых для меня средств обработки больших(?) массивов данных, поэтому я займусь их подробным изучением.
Вопрос: Нельзя ли в forvec применять переменные вектора? Типа
forvec( s=[[1,222],[i1,224],[i2,226]], ...)
То есть изящно сделать
for( i1=1,222, for( i2=i1+1,224, for( i3=(i2+1,226, ... )))

[wrest]

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

Т.е. длинное число заняло 76 байтов (не само число, а элемент Map), строка с таким же числом заняла 100 байтов, короткое число занимает 60 байтов,

У меня так (андроид, т.е. линукс 64бит)
? m=Map(); mapput(m,x="123456789012345678901234567890123456789012345",0); mapput(m,eval(x)+4,0); mapput(m,1,0);
? foreach(m,x, print(x[1][1],": bytes=",sizebyte(x)); );
123456789012345678901234567890123456789012349: bytes=136
123456789012345678901234567890123456789012345: bytes=152
1: bytes=120
? sizebyte(m)
%3 = 464
?

Но при этом!
? sizebyte("123456789012345678901234567890123456789012345")
%4 = 56
? sizebyte(eval("123456789012345678901234567890123456789012345")+4)
%5 = 48
?
-- 02.05.2024, 17:26 --

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

для меня средств обработки больших(?) массивов данных,

Ну я бы сказал не "больших" массивов, а "длинных"

[gris]

Вот пример
v=vector( 5000000,i,random(10^22)*10^22+random(10^22) );
print(#v," / ", #Set(v));
*** Set: Warning: increasing stack size to 512000000.
5000000 / 5000000
time = 13,448 ms.

nf=Map();
for( i=1, 5000000, mapput(nf,random(10^22)*10^22+random(10^22),0) );
print(#nf);
5000000
time = 37,893 ms.

nf=Map();
for( i=1, 10000000, mapput(nf,random(10^22)*10^22+random(10^22),0) );
print(#nf);
}
*** at top-level: ...f=Map();for(i=1,10000000,mapput(nf,random(10^2
*** ^---------------------
*** mapput: not enough memory
windows-7 32bit

[wrest]

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

Вот пример

Так надо было вектор удалить, он же в памяти сидит. Или это запуски "с чистого листа"?

-- 02.05.2024, 17:51 --

Dmitriy40
По поводу управления размером стека - таки да. При его макс. размере в 2 гигабайта, карта на 5 млн 45-значных чисел отъела 7 гигабайт
По 144 байта на элемент.

[gris]

Возможно, я не перезапустил PARI/GP
Но вот вылезло другое
nf=Map();
for( i=1, 10000000, mapput(nf,random(10^22)*10^22+random(10^22),0) );
print(#nf);

*** at top-level: ...f=Map();for(i=1,10000000,mapput(nf,random(10^2
*** ^---------------------
*** mapput: overflow in lg().

[wrest]

gris
А запустите так:
nf=Map();
for( i=1, 1000000, mapput(nf,random(10^22)*10^22+random(10^22),0) );
print(bytesize(nf));

[gris]

A function with that name existed in GP-1.39.15. Please update your script.
New syntax: bytesize(x) ===> sizebyte(x)
sizebyte(x): number of bytes occupied by the complete tree of the object x.
перезапустил
nf=Map();
for( i=1, 10000000, mapput(nf,random(10^22)*10^22+random(10^22),0) );
print(sizebyte(nf));

*** at top-level: ...f=Map();for(i=1,10000000,mapput(nf,random(10^2
*** ^---------------------
*** mapput: not enough memory
может быть надо оставить только PARI? Там ещё огнелис сидит... А всего 4Г

[wrest]

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

может быть надо оставить только PARI? Там ещё огнелис сидит... А всего 4Г

Ну у вас раньше памяти на 5 млн. записей хватало, а тут на один не хватило...

Короче. Проверил гипотезу как быстрее искать дубликаты. Я записал в файл 10 млн. строк. Ушло 30 секунд и получился текстовый файл gris.txt размером 450 мегабайт:
pari/gp:
? for( i=1, 10000000, write("gris.txt",random(10^22)*10^22+random(10^22)));
? ##
*** last result computed in 28,788 ms.
?
Линукс (bash):
~ $ ls -l gris.txt
-rw------- 1 u0_a530 u0_a530 448887307 May 2 18:15 gris.txt
То есть как и положено для строк - 45 байт на 44-значное число (плюс перевод каретки).

Затем линуксовой командой sort сортирую и командой uniq делаю поиск дубликатов строк:
~ $ time(sort gris.txt | uniq -D)

real 0m7.446s
user 0m27.059s
sys 0m1.864s
~ $
Поиск занимает 7,5 секунд, дубликатов строк не найдено.
Семь секунд! Вместе с чтением файла, его сортировкой и поиском дубликатов...
Ну правда работало оно, видимо, многопоточно...

[gris]

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

[Dmitriy40]

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

карта на 5 млн 45-значных чисел отъела 7 гигабайт
По 144 байта на элемент.

Заметьте что 144*5e6=720e6, в 10 раз меньше 7ГБ!