Сжатие список целых чисел в Python

Question

У меня есть список положительных (случайных) целых чисел со следующими свойствами:

Количество элементов: 78495

Максимальное значение элемента: 999982

Длина список при преобразовании в строку: 517115 (строка выглядит как «6,79384,238956 ...»)

Размер списка в текстовом файле на диске: 520 кб

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

Я посмотрел на zlib как способ сжать строку, но, по-видимому, он уменьшил размер пополам.

Есть ли способ действительно уменьшить это, чтобы я мог распаковать его/использовать его в исходном коде?

Answer 1

Учитывая ваше определение ...

это список наименьшего значений к, для которых 10^к = 1 по модулю р для простых р> 5

... я неправильно что ваши значения имеют вид (p - 1)/x где x - целое число, значительно меньшее, чем p?

Например, при р < 50, мы имеем:

p = 7 : 10^6 = 1 (mod 7) => k = 6 = (p - 1)/1 => x = 1 
p = 11 : 10^2 = 1 (mod 11) => k = 2 = (p - 1)/5 => x = 5 
p = 13 : 10^6 = 1 (mod 13) => k = 6 = (p - 1)/2 => x = 2 
p = 17 : 10^16 = 1 (mod 17) => k = 16 = (p - 1)/1 => x = 1 
p = 19 : 10^18 = 1 (mod 19) => k = 18 = (p - 1)/1 => x = 1 
p = 23 : 10^22 = 1 (mod 23) => k = 22 = (p - 1)/1 => x = 1 
p = 29 : 10^28 = 1 (mod 29) => k = 28 = (p - 1)/1 => x = 1 
p = 31 : 10^15 = 1 (mod 31) => k = 15 = (p - 1)/2 => x = 2 
p = 37 : 10^3 = 1 (mod 37) => k = 3 = (p - 1)/12 => x = 12 
p = 41 : 10^5 = 1 (mod 41) => k = 5 = (p - 1)/8 => x = 8 
p = 43 : 10^21 = 1 (mod 43) => k = 21 = (p - 1)/2 => x = 2 
p = 47 : 10^46 = 1 (mod 47) => k = 46 = (p - 1)/1 => x = 1 

Список значений х должны сжать намного лучше, чем список значений к. (Например, я был бы готов поспорить, что наиболее частым значением x будет «1».)

И поскольку довольно просто и быстро вычислить простые числа до 1 миллиона (что я считаю вашим верхним), вы можете быстро перестроить список значений k на основе сжатого списка значений x и вычисленного списка простых чисел в реальном времени.

Вы, наверное, следовало бы объяснить с самого начала, что именно вы пытаетесь сжать, чтобы получить более точные ответы.

Answer 2

Короче говоря, нет.

log(2, 999982) ~= 20 

Таким образом, наибольшее количество займет 20 бит для хранения. Предположим, что в среднем каждый номер занимает 10 бит для хранения (равномерно распределяется между 0 и максимальным).

~80,000 numbers * 10 bits per number = 800,000 bits = 100,000 bytes 

Таким образом, эти цифры, хранящиеся максимально эффективно, занимают ~ 100 КБ пространства.

Сжатие будет работать, только если есть некоторые неслучайные числа. Если они действительно случайны, как вы говорите, тогда общий алгоритм сжатия не сможет сделать это меньше, поэтому 100KB - это лучшее, что вы можете надеяться сделать.

EDIT

Обратите внимание, что все еще хуже, в том, что вы хотите, чтобы вставить их в исходный код, так что вы не можете просто использовать произвольные двоичные данные. Вам понадобится что-то текстовое, например, кодировка base64, что добавит еще ~ 33% накладных расходов. Кроме того, вы не можете хранить номера на основе среднего значения количества бит, потому что вам нужно каким-то образом узнать, сколько бит было использовано каждым отдельным номером. Возможны схемы кодирования, но все они будут нести дополнительные дополнительные накладные расходы.

ВТОРОЙ EDIT

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

Answer 3

Доступный best text compression предлагает (приблизительно) коэффициент сжатия 12-17% (62,4-90 кБ), чтобы вы не соответствовали своему порогу. Ваши данные также случайны, что в целом делает алгоритмы сжатия хуже.

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