Most efficient dict filter on key tuple?

Question

I have a dict wherein a value needs to be retrievable by any one of several keys. It seemed that making multiple dictionaries or multiple entries in a single dictionary pointing to the same value object (ref type) was more maintenance than I wanted to commit to.

I decided to use a tuple for the key. I would then use filter(...) with a lambda to determine if the given provider_lookup was in the keyed tuple. I am not concerned that a value may be duplicated across tuples (this will be guarded against as the code moves forward). Here are the two methods:

def register_block_provider(self, provider):
 block = provider()
 self.__block_providers.update({
 (block.block_id, block.name): block
 })
def get_block_provider(self, provider_lookup):
 for provider_key in filter(lambda p: (p[0], p[1]), self.__block_providers.keys()):
 if provider_lookup in provider_key:
 print("we've found the key: {key}".format(key=provider_key))
 return self.__block_providers[provider_key]
 return None

Are there specific improvements that can be made to the get_block_provider method? This works fine so I'm just asking for some feedback on the details of the implementation.

• David Foerster: "It seemed that [...] multiple entries in a single dictionary pointing to the same value object (ref type) was more maintenance than I wanted to commit to." – Why? This is exactly what dicts are for and good at, so you should use them that way unless you have a very good reason not to.
• IAbstract: Multiple entries with the same value and different keys pointing to that reference requires that if an entry is added that all variants of the expected keys are added (or deleted if removed). Using a 'compound key' means one entry, one point of failure (???). Maybe I'm being overly cautious about the maintenance needs. :)
• Roman Susi: I guess, you do not have many keys in self.__block_providers as you can afford iterating through them all for what seem to be the most frequent case (lookup). Why bother with dicts then?
• David Foerster: I would use a class derived from dict (a subclass of collections.UserDict would be idiomatic) to hide the logic of adding and removing multiple keys at the same time. But this is leading off topic and would be much better on Stack Overflow or Software Engineering.
• IAbstract: @RomanSusi: I would expect only 200-300 entries in the dictionary at some point. The number of keys is expected to be at most 2. The number of entries could explode depending on possible extensions (custom object descendants) that end users could provide. While I am expecting to provide about 50 objects, the creativity of end users cannot be determined.

Answer 1

filter

Is useless here. It's purpose is to filter out values based on a predicate:

list(filter(f, data))

is the same as:

[d for d in data if f(d)]

Given that, in your case, f is lambda p: (p[0], p[1]), it will always evaluate to True in a boolean context. Thus never filtering anything. I’m not sure what it was you were trying to achieve, but you can remove filter without changing the behaviour:

def get_block_provider(self, provider_lookup):
 for provider_key in self.__block_providers:
 if provider_lookup in provider_key:
 print("we've found the key: {key}".format(key=provider_key))
 return self.__block_providers[provider_key]
 return None

get_block_provider

I believe this method is to be used in the same kind of way than __getitem__ on dicts. Thus you need to act accordingly; it's the principle of least attonishment: you claim to be somewhat a dict then you get to act like a dict.

First of, remove that print. There is nothing justifying that line in a getter. If the user want to be sure it got something, it's its job to print something. It's not your classe's job.

Second, it might be better to raise a KeyError as a dict would have instead of returning None:

def get_block_provider(self, provider_lookup):
 for provider_key in self.__block_providers:
 if provider_lookup in provider_key:
 return self.__block_providers[provider_key]
 raise KeyError("No block corresponding to lookup '{}'".format(provider_lookup))

Be a dict

You said that

It seemed that making multiple dictionaries or multiple entries in a single dictionary pointing to the same value object (ref type) was more maintenance than I wanted to commit to.

But I disagree. Especially since looking at the code and your comments, you’re only expecting 2 different kind of lookups for your blocks: ID and name.

You do not have to entirely expose a dict interface. But you should use its strength. Your for loop in get_block_provider is a complete waste of time: you’re performing an \$O(n)\$ lookup where a dict would have provided an \$O(1)\$ one.

Instead, your lookup should rely on the underlying dictionary one. And you should focus on having only one entry point to update both keys at once:

def register_block_provider(self, provider):
 block = provider()
 blocks = self.__block_providers
 # update both keys at once
 blocks[block.block_id] = blocks[block.name] = block
def get_block_provider(self, provider_lookup):
 return self.__block_providers[provider_lookup]

You can even define

__getitem__ = get_block_provider

to mimic a dict interface.

• IAbstract: Compelling argument for multiple entries in a dict ... especially with the sample code you provided. BTW, print statement was only meant for debugging. :)

Answer 2

NOTE: I have changed the name provider to model as much of this repository is now a base (abstract) class with register_model specialized to multiple repo types.

Posting an answer as an alternative to multiple entries in the dictionary. Although @MathiasEttinger had compelling arguments for doing so, I still couldn't do it. A secondary dictionary was my solution (although I was against that, also, at first).

That said, my solution did take much of his review into consideration. Instead of multiple entries in the one dictionary, I implement a second dictionary keyed to model_key which is a tuple(id, name)

# implement dict-style indexer
def __getitem__(self, item_key):
 return self.get_model(item_key)
# get the model
def get_model(self, model_lookup):
 """
 Get a model by name or id
 :param model_lookup: tuple(int, str); ex: (1, "FooModel")
 :return: (Model descendant)
 """
 # validate provider lookup if tuple(int, str)
 if isinstance(model_lookup, tuple) \
 and len(model_lookup) == 2 \
 and isinstance(model_lookup[0], int) \
 and isinstance(model_lookup[1], str):
 model_key = model_lookup
 else:
 model_key = self.get_model_key(model_lookup)
 if model_key is not None:
 return self._models[model_key]
 return None
def get_model_key(self, model_lookup):
 """
 Get the model key for the specified model id or name
 :param model_lookup: search by model id or name
 :return: (int, str) if key found; else None
 """
 if not isinstance(model_lookup, int) and not isinstance(model_lookup, str):
 raise ValueError("model_lookup must be either an int or a str: {param}{type}"
 .format(param=model_lookup,
 type=type(model_lookup).__name__))
 if model_lookup in self._model_keys:
 return self._model_keys[model_lookup]
 return None
# specialized BlockModel registration
def register_model(self, model):
 """
 Registers a block model with the current block repository
 :param model: model descendant
 :return: (int, str) model key
 """
 block = model()
 if self.get_model_key(block.block_id) or self.get_model_key(block.name):
 raise KeyError("Duplicate key member already exists")
 model_key = (block.block_id, block.name)
 self._model_keys[block.block_id] = self._model_keys[block.name] = model_key
 self._models.update({
 model_key: block
 })
 return model_key

I am still returning None from get_model with the intent that I would substitute another model for the one not found. The calling object would log that a specific model is not found and another used in its place. I don't want this to raise an exception. The caller, if None is deemed catastrophic, will raise an Exception.

With the idea that other Python developers would be able to write extension objects (with varying levels of skill), I am intentionally making this a forgiving API where it is appropriate to do so.

• 301_Moved_Permanently: Since the signatures are the same, you can simplify the writing by defining __getitem__ = get_model (after having def get_model(...):, of course).