Как алгоритмы поиска в словаре Python работают внутри?
mydi['foo']
Если словарь содержит 1 000 000 терминов, выполняется ли поиск дерева? Ожидаю ли я производительность с точки зрения длины ключевой строки или размера словаря? Может быть, набивка всего в словарь так же хороша, как запись индекса поиска дерева для строк размером 5 миллионов?
Здесь некоторый псевдокод ближе к тому, что на самом деле происходит. Представьте, что словарь имеет атрибут data, содержащий пары ключей, значений и size, которые являются количеством выделенных ячеек.
def lookup(d, key):
perturb = j = hash(key)
while True:
cell = d.data[j % d.size]
if cell.key is EMPTY:
raise IndexError
if cell.key is not DELETED and (cell.key is key or cell.key == key):
return cell.value
j = (5 * j) + 1 + perturb
perturb >>= PERTURB
Значение perturb гарантирует, что все бит хеш-кода в конечном итоге будут использоваться при разрешении хэш-столкновений, но после того, как он ухудшится до 0, (5*j)+1 в конечном итоге коснется всех ячеек в таблице.
size всегда намного больше, чем количество реально используемых ячеек, поэтому хеш гарантированно попадет в пустую ячейку, когда ключ не существует (и обычно должен ударяться довольно быстро). Также имеется удаленное значение для ключа, указывающего ячейку, которая не должна прерывать поиск, но который в настоящее время не используется.
Что касается вашего вопроса о длине ключевой строки, хеширование строки будет рассматривать все символы в строке, но в строке также есть поле, используемое для хранения вычисленного хэша. Поэтому, если вы каждый раз используете разные строки для выполнения поиска, длина строки может иметь подшипник, но если у вас есть фиксированный набор ключей и повторное использование одних и тех же строк, хэш не будет пересчитываться после первого использования, Python получает выгоду от этого, так как большинство поисков имен включают словари, и одна копия каждой переменной или имени атрибута хранится внутри, поэтому каждый раз, когда вы получаете доступ к атрибуту x.y, есть поиск словаря, но не вызов хеш-функции.
Как вы упомянули в своем названии, dicts - это хэш-таблицы. Поиск дерева не используется. Поиск ключа - это почти постоянная операция времени, независимо от размера dict.
Вы можете найти ответы на этот вопрос полезными: Как внедрены встроенные словари Python
Вот хорошее объяснение: http://wiki.python.org/moin/DictionaryKeys
Псевдокод из ссылки выше:
def lookup(d, key):
'''dictionary lookup is done in three steps:
1. A hash value of the key is computed using a hash function.
2. The hash value addresses a location in d.data which is
supposed to be an array of "buckets" or "collision lists"
which contain the (key,value) pairs.
3. The collision list addressed by the hash value is searched
sequentially until a pair is found with pair[0] == key. The
return value of the lookup is then pair[1].
'''
h = hash(key) # step 1
cl = d.data[h] # step 2
for pair in cl: # step 3
if key == pair[0]:
return pair[1]
else:
raise KeyError, "Key %s not found." % key
В поиске хэша не используются деревья. Они используют хеш-таблицу, и они постоянно ищут время. Они занимают больше места (в среднем, я считаю, вдвое больше), чем дерево, но время поиска и вставки выигрывают.
Чтобы упростить, возьмите md5 вашего ключа и измените это с количеством адресов, которые у вас есть, и тем, где вы сохраняете или хотите получить ключ. Неважно, насколько велика установка, она всегда будет занимать такое же количество времени, пока у вас не будет значительного столкновения, что позволит избежать хорошего хеша.
Ответ 1: Внутренняя работа объясняется в этом video
Ответ 2: Нет, поиск по дереву не выполняется, если у вас есть миллион записей в словаре.
Ответ 3: поскольку могут быть ключевые коллизии, вы ожидаете производительность с точки зрения размера словаря, а не по длине ключевой строки.
Ответ 4. Рассмотрим словарь как массив (смежные ячейки памяти), но в массиве могут быть блоки, которые не используются. Следовательно, словари склонны тратить много места на память по сравнению с деревьями. Но для лучшего времени исполнения словари могут быть лучше деревьев. Ключевые столкновения могут когда-то ухудшить производительность. Вы должны прочитать о Consistent Hashing.