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

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

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

источник

2016-11-19 alec_djinn

Если вы используете Python 3.5 или ниже, то [словарь встроенный в Python 3.6, как говорят, на 20-25% быстрее, чем старый словарь в Python встроенных команд 3.5] (HTTP: //stackoverflow.com/questions/39980323/dictionaries-are-implemented-as-ordered-in-cpython-3-6).Таким образом, вы можете получить более высокую производительность, используя последнюю стабильную версию Python. –

Если ваш код ничего не сделает, я был бы очень удивлен, если бы ваш словарь был узким местом. У вас есть профилирующая информация, показывающая, что это проблема? – DSM

Я думаю, что дикт довольно быстро. Вместо того, чтобы находить альтернативу, вы рассматриваете возможность оптимизации остальной части вашего кода :) –

Нет ничего более быстрого, чем словарь для этой задачи, и это связано с тем, что сложность его индексации и даже проверки членства примерно равна 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

источник

2016-11-19 15:30:59 Kasramvd

Хотя я думаю, что OP движется в неправильном направлении, производительность примерно больше, чем большая-O. – DSM

Это трюк, который я искал! Это ускорило мой код на несколько процентов. Благодаря! –

Хороший ответ, но я думаю, что пример был бы более ясным, если бы значения были интернированными строками тоже, а не целыми числами (но это работает, я думаю, потому что целые числа интернированы внутри этого диапазона в качестве детали реализации). –

-3

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

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

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

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

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

источник

2016-11-19 15:42:24

Первое предложение является своего рода вводящим в заблуждение. В нотации Big-O речь идет не о скорости в целом, а о том, как изменяется время вычисления при изменении размера ввода. Таким образом, O (1) может быть очень медленным, а также O (n!). – ForceBru

true, но это не значит, что он будет _fast_ или _faster_, чем O (что-либо) или даже самый быстрый из всех возможных. Речь идет о том, как изменяется объем работы при изменении размера ввода. – ForceBru

... то есть: в реальном мире важны постоянные факторы. Процесс O (1), который принимает 1000 мс постоянным временем, часто будет худшим выбором, чем процесс O (n), который принимает 1 нс на элемент ввода. –

нет, я не думаю, что есть что-то быстрее, чем 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

источник

2017-11-29 06:47:43

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

ответ

Смежные вопросы