如何获取字典键或等于给定对象的 set 元素?

How to get the dictionary key or the set element that is equal to a given object?

提问人:Alexey 提问时间:1/12/2020 最后编辑:Alexey 更新时间:1/12/2020 访问量:68

问:

给定 Python 中的字典和一个对象,有没有一种有效的方法来查找等于的键?dxkdx

关于Python中的集合,可以提出一个类似的问题:给定一个集合和一个对象,有没有一种有效的方法来获得其等于的元素?sxesx

目的是避免在内存中保留重复的不可变对象。

如果所讨论的键和元素是字符串,那么,我想,可以通过实习(sys.intern)找到一些解决方法,但是对于任意不可变的可哈希对象,是否有通用的解决方案?

作为用例,请考虑使用隐式图,其中顶点是可哈希的不可变数据结构(可能只是整数的元组),它们用作字典键以保留一些关联的元数据。如果某个顶点在图遍历中生成了两次,并且需要存储在其他地方,那么查找已经使用的副本并存储两次是合理的,而不是存储新的副本。一个更具体的例子是用于解决 15 个难题的 A* 最短路径算法中的内存。

python 字典 哈希 相等

评论


答:

-2赞 agtoever 1/12/2020 #1

您的问题与可变对象和不可变对象的概念密切相关。您的问题的确切答案也是特定于实现的。我将为 CPython 回答这个问题,但请记住,其他实现具有不同的行为。

在 CPython 中,一旦创建(分配或使用)了不可变对象,就会在内存中创建该对象。具有相同值的每个下一个不可变对象都指向同一个对象 (!)。您可以使用函数(在 CPython 中是对象的内存地址)来检查这一点。id

例如:

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 会为您解决这个问题。对于集合中的不可变对象也是如此。

对于任意不可变的可哈希对象,是否有通用解决方案?

请注意,不可变对象也可以具有哈希值!默认情况下,所有内置的不可变对象都有哈希值,而可变对象则没有,但用户可以定义具有自己的哈希函数的类。从而创建可变和可哈希的对象。

评论

0赞 Alexey 1/12/2020
你声称的是假的:返回。我相信我有 CPython。x = 1000; y = 1000; x is yFalse
1赞 Mad Physicist 1/12/2020
“每个具有相同值的下一个不可变对象都指向同一个对象(!)”是完全不正确的。有一些尝试将字符串和小整数插入其中,但重要的使用通常会绕过这些情况。
0赞 Mad Physicist 1/12/2020
@Alexey。预定义的整数为 256 或 128 左右。
0赞 Alexey 1/12/2020
@MadPhysicist,请参阅此处:docs.python.org/3/c-api/long.html#c.PyLong_FromLong
0赞 agtoever 1/12/2020
致所有反对者:请解释这种行为:当这些不可变对象的值相等时,它们的身份也是相等的。