Используйте копию изменяемых объектов как ключи словаря

Question

Насколько я знаю, python требует, чтобы объект был неизменным, чтобы использоваться в качестве словарных ключей. Например, мы не можем использовать list в качестве словарных ключей, и мы должны сначала преобразовать их в tuple. Так что было не так с копией изменяемых объектов и вместо этого использовать копию. Таким образом, изменение объекта не влияет на ключ. Это потому, что этот подход неэффективен в пространстве или что-то еще?

Answer 1

dict s не принимает измененные объекты, делая глубокую копию по нескольким причинам, каждая из которых является индивидуально достаточной. Среди этих причин:

1) Это сделало бы накладные расходы на ввод сколь угодно высоким.

2) Это сделает непредвиденные накладные расходы.

3) Это сломает O (1) поиск.

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

Рассмотрим, в вашей гипотетической версии Python, эта программа:

d = { [1,2,3]:"hello" } 
for k in d: 
    k.append(4) 

Мы изменяем скопированный ключ объект Dict. Очевидно, что хэш должен быть пересчитан, и, очевидно, должна быть пересчитана хэш-таблица d. Но когда?Или, чтобы антропоморфизировать, как d знает, что k сам изменил? Ответ: практически, он не может.

Нет, если мы хотим найти O (1), нам нужна хеш-таблица. Если нам нужна хеш-таблица, нам нужны постоянные хэш-значения ключей. Если нам нужны постоянные хеш-значения ключей, нам нужны неизменные объекты.

И наоборот, если мы хотим изменить ключи, мы можем реализовать поиск O (logN). Но поскольку Python требует O (1) поиска, у нас есть неизменные ключи.

Answer 2

Я думаю, что пример поможет тоу понять:

my_value = 123456 
my_string = 'key' 

my_dict = {my_string : my_value} 

my_string = 'not key anymore!' 

print my_dict['key'] #prints : 123456 
print my_dict[my_string] # raise KeyError 

Как вы можете видеть, что ключ может все еще быть refenced после того, как «оригинал» объект был изменен. Но я сказал «оригинал», потому что объект не был действительно изменен, но был создан новый объект. В этом смысл неизменяемости. вы можете прочитать об этом: https://docs.python.org/2/reference/datamodel.html

Если ключ был изменен, то значение ключа было бы изменено, когда я сам изменил сам объект.

Answer 3

Потому что Python не любит делать слишком много под капотом. Когда вы добавляете элемент (ключ, значение) в dict, ключ в словарной строке и значение: ссылок оригинальным объектам.

Даже если ключ был копией исходного объекта, вы все равно можете получить ссылку на него, итерации items. И как только вы получите эту ссылку, вы сможете изменить ее со всеми проблемами ...

Таким образом, для метода копирования потребуется, чтобы dict не только копировал ключ при добавлении элемента, но и последовательно возвращает новую копию в методах keys() или items().

И последнее, но не в последнюю очередь, так как есть изменяемые и не являющиеся изменяемые классы, вы можете создать письменный Copyable классы в Python:

>>> class UnCopy(object): 
    def __new__(cls, x, y): 
     obj = super(UnCopy, cls).__new__(cls) 
     obj.x = x 
     obj.y = y 
     return obj 


>>> c = UnCopy('a', 'b') 
>>> d = copy.deepcopy(c) 

Traceback (most recent call last): 
    File "<pyshell#20>", line 1, in <module> 
    d = copy.deepcopy(c) 
    File "C:\Python27\lib\copy.py", line 190, in deepcopy 
    y = _reconstruct(x, rv, 1, memo) 
    File "C:\Python27\lib\copy.py", line 329, in _reconstruct 
    y = callable(*args) 
    File "C:\Python27\lib\copy_reg.py", line 93, in __newobj__ 
    return cls.__new__(cls, *args) 
TypeError: __new__() takes exactly 3 arguments (1 given) 

Во всяком случае, единственная реальная причина: это не так, как dict класс ведет себя, а не делает другие классы сопоставления из модуля collection.