моя первая публикация здесь, поэтому надеюсь, что я задал свой вопрос правильным образом,
После добавления элемента в словарь Python можно ли заставить Python сказать, добавляет ли этот элемент столкновение? (И сколько мест исследовали стратегию разрешения столкновений, прежде чем найти место для размещения элемента?)
Моя проблема: я использую словари как часть более крупного проекта, и после обширного профилирования я обнаружил, что самая медленная часть кода имеет дело с редкой матрицей расстояний, реализованной с использованием словарей.
Ключами, которые я использую, являются идентификаторы объектов Python, которые являются уникальными целыми числами, поэтому я знаю, что они все хешируют для разных значений. Но включение их в словарь все равно может вызвать столкновение в принципе. Я не верю, что словарные коллизии - это то, что замедляет мою программу, но я хочу исключить их из моих запросов.
Итак, например, с учетом следующего словаря:
d = {}
for i in xrange(15000):
d[random.randint(15000000, 18000000)] = 0
Вы можете заставить Python рассказать вам, сколько конфликтов произошло при его создании?
Мой фактический код запутан с приложением, но приведенный выше код делает словарь, который очень похож на те, которые я использую.
Повторяю: я не думаю, что столкновение - это то, что замедляет мой код, я просто хочу исключить эту возможность, показывая, что у моих словарей не много конфликтов.
Спасибо за вашу помощь.
Изменить: Некоторый код для реализации решения @Winston Ewert:
n = 1500
global collision_count
collision_count = 0
class Foo():
def __eq__(self, other):
global collision_count
collision_count += 1
return id(self) == id(other)
def __hash__(self):
#return id(self) # @John Machin: yes, I know!
return 1
objects = [Foo() for i in xrange(n)]
d = {}
for o in objects:
d[o] = 1
print collision_count
Обратите внимание, что когда вы определяете __eq__
в классе, Python дает вам TypeError: unhashable instance
, если вы также не определяете функцию __hash__
.
Он работает не так, как я ожидал. Если у вас есть функция __hash__
return 1
, то вы получите массу коллизий, как ожидалось (1125560 коллизий для n = 1500 в моей системе). Но с return id(self)
существует 0 столкновений.
Кто-нибудь знает, почему это говорит о столкновении?
Edit: Возможно, я понял это.
Это потому, что __eq__
вызывается только в том случае, если значения __hash__
для двух объектов одинаковы, а не для их "хрусткой версии" (как выразился @John Machin)?