Комментарии 60
Вам нужно двигаться в другом направлении не дробить на byte, а упаковывать по несколько малых значений в один int используя какие-то биты для мето-данных.
Разбиваем пространство значений на блоки по 256.
Если в один блок попало больше восьми чисел, то выгоднее представить блок как битовую карту, занимающую 32 байта, вместо 4*количество чисел.
Есть varint, в protocol buffers используется чтобы плотно числа паковать.
— RLE кодирование
— список диапазонов, но тут на сами данные нужно смотреть, подойдет ли.
ЗЫ Да и вообще для такого, сначала статистику нужно собрать, а что там будет храниться.
Про статистику я как раз писал — что всё зависит от данных, поэтому и расписал разные варианты.
В случае когда известно распределение чисел и мы храним данные в байтах, наиболее эффективной кодировкой будет следующий подход:
- Создаём биективное отображение, которое отображает самое частое число в 0, следующее по частоте в 1, и т.д. (можно отображать не отдельные числа, а диапазоны, например, 128 наиболее частых чисел получают индексы 0-127, и т.д.)
- Кодируем полученные индексы используя вариант VLQ использующийся в git-е.
Это если мы заботимся только о плотности хранения. Если же нам важна ещё скорость упаковки/распаковки, то тут уже начинается поиск компромиссов. Например, Group Varint Encoding (вариант VLQ) менее плотен по сравнению с git VLQ, но за счёт меньшего количества ветвлений он быстрее на современных процессорах.
Group varint — вариант для скорости, надо тут тестировать на C#, возможно ли получить преимущество, или невозможность делать некоторые вещи — сожрёт возможную выгоду.
Попробуйте посмотреть, например, в сторону Roaring Bitmaps, или аналогичного. Есть готовые реализации и биндинги ко всем основным языкам, проблема дурки решена тем, что вам этот код поддерживать не нужно. Довольно универсально и шустро работает. Естесственно, зная свои данные, можно изобрести более эффективный велосипедик именно для этих данных, как справедливо отмечает автор статьи.
Но если есть специфика в данных то всегда можно из этой специфики что-то еще вытянуть для пользы компресии. Хотя бы сократить размерность чисел (кстати тоже довольно стандартная задача).
Judy arrays are designed to minimize the number of expensive cache-line fills from RAM, and so the algorithm contains much complex logic to avoid cache misses as often as possible
Judy arrays are extremely complicated. The smallest implementations are thousands of lines of code.[5] In addition, Judy arrays are optimized for machines with 64 byte cache lines, making them essentially unportable without a significant rewrite.
…
hash table performance is strictly superior to Judy for under 10,000 items. Beyond that, hash table performance slows (as mentioned before, presumably due to secondary cacheing effects). Judy on sequential data maintains the same performance regardless of size, and is superior beyond 20,000 entries (on this machine, and tuning the hash table might change this crossover point). However, the hash table is strictly superior on all the random data presented here, generally by a factor of 2.
Эта тема довольно хорошо изучена и начать можно, например, с https://arxiv.org/abs/1401.6399.
Или прямо с кода для C#:
https://github.com/Genbox/CSharpFastPFOR
А ещё можно множества в формулами кодировать или их смещение. Ну или хранить в double после запятой
Если числа в последовательности уникальные и не повторяются, и последовательность в диапазоне от 0 до UINT_MAX. Создадим массив от 0 до UINT_MAX типа Boolean. Обходим всю входящую последовательность. Устанавливаем True элементам массива с тем индексами, значения элементов из последовательности которых получаем. Например, число в последовательности равно 265, значит, элементу массива с индексом 265 ставим True, следующее число в последовательности равно 621, значит элементу массива с индексом 621 ставим True, и так далее. Когда мы пройдём всю последовательность, то у нас в массиве будут отмечены элементы, индексы которых были в последовательности.
Затем мы можем обходить массив и смотреть. Элемент с индексом 0 равен True — значит число 0 было в последовательности. Элемент с индексом 1 равен True — значит число 1 было в последовательности. И так далее.
В этом случае нам понадобится UINT_MAX × SizeOf(Boolean) = 4 294 967 296 × 1 байт = 4 294 967 296 байт памяти. Четыре гигабайта — это меньше, чем 10 гигабайт из вступительной части статьи, но пока ещё много.
Если вместо массива Boolean использовать массив из бит, то достаточно выделить памяти 4 294 967 296 байт / 8 = 536 870 912 байт, это уже 500 мегабайт и возможно, что вполне достаточно. Только нужно будет организовать установку и сбрасывание нужного бита в такой битовой карте.
Алгоритмам сжатия очень нравятся повторения, а тут их не очень много.
Если хранить отсортированный массив разность между отсортированными числами 1,2,3,4,8 => 1,1,1,1,4 => 1,0,0,0,3, то число повторений вырастет. Возможно, значительно (зависит от данных, да-да), что позволит "заархивировать" данные с существенным выигрышем по памяти.
И при создании способов упаковки не надо забывать про накладные расходы по упаковке-распаковке. Сэкономите гигабайт памяти, но программа ваши 10 ГБ будет обрабатывать в десятки раз дольше… Можно, конечно, порекомендовать пользователям купить новый компьютер, но программист тоже должен уметь соблюдать баланс.
Советую ознакомиться с работами Daniel Lemire, Leonid Boytsov, Nathan Kurz и т.д. по данной теме.
Соответственно, недостает сравнения с https://www.roaringbitmap.org/ и https://github.com/lemire/FastPFor.
Без этого плюсануть статью совесть не позволяет.
Daniel Lemire с коллегами занимался этой темой (Integer Compression) более 6 лет. Собрал, наработал и опробовал массу идей, опубликовал около десятка работ и довел до ума несколько реализаций. А в https://github.com/lemire/FastPFor/blob/master/README.md пожалуй лучший набор ссылок по теме, как на научные работы (т.е. идеи с глубокой проработкой и выкладками), так и на реализации (с оптимизацией и т.д.).
С одной стороны, здорово что вы пытаетесь самостоятельно разобраться в теме и что-то придумать. Однако, не стоит делать публикаций без минимального ознакомления с примерно общеизвестной (хотя и в узких кругах) информацией по теме. Уж извините, вовсе не хочу обидеть, но это достаточно вредный дилетантизм.
А потом другие люди начинают по этим статьям делать аналогичные реализации на других языках. Но для них это магия, и получается такой код (пример из C# реализации Roaring Bitmap):
var groupbyHb = values.Distinct().OrderBy(t => t).GroupBy(Util.HighBits).OrderBy(t => t.Key).ToList();При этом, если я буду реализовывать свою задачу (да, я пока не сделал её), я, естественно проанализирую все варианты, и выберу известный и стабильный, если он не особо хуже велосипеда. А если хуже? Использовать его только потому что автор какой-то известный, это я считаю совершенно неправильно.
Пардон, ну так вы для начала просто прочитайте публикации Daniel Lemire по ссылкам.
Причем если Дэниеля внятно спросить что-то beyond RTFM (тем более по-французски), то он очень хорошо отвечает.
Использовать ли алгоритм, только потому что его написал какой-то известный Дядька?
Возьмём Roaring Bitmap — структура, предназначена для эффективной манипуляции со множествами. У меня постановка — хранение. Разные задачи. Будет ли эта структура волшебной и хранить эффективнее? Сомневаюсь.
Мы можем продолжать дискуссию, но я могу взять реализацию на Roaring Bitmap на C#, и первый попавшийся велосипед и сравнить на каких-то данных. Если Roaring Bitmap окажется хуже, вы признаете, что другие решения имеют право на жизнь, или скажете, что я всё неправильно понял, и надо всё равно использовать существующие решения? :) Т.е. стоит мне тратить время на сравнение, или вас не переубедить?
Да, давайте еще раз:
- Есть ряд научных работ (разных ученых/исследователей) по теме сжатия целочисленных последовательностей, в которых собрано и проанализировано немало различных идей/подходов.
- Есть FastPFOR (включая https://github.com/Genbox/CSharpFastPFOR), streamvbyte, TurboPFor и немало других реализаций под разные задачи/требования, где использованы результаты этих научных работ.
- Кроме этого есть и упомянутые Roaring Bitmap (в том числе на C#, на Java и даже на JS).
Соответственно, замечательно что вы пытаетесь самостоятельно разобраться и придумать что-то новое. Однако, без ознакомления с наработанным опытом из первого пункта (совершенно вне зависимости от остальных) результат вашей работы (включая статью) рискует быть излишне дилетантским и наивным.
Нет, совсем не так.
Вне зависимости от ученой степени ваша работа может представлять интерес (не быть дилетантской и наивной), если хотя-бы одно из двух:
- Вы со знанием дела теоретически показываете что предложили новый подход или улучшили уже известный.
- Вы практически (бенчмарком) показываете ценность вашего подхода и/или идеи. Например, можно померятся силами с TurboPFor (там в README достаточно таблиц с результатам различных реализаций).
А пока вы просто не понимаете как смешно выглядите, уж извините за прямоту.
Roaring Bitmaps не совсем то что вам нужно (не считая проблем шарповой реализации). А вот с CSharpFastPFOR померятся вполне уместно. Собственно этого достаточно чтобы соотнести результат вашего VLQ с остальными competitors в score-таблицах у TurboPFor и т.п.
Кроме этого, это поможет вам самим сориентироваться и решить куда двигаться дальше. Ну и конечно было-бы любопытно увидеть статью-продолжение с разбором полетов.
P.S.
На всякий — про качество кода CSharpFastPFOR мне ничего не известно, т.е. там тоже могут быть какие-то перлы.
Итак, 1670118 хешсета, 234965944 суммарное количество интов.
Сохраняем тупо в интовых массивах. 955Мб/981Мб примерно сходится. Некоторые накладные расходы не очень существенны.
Для начала быстро глянул на Roaring Bitmaps
Попробуем CRoaring (это враппер, его нельзя использовать в продакшене, можно получить жёсткую утечку памяти): 67/864 (тут всё ушло в unmanaged память, прироста особо нет).
RoaringBitmap — нативная реализация на C#: 676/712
Да, вы правы, не очень подходит.
Переключаемся на CSharpFastPFOR: 639/954.
Отсортируем массивы: результат аналогичный.
Возьмём разницу между числами (вроде можно для этого алгоритма): 218/360
Тупой VLQ: 749/1041
VLQ с разницей: 307/509
В итоге CSharpFastPFOR с доработками победил. Да я проиграл. Буду ли я использовать CSharpFastPFOR? Его точно нет, его надо переписать полностью. Буду ли я использовать что-то аналогичное (если есть) — не знаю. VLQ пишется за 5 минут и всем понятен, тут — нужна production-ready реализация.
Буду ли играться дальше — а почему бы и нет. :)
Понятно, что в чистом виде не подойдёт, вопрос самого подхода — насколько память сэкономит.
Все обсуждения напомнили мне одну задачу:
Отсортировать миллион 8-мизначных чисел на компьютере с одним мегабайтом памяти
Если списки достаточно плотные от 50% заполнения то самый выгодный вариант будет использовать массив подсчёта. 1 в каждом бите, если элемент есть и 0, если не существует. Как уже писали выше если int значение, то потребуется 500Мбайт накладных расходов, если только положительные числа — в два раза меньше.
Всё что Вы описали выше интересно с академической точки, но сомневаюсь, что в реальном проекте даже 2х-4х кратная экономия по памяти ценой таких накладных расходов оправдана.
В одном проекте где потребовалось подсчитывать все int значения со счётчиком, я просто докупил памяти до 16 гб.
10Гб — не очень много, да. Но, есть другие задачи. Например, та же перестройка с нуля подобных сетов уже займёт ещё 10Гб (например, чтобы не париться с многопоточностью иногда проще пересобрать с нуля, чем править существующие). Я специально не рассказывал про проект, чтобы не отвлекаться, но тут 10Гб, там 10Гб, а потом Out of Memory :)
И при таких объёмах данных разумнее мне кажется разделить множества на подмножества, и обрабатывать их по лимиту оперативной памяти.
Я когда смотрю на современные языки типа Python, которые насилуют память, сверх не эффективно её используя, просто сердце щемит. Однако согласитесь, работает все очень быстро, на типовых задачах.
Меня немного печалит современная тенденция, с другой стороны — я понимаю, время разработчика дорогое, а железо дешёвое. Но ведь всегда можно сделать быстро, а потом улучшать, можно даже в свободное от работы время. Просто потому что это не абстрактный pet project, а реальная задача. Иначе перестаёшь чувствовать себя программистом, а просто каким-то маляром, красящим от забора до обеда.
А вот интересно, что это за задача такая, которая для миллиона множеств с миллионом элементов в каждом требует одновременного присутствия в оперативной памяти их всех сразу?
Хороший пример решения задачи такого рода — исходный код Люсены: ее индекс, собственно, это набор файлов, в котором хранятся числа разных распределений. Соответственно, для каждого типа файлов они придумывают свой собственный кодек, их можно посмотреть, например, здесь.
Мне приходилось решать похожие задачи (хотя, скорее, для оптимизации хранения), я использовал комбинацию уже упоминавшихся тут приемов:
— отсортировать числа
— взять разницу между соседними (если числа разные, можно отнять 1)
— закодировать Varint encoding (7 бит на значение, восьмой бит — флаг последнего байта)
— разделить на куски и каждый кусок сжать deflate-ом (либо lz4, если нужна скорость).
А какие недостатки будут, если завести 256 массивов, и отделить и хранить первый байт из четырёхбайтного числа в качестве индекса массива? Таким образом действительно храня в памяти только 3 байта из 4.
Но обычно на практике чаще применяется дельта-кодирование с последующим сжатием компрессором словарным методом. И если позволяется сортировка чисел, то можно разбить набор на бакеты и к ним применять дельта-кодирование по отдельности. А так как первое число в дельта-кодировании хранится как есть и все числа не превышают первого числа следующего бакета, это позволит понять какой диапазон хранится в данном бакете. Для более быстрого доступа без распаковки всего объёма данных.
То что вы упомянули что числа более случайны и вряд ли повторяются, это можно исправить с помощью BWT преобразования, которое добавит повторяемости даже без потери порядка элементов. Это довольно хитрый алгоритм, который позволяет добавить повторяемости и выявить закономерности для последующего применения словарных методов сжатия.
Если есть значительные промежутки между числами, можно сделать аналогично тому, как хранятся таблицы страниц для защищенного режима процессора.
Для 32 бит адрес делится на 3 части 10+10+12 бит. Для первых 10 бит одна таблица, для вторых 10 бит набор других таблиц, остальное это сама страница размером 4kB. То есть первая таблица разбивает адресное пространство на диапазоны по 4MB. Если в таблице первого уровня в какой-то строке стоит бит 0, то страницы в этом диапазоне точно нет, и таблица второго уровня тоже отсутствует.
Для чисел, в отличие от страниц, надо также хранить сами числа, можно хранить их не целиком, а только последние 12 бит. Например, если у нас всего 2 числа 1 и 232-2, то таблица первого уровня будет выглядеть как
0x123000, NULL, NULL, ..., NULL, NULL, 0x124000
(размером 1024*4 байт, присутствуют элементы из первого и последнего диапазона 4MB, числа в которых начинаются на 0x00?.. и 0xFF?...)
по указанным адресам будут 2 таблицы второго уровня
0x128000, NULL, NULL, ...
NULL, NULL, ..., 0x129000
(числа начинаются на 0x00000… и 0xFFFFF...)
по этим адреса будут 2 таблицы с данными
[1, 0x001] и [1, 0xFFE]
(первый элемент длина, далее 12-битовые числа).
Можно адреса таблиц на биты заменить, но тогда вторые таблицы надо размещать в одном большом массиве и подсчитывать биты в главной таблице, чтобы вычислить смещение.
Как-то так. Для 2 чисел конечно есть оверхед, но для большего количества может быть экономия.
Храним числа экономно