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]関連する item を簡単に取得できることはわかっています'Node 2'が、への参照を効率的に返したいと考えていますn2。

のすべての要素を調べることでできることはわかっていますがd、試してみましたが、遅すぎます（辞書には何千もの項目があり、これをかなりの回数行います）。

内部でその識別子のand演算子をdict使用して、ノードとそれに関連するアイテムを格納していることを知っています。実際、ルックアップを使用すると、実際には中間ステップとしてルックアップする必要があるため、これは間違いなく可能です。hasheqn2'Node 2'my_id'Node 2'n2

これを使用して、データをグラフに保存しています。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

2つの辞書があります。-キー/値をプライマリディクショナリに追加するときはいつでも、キー/値を交換して、それらを逆ディクショナリにも追加します。

例えば：

# 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]

キーはノードではなく識別子です。このように 2 つのクラスを「等しい」状態にすることは、非常に危険です。本当にノードを名前で見つける必要がある場合は、ノード クラスまたは外部で実行する必要がありますが、ハッシュ内のノードの存在に依存するべきではありません。

それを変更できない場合（コードを変更できないため）、非効率的な方法で立ち往生していると思います

于 2010-11-19T13:48:27.497 に答える
0

my_id を使用して「ノード 2」を検索すると、実際には中間ステップとして n2 を検索する必要があります

これは正しくありません。ディクショナリはハッシュテーブルです。アイテムのハッシュを (バケットの) エントリにマップします。を要求するとd[my_id]、Python はまずそれを取得hash(my_id)し、次に で調べdます。hash(n1) == hash(id1)非常に悪いことです。

識別子とノード間のマッピングを求めています。これらのいずれかが必要な場合は、自分で作成する必要があります。

識別子はすべて作成時にノードと一致していますか?それとも後で構築しますか? つまり、識別子 を持つノードを検索できるようにすることを本当に要求していますidentifier({'name':'Alex'})か、それともその識別子は既に作成されてノードに追加されていますか? 後者の場合、次のことができます。

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