في بيثون ، كيف يمكنك استرداد مفتاح من القاموس؟

Question

لدي معرف قابل للاستعداد لوضع الأشياء في القاموس:

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) ، لكن يمكنني رؤية القاموس الذي يخزن العقد الخاصة بي. يمكنني أيضًا الحفاظ على قاموس إضافي حول المعرفات للعقد ، لكن هذا سيكون ألمًا (أحتاج إلى لف فئة الرسم البياني وإعادة كتابة جميع العقدة ، وإزالة العقدة ، وإضافة العقد من القائمة ، وإزالة العقد من القائمة ، وإضافة EDGE ، إلخ. اكتب وظائف للحفاظ على هذا القاموس محدثًا).

هذا هو تماما اللغز. أي مساعدة سيكون موضع تقدير حقا!

Answer 1

بدلاً من

d[n1] = 'Node 1'

استعمال:

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

ثم يمكنك الوصول إلى N1 بغض النظر عن كيفية العثور على القيمة.

لا أعتقد أن هناك طريقة مع القواميس لاسترداد المفتاح الأصلي K1 إذا كان كل ما لديك هو K2 يساوي K1.

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

Answer 3

فيما يلي طريقة لاستخدام كائن عقدة مخصص مع NetworkX. إذا قمت بتخزين الكائن في قاموس "سمة العقدة" ، فيمكنك استخدامه كقاموس عكسي لاستعادة الكائن من خلال الرجوع إلى المعرف. إنه محرج بعض الشيء لكنه يعمل.

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

Answer 4

الشيء هو أنه لا يوجد ضمان بأن المفتاح هو عقدة فعالة. ماذا لو فعلت

d[my_id]=d[my_id] 

كل شيء سيظل يعمل بشكل مثالي إلا الآن ، مفتاحك هو معرف وليس عقدة. السماح لفصلين بـ "متساوٍ" مثل هذا أمر خطير حقًا. إذا كنت بحاجة حقًا إلى العثور على عقدة باسمها يجب أن يتم في فئة العقدة أو الخارجي ، ولكن لا ينبغي أن تعتمد على عدم وجود العقدة في تجزئة.

إذا لم تتمكن من تعديل ذلك (لأنه لا يمكنك تعديل الكود) ، فأعتقد أنك عالق للقيام بالطريقة غير الآلية

Answer 5

يحتاج استخدام my_id إلى البحث عن "Node 2" فعليًا إلى البحث عن N2 كخطوة وسيطة

هذا هو غير صحيح. القاموس هو علامة تصنيف: إنه يرسم تجزئة عنصر إلى إدخالات (دلو من). عندما تسأل d[my_id], ، بيثون أولاً hash(my_id) ثم ينظر إلى ذلك في d. أنت تشعر بالارتباك لأن لديك ذلك hash(n1) == hash(id1), ، وهو شيء سيء للغاية.

أنت تطلب رسم الخرائط بين المعرفات والعقد. إذا كنت تريد واحدة من هذه ، فسيتعين عليك إنشاء واحدة بنفسك.

---

هل جميع المعرفات متطابقة مع العقد عند الخلق ، أم أنك تبنيها لاحقًا؟ هذا هو أنت هل حقا يطلب أن تكون قادرًا على العثور على العقدة مع المعرف identifier({'name':'Alex'}), ، أم أن هذا المعرف تم إنشاؤه بالفعل وإضافته إلى عقدة؟ إذا كان الأخير ، يمكنك القيام بما يلي:

class Node:
    def __init__(self, id, value):
        id.parent = self
        ...