Python では、辞書からキーを取得するにはどうすればよいでしょうか?
-
26-09-2019 - |
質問
辞書に内容を登録するためのハッシュ可能な識別子があります。
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
を使用しています hash
そして eq
ノードを格納するためのその識別子の演算子 n2
およびそれに関連するアイテム、 'Node 2'
. 。実際に使用すると、 my_id
見上げる 'Node 2'
実際に調べる必要があります n2
中間ステップとして、 これは間違いなく可能なはずです。
これをグラフにデータを保存するために使用しています。ノードには多くの追加データがあります (ここに value
) ハッシュでは使用されません。使用しているグラフ パッケージ (networkX) は作成しませんでしたが、ノードを格納するディクショナリを見ることができます。ノードへの識別子の追加の辞書を保持することもできますが、これは面倒です(グラフクラスをラップして、ノードの追加、ノードの削除、リストからのノードの追加、リストからのノードの削除、エッジの追加をすべて書き直す必要があります) 、など。type 関数は辞書を最新の状態に保ちます)。
これはかなりのパズルです。助けていただければ幸いです。
解決
の代わりに
d[n1] = 'Node 1'
使用:
d[n1] = ('Node 1', n1)
そうすれば、値をどのように見つけたかに関係なく、n1 にアクセスできます。
k1 に等しい k2 しかない場合、辞書を使って元のキー k1 を取得する方法はないと思います。
他のヒント
辞書を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]
ここでは、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
問題は、キーが事実上ノードであるという保証はないということです。そうしたらどうしますか
d[my_id]=d[my_id]
キーがノードではなく識別子であることを除けば、すべてが引き続き完全に機能します。このように 2 つのクラスを「同等」にすることは非常に危険です。本当に名前でノードを検索する必要がある場合は、Node クラスまたは外部で実行する必要がありますが、ハッシュ内のノードの存在に依存すべきではありません。
それを変更できない場合(コードを変更できないため)、非効率的な方法を実行することになっていると思います
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
...