Есть ли что-то быстрее, чем dict()?

Мне нужен более быстрый способ хранения и доступа около 3 ГБ пар k:v. Где k - это string или integer, а v - np.array(), которые могут иметь разные формы. Есть ли какой-либо объект, который быстрее, чем стандартный python dict, для хранения и доступа к такой таблице? Например, a pandas.DataFrame?

Насколько я понял, python dict - довольно быстрая реализация хэш-таблицы, есть ли что-то лучше, чем в моем конкретном случае?

Ответы

Ответ 1

Нет ничего более быстрого, чем словарь для этой задачи, и потому, что сложность его индексации и даже проверки членства примерно равна O (1).

После сохранения ваших товаров в словаре вы можете получить к ним доступ в постоянное время. Тем не менее, проблема заключается не в процессе индексирования. Но вы можете сделать процесс немного быстрее, выполнив некоторые изменения в ваших объектах и ​​их типах. Это может привести к некоторым оптимизации в рамках операций капота. Например, если ваши строки (ключи) не очень большие, вы можете ставить их в очередь, чтобы их обналичивали в памяти, а не создавали как объект. Если ключи в словаре интернированы и ключ поиска интернирован, сопоставление ключей (после хэширования) может быть выполнено с помощью сравнения указателей вместо сравнения строк. Это делает доступ к объекту очень быстрым. Python предоставил intern() в модуле sys, который вы можете использовать для этой цели.

Введите строку в таблицу "интернированных" строк и верните интернированную строку, которая является самой строкой или копией. Интернированные строки полезны для получения небольшой производительности при поиске словарей...

Вот пример:

In [49]: d = {'mystr{}'.format(i): i for i in range(30)}

In [50]: %timeit d['mystr25']
10000000 loops, best of 3: 46.9 ns per loop

In [51]: d = {sys.intern('mystr{}'.format(i)): i for i in range(30)}

In [52]: %timeit d['mystr25']
10000000 loops, best of 3: 38.8 ns per loop

Ответ 2

Нет, я не думаю, что есть что-то быстрее, чем dict. Сложность его проверки индекса - O(1).

-------------------------------------------------------
Operation    |  Average Case  | Amortized Worst Case  |
-------------------------------------------------------
Copy[2]      |    O(n)        |       O(n)            | 
Get Item     |    O(1)        |       O(n)            | 
Set Item[1]  |    O(1)        |       O(n)            | 
Delete Item  |    O(1)        |       O(n)            | 
Iteration[2] |    O(n)        |       O(n)            | 
-------------------------------------------------------

PS https://wiki.python.org/moin/TimeComplexity

Ответ 3

Вы можете думать о сохранении их в структуре данных, например, Trie, если ваш ключ является строкой. Даже для хранения и извлечения из Trie вам требуется O (N), где N - максимальная длина ключа. То же самое происходит с вычислением хэша, который вычисляет хэш для ключа. Хеш используется для поиска и хранения в Hash Table. Мы часто не рассматриваем время хэширования или вычисления.

Вы можете сделать снимок Trie, который должен быть почти равной производительности, может быть немного быстрее (если значение хэша вычисляется по-разному, скажем

HASH[i] = (HASH[i-1] + key[i-1]*256^i % BUCKET_SIZE ) % BUCKET_SIZE

или что-то подобное из-за столкновения, нам нужно использовать 256 ^ i.

Вы можете попытаться сохранить их в Trie и посмотреть, как это работает.