Using the bisect module to create a mapping

In the previous example, we created a dict mapping to achieve a fast mapping from a color name to a Color object. This isn't the only choice; we can use the bisect module instead. Using the bisect module means that we have to create a sorted object, which we can then search. To be perfectly compatible with the dict mapping, we can use collections.Mapping as the base class.

The dict mapping uses a hash to locate items almost immediately. However, this requires allocating a fairly large block of memory. The bisect mapping does a search, which doesn't require as much memory, but performance can be described as immediate.

A static mapping class looks like the following command snippet:

import bisect
from collections import Mapping
from typing import Iterable, Tuple, Any

class StaticMapping(Mapping):
    def __init__(self, 
      iterable: Iterable[Tuple[Any, Any]]) -> None:
        self._data = tuple(iterable)
        self._keys = tuple(sorted(key for key,_ in self._data))
    
    def __getitem__(self, key):
        ix= bisect.bisect_left(self._keys, key)
        if (ix != len(self._keys) 
          and self._keys[ix] == key_:
            return self._data[ix][1]
        raise ValueError("{0!r} not found".format(key))
    def __iter__(self):
        return iter(self._keys)
    def __len__(self):
        return len(self._keys)  

This class extends the abstract superclass collections.Mapping. It provides an initialization and implementations for three functions missing from the abstract definition. The type of Tuple[Any, Any] defines a generic two-tuple. 

The __getitem__() method uses the bisect.bisect_left() function to search the collection of keys. If the key is found, the appropriate value is returned. The __iter__() method returns an iterator, as required by the superclass. The __len__() method, similarly, provides the required length of the collection.

Another option is to start with the source code for the collections.OrderedDict class, change the superclass to Mapping instead of MutableMapping, and remove all of the methods that implement mutability. For more details on which methods to keep and which to discard, refer to the Python Standard Library, section 8.4.1.

Visit the following link for more details:

https://docs.python.org/3.3/library/collections.abc.html#collections-abstract-base-classes

This class may not seem to embody too many functional programming principles. Our goal here is to support a larger application that minimizes the use of stateful variables. This class saves a static collection of key-value pairs. As an optimization, it materializes two objects.

An application would create an instance of this class to perform rapid lookups of values associated with keys. The superclass does not support updates to the object. The collection, as a whole, is stateless. It's not as fast as the built-in dict class, but it uses less memory and, through the formality of being a subclass of Mapping, we can be assured that this object is not used to contain a processing state.