complexity of set of nameduple lookup
Question: Hi in Python i have a namedtuple because i want to store a few values in the
same object.

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

I store those A's in a registry class which holds a 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) 
    

In this way i can easily retrieve those namedtuples by key1 which i need in
most cases (80%), but also on key2 or key3 (other 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
    

**Question:**

Now from that i read in the documentation about sets, is that lookup in sets
is of complexity O(1). But is this still true if i store namedtuple in sets
like in the example above? Or does such a construct increase the lookup time
of objects in my registry and is another method of being able to lookup values
by multiple keys preferred, time-wise.


Answer: Lookup in a set is only O(1) if you are looking for the item in the set. You
are looking at each item in the set to see if it matches a particular
criterion -- which is completely different (It'll be O(N) complexity on
average).

A more efficient way to store this would be to put the tuple into a dict that
maps the key to the tuple. You'll need 3 dicts to store the data this way (so
there is more memory involved in this approach if that is a concern)

    
    
    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)
    

