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.

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.

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.