複雜的一套nameduple查找

Question

嗨在Python我有一個namedtuple，因爲我想存儲在同一個對象的幾個值。

A = namedtuple("A", "key1 key2 key3") 

我存儲這些A在其中持有一組（）

class ARegistry(object): 

    def __init__(self): 
     self._register = set() 


    def register(self, value1, value2, value3): 
     self._register.add(A(key1=value1, key2=value2, key3=value3) 

    def __getitem__(self, value1): 
     return next((x for x in self._registry if x.key1 == value1), None) 

    def get_by_key2(self, value): 
     return next((x for x in self._registry if x.key2 == value), None) 


    def get_by_key3(self, value): 
     return next((x for x in self._registry if x.key3 == value), None) 

這樣，我可以很容易地檢索由key1的那些namedtuples，我需要在大多數情況下（80％）的註冊類，同時也對KEY2或KEY3（其他20％）：

myobj1 = a_register["foo"] # Search on key1 
myobj2 = a_register.get_by_key2("bar") # Search on key2 
myobj3 = a_register.get_by_key3("bar") # Search on key3 

問題：

現在，我從關於集合的文檔中讀到，集合中的查找是否具有複雜性O（1）。但是，如果我像上面的例子中那樣存儲名爲tuple的數據，這仍然是真的嗎？或者這樣的構造增加了我的註冊表中對象的查找時間，並且是另一種能夠通過多個鍵首選，按時間查找值的另一種方法。

Answer 1

如果您正在查找集合中的項目，則查找集合中只有O（1）。您正在查看集合中的每個項目以查看它是否符合特定標準 - 這是完全不同的（平均而言，它將是O（N）複雜度）。

一個更有效的方式來存儲這將是把元組成一個字典，將密鑰映射到元組。您需要3個字節以這種方式存儲數據（因此，如果需要關注，此方法中涉及的內存會更多）

from collections import defaultdict 

class ARegistry(object): 

    def __init__(self): 
     self._register = [ 
      defaultdict(list), # lookup based on first item in A 
      defaultdict(list), # lookup based on second item in A 
      defaultdict(list), # lookup based on third item in A 
     ] 

    def register(self, value1, value2, value3): 
     tup = A(key1=value1, key2=value2, key3=value3) 
     for v, registry in zip(tup, self._register): 
      registry[v].append(tup) 

    def __getitem__(self, value1): 
     return next(iter(self._register[0][value1]), None) 

    def get_by_key2(self, value): 
     return next(iter(self._register[1][value]), None) 

    def get_by_key3(self, value): 
     return next(iter(self._register[2][value]), None)