Структура данных с эффективным использованием памяти для набора целочисленных кортежей

Question

У меня вычислительная проблема, связанная с огромным количеством целочисленных кортежей, которые я должен хранить в наборе. Более подробно, настройка:

• Есть положительное целое число n (<= 10) и много целочисленных кортежей длины <code>n;
• У меня есть огромный набор X таких кортежей, который строится за много шагов;
• На каждом шаге я часто проверяю, входит ли какой-нибудь кортеж t в X; если нет, такие кортежи добавляются к X в конце каждой итерации;
• Затем мне нужно перебирать элементы X, чтобы выполнить некоторые другие вычисления.

До сих пор я использовал Python встроенный set класс, и это было нормально. Размер X содержал до 5 миллионов записей, а это занимало около 3–3,5 ГБ памяти (набор X вместе с некоторыми дополнительными данными). Я столкнулся с необходимостью масштабировать это до 30–50 миллионов записей (или более), поэтому я ищу для этого более эффективную с точки зрения памяти структуру данных.

Требования к этой структуре данных, таким образом, следующие :

• Каждая запись появляется только один раз;
• Быстрая проверка членства и быстрая вставка;
• Итерация по всем записям не слишком сложна.

Очевидным кандидатом на такую ​​структуру данных является Tr ie, но реализации, которые я видел, не совсем соответствуют моим потребностям. Лучшим вариантом кажется PrefixSet из pygtrie (по крайней мере, лучше документировано). Но, как показывает следующий короткий тест, на самом деле он занимает как минимум в 2–5 раз больше места.

from pygtrie import PrefixSet
from random import randint
from pympler import asizeof

t = PrefixSet()
s = set()

for i in range(100000):
    x = tuple(randint(0, 15) for _ in range(10))
    t.add(x)
    s.add(x)

print('|s|={} |t|={}'.format(asizeof.asizeof(s), asizeof.asizeof(t)))

Дает

|s|=16995032 |t|=75835376

Таким образом, очевидно, что он не использует преимущества особенности входных данных (ну, а почему это должен быть класс общего назначения).

Вопрос: какая структура данных типа набора данных наиболее эффективна для памяти для хранения целочисленных кортежей фиксированной длины? Какие из таких структур данных уже реализованы в Python?

Answer 1

Если вы хотите оптимизировать использование памяти, вам придется использовать шаблоны в ваших данных. Если распределение значений в ваших кортежах не является действительно случайным, должны быть некоторые из 10 позиций, которые имеют меньше различных значений, чем другие. Это то, что древовидное хранилище может использовать для уменьшения использования памяти.

Например, для 1 миллиона кортежей, если первый элемент в кортежах имеет только значения 3, 5 и 9 во всех кортежах, сохраняя 9 элементов кортежи суффиксов в словаре из 3 наборов должны сохранять пространство, эквивалентное 999997 целым числам (теоретически):

{
   3: set(of all 9-tuples that should be prefixed by 3)
   5: set(of all 9-tuples that should be prefixed by 3)
   9: set(of all 9-tuples that should be prefixed by 3) 
}

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

{
   (3,7): set(of all 8-tuples that should be prefixed by (3,7) )
   (3,1): set(of all 8-tuples that should be prefixed by (3,1) )
   (3,4): set(of all 8-tuples that should be prefixed by (3,4) )
   (5,4): set(of all 8-tuples that should be prefixed by (5,4) )
   ...
}

Конечно, наименее различающиеся элементы могут не быть первыми, поэтому вам может потребоваться некое сопоставление, чтобы изменить порядок позиций в этом словаре.

Проблема с тестированием этого вида оптимизации хранилища на случайно сгенерированных данных состоит в том, что сама случайность элементов сводит на нет цель иерархического хранилища и бросает его в худшем случае. Даже если у вас есть какая-то комбинация позиций, которая уменьшает количество различных значений, все равно придется уменьшить счетчик размера префикса на большее пространство, чем добавленные накладные расходы иерархической структуры (мои тесты показывают, что наборы очень эффективны при хранении кортежи небольших целых чисел, поэтому их будет сложно превзойти)

Короче говоря, если вы знаете, что ваши данные имеют некоторые шаблоны распределения, которые позволят вам выбрать хороший уровень группировки, вы сможете извлечь выгоду из Tr ie или PrefixSet, сопоставляя позиции с их структурой (а также не давая им управлять целыми кортежами). В противном случае будет очень сложно добиться сколько-нибудь значимой экономии памяти.