Comments 56
Вопрос про оценку эффективности сжатия. Сначала вам удалось достичь примерно такого же, как в случае 7-zip, примерно восьмикратного сжатия с использованием разностей без использования их структуры. Потом, поиграв с пилообразными закономерностями в распределении разностей, вы обошли 7-zip почти в полтора раза, добившись более чем 11-кратного сжатия, но этот результат 7-zip смог ужать на 5%. То есть выходит, что если 7-zip может поджать, есть что поджимать, но если не может, то это ничего не значит.
Можно ли оценить эффективность сжатия от предельно возможного, как-то сравнивая результат сжатия с распределением случайной величины, с белым шумом? (Насколько я понимаю с дилетантских позиций, случайная величина несжимаема).
Может, там до идеально возможного остается несколько процентов, которые труда не стоят, а может оказаться, что еще есть куда стремиться, хотя неясно, как.
Иными словами, вы в конце публикации попробовали как-то улучшить результат еще, но явного успеха уже не получается.
А можно ли просто оценить, насколько он вообще может быть улучшен в принципе?
Однако помимо статистических распределений бывают знания (эвристики) о структуре сжимаемых данных, на них наложить математических ограничений не получится, это, по сути, предел предсказательной возможности модели кодировщика (в пределе решением является алгоритм генерации последовательности по её номеру, см. «Архиватор Бабушкина» :))
Другое дело что автор хотел получать числа быстрее чем генерируя их каждый раз, так что мы пытаемся найти баланс между размером файла и скоростью доступа. Для такого баланса теоретических формул не бывает.
В байте 7 бит отдаются под информацию, а 8-й бит говорит, надо ли читать еще 1 байт, чтобы получить текущее значение. Таким образом, при хранении разрядность не ограничена в принципе, а место равно количеству байт, необходимых, чтобы разложить все значущие биты по 7. Также, плюс, что не требуются словари, и состояние алгоритма максимально простое.
Интересная статья, но не помешало бы объяснения, зачем это всё нужно.
Кодирование целым числом битов хорошо подходит, если вероятности разных чисел в последовательности равны степеням двойки. Здесь может лучше подойти арифметическое кодирование или другие подобные методы.
У меня такое чувство. что половина из отметившихся в комментариях не уловила, суть идеи в строго детерминированном характере частотности интервалов. Традиционное же кодирование исходит из некоторых общих представлений о данных. Поскольку частотность интервалов детерминирована, нет никаких проблем рассчитать эффективность любого другого метода кодирования, на последней диаграмме я несколько таких примеров привел. Есть предложение? Посчитайте сами. Итоги в студию.
Но. Но к чему такая сложность? Для простых чисел, если это небольшие числа, то есть если это не всякие порядка 2^256, а как здесь меньше 2^40 вполне годится тупое хренение битовой маски. Есть правда одна «хитрость», но это хитрость достаточно очевидна.
Давай посчитаем. Пусть у нас есть простые до 10е12. Для хранения прямо вот просто битовой маски достаточно 1,25е11 бит. Это сразу же 116 ГиБ. Заметим также, что если взять произведение нескольких простых чисел, то простые числа могут попадать не на все, а только на некоторые остатки от деления на это произведение (кроме самых первых):
2 — только остаток 1
2*3=6 — только остатки 1 и 5
2*3*5=30 — только 1, 7, 11, 13, 17, 19, 23, 29 (8 чисел)
Для 2*3*5*7=210 можно тоже вручную посчитать, даже для 2*3*5*7*11=2310 можно маску сохранить. Дальше выигрыш совершенно несущественный.
В решете Эратосфена эту оптимизацию часто называют wheel optimization. Мы можем хранить не все биты, а только попадающие в остатки. То есть для «колеса» в 30 не все 30 бит, а только 8. Это даёт нам сразу менее 32 ГиБ
Раскодировать такое хранение на несколько порядков проще. Ну и кодировать прямо скажем — не занудно.
Для цикла 210 получается 48 значений остатков, т.е. хранить можно 48 бит из 210, это уже 26,6 ГиБ.
Для цикла 2310 получается 480 допустимых значений, это уже 24,19 ГиБ. И это уже лучше вашего результата :)
Ещё замечание (извиняюсь за спам).
Простые числа до 2^32 считаются сейчас вовсе не часы, а секунды или даже доли секунды. Это не отменяет того, что дальше считать всё сложнее и сложнее, но до 2^40 просеять не проблема.
Если эта тема интересует, есть primesieve.org, это опенсорсный проект на гитхабе. Там все разъяснения есть.
Триллион чисел генерируются за чуть больше двух минут на обычном ноутбуке (i7-7500U), что сравнимо со скоростью считывания 24ГБ данных с диска:
$ ./primesieve 1000000000000
Sieve size = 256 kilobytes
Threads = 4
100%
Primes: 37607912018
Seconds: 147.634
2*3=6 — только остатки 1 и 5
Хочу заметить, что поэтому и появляются промежутки 2 и 4. На следующем шаге убираются числа, кратные 5, и появляются промежутки длиной 6. Потом кратные 7, и добавляются возможные промежутки 8, 10. И т.д.
Насколько я понял, там выявлена закономерность между параллельными рядами простых чисел. А раз есть формула — возможно, удастся повысить сжатие. Удачи!
надо чуть больше 4 гигабайт.
Вы ошибаетесь 1 триллион это 10^12, для 10^12/30 нужно 33_333_333_334 байт, то есть более 33 миллиардов байт. Это примерно 31,044 ГиБ (если поделить на 1024 три раза). Как раз это я и предложил выше.
А вот по номеру так искать конечно не получится.
Поиск по номеру можно легко оптимизировать, сохраняя промежуточные Pi(N) — количество простых чисел не превосходящих данное. Сохранять например одно число на 256 КиБ, то есть на 256102430=7864320 чисел. Это удобно, потому что потребует хранения всего 127157 чисел, а 256 килобайт — отлично ложится в L2 кэш процессора и посчитать биты тм достаточно просто.
И асимптотически такой метод проиграет кодированию интервалов.
Асимптотический проигрыш этой схемы хранения кодированию интервалов совсем не очевиден. На больших значениях интервалы будут расти, а значит будут требовать всё больших значений. При этом "плотность" заполнения битовой маски падает вместе с упомянутым Pi(N), который близок к n/ln(n). То есть очень медленно.
Для флага достаточно одного бита, плюс пропускаются четные — итого для 32-битных чисел сжатие в 64 раза. Реализация тривиальная, очень быстрый доступ по значению числа, но относительно медленный по номеру в последовательности простых.
среди нечетных 999999999989/2 (делим на 2 т.к. четные исключаем) сжимается арифметическим кодированием до 24578934869 байт = 22.89 Гб. Если кодировать арифметическим интервалы между простыми можно выиграть еще.
Вопрос. Вот мы всячески наизголялись над массивом. А какие методы верификации результата у нас есть? Ну, проверить, что числа, которые получаем, простые — можно. А как проверить что ничего не пропустили?
Вообще-то таблицы так и строят — берут все числа по очереди. Как тут пропустить что-то можно?
Отдельные вещи можно проверить у альтернативных источников. Например, последнее простое в использованной мной таблице 999999999989, имеет порядковый номер 37607912018, здесь primes.utm.edu/nthprime этому можно получить подтверждение. Значит, во всяком случае пропусков нет. А вот проверить на предмет перестановок и подмен — тут увы. Только поэлементное сравнение с такой же таблицей, либо поштучная проверка на простоту. Собственно, этим-то простые и замечательны, что другого способа нет.
Сильное уменьшение таблицы может дать использование быстрого вероятностного теста на простоту и хранение тех чисел на которых этот тест "врёт" что оно простое. Например такого:
def fast_test(n):
for p in [997, 32416190071]:
if pow(p, n-1, n) != 1:
return False
return TrueМожно подобрать таких свидетелей простоты (вместо 997 и 32416190071) для которых тест не ошибается если входные числа лежат в заданных пределах.
Вот тест посложнее, должен не врать до 1 трлн. Под pypy3 тестирует около 3 млн чисел в секунду.
def miller_rabin(n):
if n == 2:
return True
if n % 2 == 0:
return False
A = [2, 13, 23, 1662803]
if n in A:
return True
r, s = 0, n - 1
while s % 2 == 0:
r += 1
s //= 2
for a in A:
x = pow(a, s, n)
if x == 1 or x == n - 1:
continue
for _ in range(r - 1):
x = pow(x, 2, n)
if x == n - 1:
break
else:
return False
return TrueОн должен уменьшиться. Идея в том, чтобы бежать по числам (как сказали выше, можно рассматривать каждое 4-е число если работать в 30-ричной системе счисления) и проверять каждое из них каким-то быстрым тестом на простоту. Этот тест может давать ложноположительные срабатывания, но чисел на которых он это делает должно быть не так много и их можно сохранить отдельно.
Кроме того, можно строить таблицу на лету, например, с помощью решета эратосфена, что на хорошем компьютере быстрее, чем считать её с диска.
Построение на лету хорошо для разовых задач, но усложнение программирования ставит под вопрос выполнимость самих таких задач. Прикладные задачи потребуют дополнить построение на лету кэшированием и сложность программирования возрастет в разы.
Те простые числа, для которых быстрый тест на простоту не врёт, можно не включать в таблицу. 3/4 можно исключить, если рассматривать числа в 30-ричной системе и проверять только те, которые заканчиваются цифрами "1", "7", "11", "13", "17", "19", "23", "29".
Чтобы код не усложнялся, можно использовать готовую библиотеку для поиска простых чисел, например primesieve, https://primesieve.org/api/namespaceprimesieve.html. Тогда сложность уйдёт в библиотеку. Кеширование можно реализовать через внешний класс для каждого блока, например, по 10 000 тысяч чисел, что позволит значительно уменьшить потребление памяти программой, насколько я понял, примерно на 23ГБ для первого 1трлн простых. Хотя, таблица будет быстрее при случайном доступе к простым.
7z a primes.7z -m0=Delta:4 -m1=LZMA:d19 primes1m.4
Разница на первом миллионе 32 битных простых в три раза (785827 против 258063)
У Вас есть частотность интервалов, дальше их закодировать Хаффманом. Ну и делать отсечки каждые N элементов для более простой расшифровки.
Вроде должен давать теоретический минимум в хранении.
Компрессия больших массивов простых чисел