Список-список против хеш-хэшей

Question

Настройка: мне нужно хранить векторы объектов, связанные с парами строка-строка. Пары строка-строка кодируют отношение ввода-вывода. Там будет относительно небольшое количество входов X (например, 5), и для каждого входа xбудет сравнительно небольшое количество выходов Y|x (например, 10).

Вопрос в том, какая структура данных самая быстрая?

Дополнительная актуальная информация:

1. Выходы обычно различны для каждого входа, и нельзя предполагать, что каждый X имеет одинаковое количество выходов.
2. Поиск будет выполняться "много раз" (возможно, 1000).
3. Входы будут дискретизированы одинаково часто, но для каждого входа, как правило, один или два выхода будут доступны часто, а остальные будут доступны нечасто или вообще не будут.

В настоящее время я рассматриваю три варианта:

1. list-of-lists: доступ к внешнему списку с индексом (представляющим ввод X[i]), доступ к внутреннему списку с индексом (представляющим выходные данные) Y[i][j]).
2. hash-of-hashes: такой же, как указано выше.
3. плоский хэш: key = (input,output),

Answer 1

Если у вас есть строки, неясно, как вы будете искать индекс, чтобы эффективно использовать список списков без использования хеширования. Если вы можете передать что-то, что хранит ссылку на индекс (например, если набор выходных данных является фиксированным, и вы можете определить их перечисление), то вместо строки список списков будет быстрее (при условии, что вы имеете в виду список в смысл "не обязательно связанный список" с доступом к элементу O(1)). В противном случае вы можете просто хэшировать напрямую и сэкономить свои усилия.

Если нет, то это оставляет хэш хешей v. Плоский хеш. Каков ваш шаблон доступа? Вы всегда будете запрашивать X,Y или вам когда-нибудь понадобится доступ ко всем выходам для X? Хеш (X+Y), скорее всего, примерно эквивалентен хешу (X) + хеш (Y) (оба собираются, как правило, обходить все буквы, чтобы сгенерировать хеш. Таким образом, отдельные хеши являются более гибкими, с небольшими (почти наверняка незначительными)) Начиная с 3, похоже, вам может понадобиться хэш хэшей.