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

Question

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

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

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

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

Answer 1

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

Answer 2

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

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

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

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

Answer 3

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

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

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

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

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

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