Блог

У меня есть dict из некоторого хэш-ключа в битовую строку. Битовая строка может иметь переменную длину, но обычно она составляет < 160 бит и обычно <80. У меня около 80 миллионов пар ключ-значение.

Как я могу сохранить эту структуру данных в как можно меньшем объеме памяти? Я не хочу заполнять битовые строки, иначе я потеряю совсем немного места (без каламбура).

Я предполагаю, что мне придется сохранить байт в начале, указывающий длину битовой строки. Все в порядке.

Какой наиболее экономичный способ сохранить этот dict в памяти?

Я бы предпочел использовать Python, но открыт для других вариантов.

Если вы имеете в виду заполнение битовых строк до целого числа байт, то вы могли бы сохранить конкатенацию всех начальных битовых строк в одной битовой строке и сохранить словарь, значениями которого являются кортежи вида (bit position, length) .

Проблема в том, что если я правильно рассчитал, то длина этой более крупной битовой строки может превышать 12 миллиардов бит, поэтому bit position потребуется пара бит над int . Затем, если вам нужно заполнить саму позицию бита, мы возвращаемся к исходной точке.

Однако, если количество различных длин < 64, вы могли бы уместить поле длины в 6 бит, и в итоге вы получите словарь, сопоставляющий хэш-ключи с 5-байтовыми кортежами, индексируемыми в единственную битовую строку. Сработает ли это для вас?