nameduple 查找集的复杂性

Question

您好，Python 我有一个命名元组，因为我想在同一个对象中存储一些值。

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

我将这些 A 存储在注册表中 class，其中包含一个 set()

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 检索那些我在大多数情况下 (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)。但是，如果我像上面的例子那样将 namedtuple 存储在集合中，这仍然是真的吗？或者这样的构造是否会增加我的注册表中对象的查找时间，并且是另一种能够按时间首选的多个键查找值的方法。

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)

nameduple 查找集的复杂性

complexity of set of nameduple lookup

python

dictionary

set

namedtuple