Как получить словарный ключ или заданный элемент, равный заданному объекту?

Question

Имея словарь d в Python и объект x, существует ли эффективный способ поиска ключа k в d, равного x?

Аналогичный вопрос можно задать для наборов в Python: для набора s и объекта x существует ли эффективный способ получить элемент e из s, равный x ?

Цель состоит в том, чтобы избежать хранения в памяти дублирующихся неизменяемых объектов.

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

В качестве варианта использования рассмотрите возможность работы с неявным графом, где вершины являются хэшируемыми неизменяемыми структурами данных (возможно, просто кортежами целых чисел). ), которые используются в качестве словарных ключей для хранения некоторых связанных метаданных. Если какая-то вершина генерируется дважды при обходе графа и должна храниться в другом месте, разумно найти уже использованную копию и сохранить ее дважды, а не сохранять новую копию. Более конкретный пример - сохранение памяти в алгоритме A * кратчайшего пути, применяемом для решения 15 задач.

Answer 1

Ваш вопрос тесно связан с понятием изменяемых и неизменных объектов . Точным ответом на ваш вопрос также является спецификация реализации c. Я отвечу за CPython, но имейте в виду, что другие реализации имеют другое поведение.

В CPython после создания (назначения или использования) неизменяемого объекта он создается в памяти. Каждый следующий неизменный объект с тем же значением указывает на тот же объект (!). Вы можете проверить это с помощью функции id (которая в CPython является адресом памяти объекта).

Например:

a = 5  # int's are immutable
d = {5: "five", 8: "eight"}
k = 5

# a and k have the same id; they point to the same object!
print(f"id(a) = {id(a)}") 
print(f"id(k) = {id(k)}")
print(a in d)  # the key a is in dict d
print(d[a])  # the value for key a in dict d

a = (5, )  # tuples are also immutable
d = {(5,): "five", (8,): "eight"}
k = (5, )

# a and k have the same id; they point to the same object!
print(f"id(a) = {id(a)}") 
print(f"id(k) = {id(k)}")
print(a in d)  # the key a is in dict d
print(d[a])  # the value for key a in dict d

Даже если я назначу построенный или вычисляемый неизменный объект переменной, это тот же объект (id), что и другой переменной с тем же значением.

a1 = 3.14
b1 = 'kgvjkdfsjl'
c1 = (63474236728,)
d1 = 1e10
a2 = 3 + 0.14
b2 = 'kgvj' +'kdfsjl'
c2 = (63474236728,)
d2 = 1e9 * 10

print(all([a1 == a2, b1 == b2, c1 == c2, d1 == d2]))  # gives True: the values are all equal
print(all([a1 is a2, b1 is b2, c1 is c2, d1 is d2]))  # gives True: the identities are all equal

Возвращаясь к вашим вопросам:

Есть ли эффективный способ найти ключ в d, равный k?

Вы наделены не надо этого делать. CPython позаботится об этом за вас. То же самое верно для неизменных объектов в наборах.

существует ли общее решение для произвольных неизменяемых хеш-объектов?

Имейте в виду, что неизменяемые объекты также могут иметь значения ha sh! По умолчанию все встроенные неизменяемые объекты имеют хэши, а изменяемые - нет, но пользователи могут определять классы, которые имеют свои собственные функции ha sh. Тем самым создавая изменчивые и переносимые объекты.