структура данных для сжатия в стиле RLE

позволяет говорить, что у меня есть цифры от 1-10 миллионов (идентификаторы клиентов). каждое отдельное число связано с 1 из 3 возможных значений - A, B, C.структура данных для сжатия в стиле RLE

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

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

Кроме того, есть ли реализация java интервала-дерева, которое было предложено в ответе.

источник

2010-02-17 Andreas Petersson

После того, как в какие операции структура данных вы хотите выполнить над данными? –

для числа X Я хочу знать, является ли это частью A или B или C. –

Вы можете попробовать LinkedListMultimap из Google Collections с некоторой сложной логикой.

Что такое сложная логика: каждое нечетное значение представляет начало интервала, и каждое четное значение представляет конец интервала.

Например, у вас есть 1001-1100 идентификаторы в A, 1101-1300 в B и 1301-1400 снова в

multimap.put (A, 1001); 
multimap.put (A, 1100); 

multimap.put (B, 1101); 
multimap.put (B, 1300); 

multimap.put (A, 1301); 
multimap.put (A, 1400);

источник

2010-02-17 14:30:27 Roman

Создать 3 деревьев интервальных или отсортированный карту (начало, конец) пар , каждый из которых представляет категории A, B и C.

источник

2010-02-17 14:53:08 kennytm

Но интервалы не перекрываются. Также будет работать двоичное дерево. –

Начните с того, что вы переставляете структуру данных, используя ti вместо сохранения сопоставления клиентов -> категории (A/B/C), сохраните сопоставление категорий -> клиентов. Я обнаружил, что транспонирование является обычным и классным методом для разработки очень эффективных структур данных.

Теперь используйте 3 растровых изображения (битмаски, биты, такие как java.util.BitSet) для каждой из таблиц 3 A, B, C. В i-м бите таблицы A будет указано, является ли номер клиента «i» в категории A.

Каждая из этих таблиц займет всего N/8 байт памяти, что составляет всего 3,75 МБ, учитывая ваших 10-миллионных клиентов.

(обратите внимание, что это будет работать, только если идентификатор клиента являются последовательными целыми числами)

источник

2010-02-21 14:47:49 jkff

, в то время как это не учитывает секвенциальное выравнивание, оно очень эффективно. я попробую это. 3.7mb не слишком много памяти в моем случае. однако фактическая структура памяти каждого из битов выглядит очень избыточной. 0000000000000000000111111111111111111110000000000 также может быть сжат до 20x0.20x1,10x0 как-то. или, может быть, реализация битового набора, закодированная хаффманом? –

Вы можете сжимать биты так или иначе, возможно, даже с gzip, но затем вы теряете чрезвычайно эффективный доступ к чтению/записи произвольного доступа. В целом, лучшее решение зависит от того, как вы собираетесь получить доступ к структуре данных. – jkff

О, кстати, вам не нужны 3-битные маски для A, B и C. Вам нужно только сохранить A и B, потому что C выходит автоматически как ~ (A || B). – jkff

структура данных для сжатия в стиле RLE

ответ

Смежные вопросы