5

我有一个可散列的标识符，用于将内容放入字典中：

class identifier():
    def __init__(self, d):
        self.my_dict = d
        self.my_frozenset = frozenset(d.items())
    def __getitem__(self, item):
        return self.my_dict[item]
    def __hash__(self):
        return hash(self.my_frozenset)
    def __eq__(self, rhs):
        return self.my_frozenset == rhs.my_frozenset
    def __ne__(self, rhs):
       return not self == rhs

我有一个节点类型，它封装标识符以实现散列和相等：

class node:
    def __init__(self, id, value):
        # id is of type identifier
        self.id = id
        self.value = value
        # define other data here...
    def __hash__(self):
        return hash(self.id)
    def __eq__(self, rhs):
        if isinstance(rhs, node):
            return self.id == rhs.id
        ### for the case when rhs is an identifier; this allows dictionary
        ### node lookup of a key without wrapping it in a node
        return self.id == rhs
    def __ne__(self, rhs):
        return not self == rhs

我将一些节点放入字典中：

d = {}
n1 = node(identifier({'name':'Bob'}), value=1)
n2 = node(identifier({'name':'Alex'}), value=2)
n3 = node(identifier({'name':'Alex', 'nationality':'Japanese'}), value=3)
d[n1] = 'Node 1'
d[n2] = 'Node 2'
d[n3] = 'Node 3'

一段时间后，我只有一个标识符：

my_id = identifier({'name':'Alex'})

有什么方法可以有效地查找在这个字典中存储了这个标识符的节点？

请注意，这比听起来要复杂一些；我知道我可以轻松地使用它d[my_id]来检索关联的项目'Node 2'，但我想有效地返回对n2.

我知道我可以通过查看 中的每个元素来做到这一点d，但我已经尝试过了，它太慢了（字典中有数千个项目，我这样做了很多次）。

我知道内部dict正在使用该标识符的hashandeq运算符来存储节点n2及其关联项，'Node 2'. 其实使用my_idto lookup'Node 2'其实需要lookupn2作为中间步骤，所以这应该是绝对可以的。

我正在使用它来将数据存储在图表中。节点有很多value未在散列中使用的附加数据（我放的地方）。我没有创建我正在使用的图形包（networkX），但我可以看到存储我的节点的字典。我还可以在节点标识符周围保留一个额外的字典，但这会很痛苦（我需要包装图形类并重写所有添加节点、删除节点、从列表中添加节点、从列表中删除节点、添加边等键入函数以使该字典保持最新）。

这真是个谜。任何帮助将非常感激！

4

5 回答 5

5

代替

d[n1] = 'Node 1'

采用：

d[n1] = ('Node 1', n1)

然后，无论您如何找到该值，您都可以访问 n1 。

如果你所拥有的只是一个等于 k1 的 k2，我不相信字典有办法检索原始密钥 k1。

于 2010-11-19T12:30:00.730 回答
3

有两本词典。- 每当您向主字典添加键/值时，也将它们添加到反向字典，但键/值交换。

例如：

# When adding a value:
d[n2] = value;
# Must also add to the reverse dictionary:
rev[value] = d

# This means that:
value = d[n2]
# Will be able to efficiently find out the key used with:
key = rev[value]
于 2010-11-19T12:37:27.757 回答
1

这是一种在 NetworkX 中使用自定义节点对象的方法。如果将对象存储在“节点属性”字典中，则可以将其用作反向字典，通过引用 id 来取回对象。这有点尴尬，但它有效。

import networkx as nx

class Node(object):

    def __init__(self,id,**attr):
        self.id=id
        self.properties={}
        self.properties.update(attr)

    def __hash__(self):
        return self.id

    def __eq__(self,other):
        return self.id==other.id

    def __repr__(self):
        return str(self.id)

    def __str__(self):
        return str(self.id)


G=nx.Graph()
# add two nodes
n1=Node(1,color='red') # the node id must be hashable
n2=Node(2,color='green')
G.add_node(n1,obj=n1)
G.add_node(n2,obj=n2)

# check what we have
print G.nodes() # 1,2
print n1,n1.properties['color'] # 1,red
print n1==n2   # False 
for n in G:
    print n.properties['color']
print Node(1) in G # True
# change color of node 1
n1.properties['color']='blue'
for n in G:
    print n.properties

# use "node attribute" data in NetworkX to retrieve object
n=G.node[Node(1)]['obj']
print type(n) # <class '__main__.Node'>
print n # 1
print n.id # 1
print n.properties # {'color': 'blue'}

当然，您可以定义一个使这更简单的函数：

   def get_node(G,n):
        return G.node[Node(1)]['obj']

    n=get_node(G,1)
    print n.properties
于 2010-11-20T17:03:08.697 回答
0

问题是，不能保证密钥实际上是一个节点。如果你这样做怎么办

d[my_id]=d[my_id]

除了现在，一切仍然可以正常工作，您的密钥是标识符而不是节点。像这样允许两个类“相等”是非常危险的。如果你真的需要通过它的名字找到一个节点，应该在节点类或外部完成，但不应该依赖于哈希中节点的存在。

如果你不能修改它（因为你不能修改代码），那么我猜你会坚持做低效的方式

于 2010-11-19T13:48:27.497 回答
0

使用 my_id 查找“节点 2”实际上需要查找 n2 作为中间步骤

这不是真的。字典是一个哈希表：它将项目的哈希映射到（一桶）条目。当你请求时d[my_id]，Python 首先获取hash(my_id)然后在d. 你会感到困惑，因为你有那个hash(n1) == hash(id1)，这是一件非常糟糕的事情。

您要求在标识符和节点之间进行映射。如果您想要其中之一，则必须自己创建一个。

标识符是否在创建时都与节点匹配，或者您稍后再构建它们？也就是说，您真的要求能够找到带有 identifier 的节点identifier({'name':'Alex'})，还是已经创建了该标识符并将其添加到节点？如果是后者，您可以执行以下操作：

class Node:
    def __init__(self, id, value):
        id.parent = self
        ...
于 2010-11-19T14:17:40.053 回答