У меня есть особые потребности, и наиболее важными проблемами являются:
- в памяти
- очень низкий объем памяти
- скорость
Вот моя "проблема": мне нужно хранить в памяти огромное количество очень разреженных битовых массивов. Эти наборы битов предназначены только для добавления и должны использоваться в основном для пересечений. Под огромными я подразумеваю массивы до 200 000 бит.
Диапазон должен быть между [0...16 000 000] для каждого набора битов.
Я провел предварительный тест с «только» 10 673-битными массивами, содержащими некоторые фактические данные, которые у меня есть, и получил следующие результаты:
1% of the bit arrays ( 106 bit arrays) Hamming weight: at most 1 bit set
5% of the bit arrays ( 534 bit arrays) Hamming weight: at most 4 bits set
10% of the bit arrays ( 1068 bit arrays) Hamming weight: at most 8 bits set
15% of the bit arrays ( 1603 bit arrays) Hamming weight: at most 12 bits set
20% of the bit arrays ( 2137 bit arrays) Hamming weight: at most 17 bits set
25% of the bit arrays ( 2671 bit arrays) Hamming weight: at most 22 bits set
30% of the bit arrays ( 3206 bit arrays) Hamming weight: at most 28 bits set
35% of the bit arrays ( 3740 bit arrays) Hamming weight: at most 35 bits set
40% of the bit arrays ( 4274 bit arrays) Hamming weight: at most 44 bits set
45% of the bit arrays ( 4809 bit arrays) Hamming weight: at most 55 bits set
50% of the bit arrays ( 5343 bit arrays) Hamming weight: at most 67 bits set
55% of the bit arrays ( 5877 bit arrays) Hamming weight: at most 83 bits set
60% of the bit arrays ( 6412 bit arrays) Hamming weight: at most 103 bits set
65% of the bit arrays ( 6946 bit arrays) Hamming weight: at most 128 bits set
70% of the bit arrays ( 7480 bit arrays) Hamming weight: at most 161 bits set
75% of the bit arrays ( 8015 bit arrays) Hamming weight: at most 206 bits set
80% of the bit arrays ( 8549 bit arrays) Hamming weight: at most 275 bits set
85% of the bit arrays ( 9083 bit arrays) Hamming weight: at most 395 bits set
90% of the bit arrays ( 9618 bit arrays) Hamming weight: at most 640 bits set
95% of the bit arrays (10152 bit arrays) Hamming weight: at most 1453 bits set
96% of the bit arrays (10259 bit arrays) Hamming weight: at most 1843 bits set
97% of the bit arrays (10366 bit arrays) Hamming weight: at most 2601 bits set
98% of the bit arrays (10473 bit arrays) Hamming weight: at most 3544 bits set
99% of the bit arrays (10580 bit arrays) Hamming weight: at most 4992 bits set
100% of the bit arrays (10687 bit arrays) Hamming weight: at most 53153 bits set
Увидев вовлеченные числа, мне, очевидно, нужно использовать сжатые битовые массивы, и это не проблема: должно быть легко иметь дело с тем, что битовые массивы «только добавляются».
Биты битового массива, которые включены, немного сгруппированы, но не полностью. Таким образом, вы, как правило, имеете несколько включенных битов в одной и той же области (но обычно не один за другим, что делает RLE не очень хорошим для включенных битов).
У меня вопрос, какое сжатие использовать?
Теперь я не знаю, должен ли я поставить свой первый подход здесь или в ответ на мой собственный вопрос.
По сути, я представил сценарий «наихудшего случая», используя очень тупую кодировку:
1 бит: если включено, следующие 5 бит определяют, сколько бит необходимо для вычисления «пропуска», если выключено, оптимизация: следующие 5 бит определяют, сколько битов следует понимать буквально (то есть «включено» или «выключено»). ', без пропуска) [это будет переключено только в том случае, если будет определено, что оно более эффективно, чем другое представление, поэтому, когда оно срабатывает, это всегда будет оптимизация (по размеру)]
5 бит: сколько битов мы можем пропустить перед включением следующего бита.
х бит: пропустить
Вот пример: в битовом массиве установлено 3 бита, первый бит равен 3 098 137, второй — 3 098 141, а третий — 3 098 143.
+-- now we won't skip
|
| +-- 3 because we need 3 bits to store "6" (from 3 098 138 to 3 098 143)
| | +--- 3 098 141 is on
22 3 098 137 | 3 | +- 3 098 143 is on
1 10110 1011110100011000011001 0 00011 000101 etc.
Первый бит говорит о том, что мы собираемся пропустить биты. 5 следующих битов (всегда 5) говорят, сколько битов нам нужно, чтобы сказать, сколько битов мы пропустим 22 бита, говорящих о переходе к 3 098 137 один бит говорит о том, что мы не пропускаем биты 5 следующих битов (всегда 5) говорят сколько бит мы будем читать "как есть" 6 бит: выкл, выкл, выкл, вкл, выкл, вкл значит 3 098 141 и 3 098 143 включены и т.д.
Увидев удивительную разреженность этих битовых массивов, это кажется довольно эффективным по размеру.
Поэтому, используя эту кодировку, я взял свои образцы данных и вычислил сценарий «наихудшего случая» (я еще не написал алгоритм, я бы предпочел сначала несколько входных данных отсюда): в основном я считал, что не только «размер Оптимизация» никогда не сработает, а также то, что 5 бит всегда будут установлены на максимальное значение (24 бита), чего, конечно, не может быть.
Я сделал это только для того, чтобы получить очень грубое представление о том, каким может быть «худший из худших» случаев.
Был очень приятно удивлен:
Worst case scenario:
108 913 290 bits needed for the 10 687 very sparse bit arrays
12.9 MB (13 295 KB)
Поскольку данные являются фактическими данными, и все данные аналогичны, я знаю, что в худшем случае я мог бы хранить свои 200 000-битные массивы примерно в 240 МБ, и это нормально.
Я почти уверен, что фактическое кодирование будет намного меньше, чем это, но, поскольку я еще не написал его, я могу (очень легко) вычислить только «худший случай», поэтому я показываю только его.
Любые подсказки/идеи о том, как сделать это более эффективным по размеру (помня о том, что это сверхразреженные битовые массивы, что их должно быть сотни тысяч, что они должны быть в памяти и что они должны быть «только добавленными») ?
О моем случае "только добавление"
По сути, у меня есть один растущий "пространство" (диапазон, но "пространство" — это фактический термин, как я его понимаю) и множество битовых массивов, которые имеют несколько наборов бит. Когда диапазон изменяется, скажем, от 0 до 1 000 000, все битовые массивы идут от 0 до 1 000 000. Когда диапазон вырастает до 1 000 001, то растут и все битовые массивы, все на один бит. Но к большинству этих битовых массивов в конце добавляется «0», а от 4 до 8 битовых массивов в конец добавляется «1». Однако я не могу заранее предсказать, к какому из битовых массивов будет добавлен 0 или 1.
Итак, у меня есть много битовых массивов одинакового размера, которые очень разрежены (‹ 0,5% их битов) и все они «растут» по мере роста диапазона (поэтому они все всегда растут). по той же ставке).
массивы Джуди великолепны. Но я читал о них несколько лет назад, и это было «выше головы». Массивы Judy - это библиотека 20KLOC только для C, и я определенно не буду ее повторно реализовывать. Но они потрясающие.
Итак, я думаю, мне нужно добавить, что я хотел бы, чтобы все это оставалось относительно простым, что не так уж и надуманно, если увидеть специальное свойство «только добавление» моих очень разреженных битовых массивов.
