Python dictionary - binary search for a key?

Question

I want to write a container class that acts like a dictionary (actually derives from a dict), The keys for this structure will be dates.

When a key (i.e. date) is used to retrieve a value from the class, if the date does not exist then the next available date that preceeds the key is used to return the value.

The following data should help explain the concept further:

Date (key)      Value
2001/01/01      123
2001/01/02       42
2001/01/03      100
2001/01/04      314
2001/01/07      312
2001/01/09      321

If I try to fetch the value associated with key (date) '2001/01/05' I should get the value stored under the key 2001/01/04 since that key occurs before where the key '2001/01/05' would be if it existed in the dictionary.

In order to do this, I need to be able to do a search (ideally binary, rather than naively looping through every key in the dictionary). I have searched for bsearch dictionary key lookups in Python dictionaries - but have not found anything useful.

Anyway, I want to write a class like that encapsulates this behavior.

This is what I have so far (not much):

#
class NearestNeighborDict(dict):
#
"""
#
a dictionary which returns value of nearest neighbor 
if specified key not found
#
"""

def __init__(self, items={}):
    dict.__init__(self, items)


def get_item(self, key):
    # returns the item stored with the key (if key exists)
    # else it returns the item stored with the key

A tree would be a better data structure for this. – FogleBird Jul 02 '10 at 02:13 — FogleBird, Jul 02 '10 at 02:13

Alex Martelli · Accepted Answer · 2010-07-02T02:31:36.750

You really don't want to subclass dict because you can't really reuse any of its functionality. Rather, subclass the abstract base class collections.Mapping (or MutableMapping if you want to also be able to modify an instance after creation), implement the indispensable special methods for the purpose, and you'll get other dict-like methods "for free" from the ABC.

The methods you need to code are __getitem__ (and __setitem__ and __delitem__ if you want mutability), __len__, __iter__, and __contains__.

The bisect module of the standard library gives you all you need to implement these efficiently on top of a sorted list. For example...:

import collections
import bisect

class MyDict(collections.Mapping):
  def __init__(self, contents):
    "contents must be a sequence of key/value pairs"
    self._list = sorted(contents)
  def __iter__(self):
    return (k for (k, _) in self._list)
  def __contains__(self, k):
    i = bisect.bisect_left(self._list, (k, None))
    return i < len(self._list) and self._list[i][0] == k
  def __len__(self):
    return len(self._list)
  def __getitem__(self, k):
    i = bisect.bisect_left(self._list, (k, None))
    if i >= len(self._list): raise KeyError(k)
    return self._list[i][1]

You'll probably want to fiddle __getitem__ depending on what you want to return (or whether you want to raise) for various corner cases such as "k greater than all keys in self".

@Daniel, yes, with this simple implementation (using binary search as requested) inserting a totally new key will be linear (as will deleting an existing one). If such insertions and deletions are frequent, adapting http://www.dmh2000.com/cjpr/RBPython.html , http://code.activestate.com/recipes/576817-red-black-tree/ , or the like (still with `collections.MutableMapping` support;-) might be preferable (still `O(log n)` operations of course -- no way to get the amortized `O(1)` perf of a dict w/o some caching/lookaside trickery based on knowing the frequency of various operation patterns;-). — Alex Martelli, Jul 02 '10 at 14:56

score 6 · Answer 2 · answered Apr 10 '14 at 19:05

6

The sortedcontainers module provides a SortedDict type that maintains the keys in sorted order and supports bisecting on those keys. The module is pure-Python and fast-as-C implementations with 100% test coverage and hours of stress.

For example:

from sortedcontainers import SortedDict

sd = SortedDict((date, value) for date, value in data)

# Bisect for the index of the desired key.
index = sd.bisect('2001/01/05')

# Lookup the real key at that index.
key = sd.iloc[index]

# Retrieve the value associated with that key.
value = sd[key]

Because SortedDict supports fast indexing, it's easy to look ahead or behind your key as well. SortedDict is also a MutableMapping so it should work nicely in your type system.

answered Apr 10 '14 at 19:05

GrantJ

8,162
3
52
46

Note that maintaining a companion array of the sorted keys (which is required for bisect to work) will still mean O(N) insertion and O(N) deletion, because at some point, that array has to undergo array insertion or array deletion to be kept in sync with the underlying dictionary. There are alternatives using tree-based dictionaries but then you don't get O(1) insertion and removal on the dict side of things. – ely Apr 08 '16 at 18:33
@Mr.F [SortedContainers](http://www.grantjenks.com/docs/sortedcontainers/) is more clever than that. It still uses `bisect` but avoids the O(N) insertion and deletion costs. See the [comparisons](http://www.grantjenks.com/docs/sortedcontainers/performance.html) and a discussion of the [implementation](http://www.grantjenks.com/docs/sortedcontainers/implementation.html). – GrantJ Apr 09 '16 at 23:05

score 0 · Answer 3 · answered Oct 10 '14 at 12:14

0

Use the floor_key method on bintrees.RBTree: https://pypi.python.org/pypi/bintrees/2.0.1

answered Oct 10 '14 at 12:14

fred271828

959
1
11
18

development has been discontinued on this one. instead, they refer to https://pypi.org/project/sortedcontainers/ – mrhd Apr 14 '20 at 11:45

score 0 · Answer 4 · answered Jul 02 '10 at 02:37

I'd extend a dict, and override the __getitem__ and __setitem__ method to store a sorted list of keys.

from bisect import bisect

class NearestNeighborDict(dict):
    def __init__(self):
        dict.__init__(self)
        self._keylist = []

    def __getitem__(self, x):
        if x in self:
            return dict.__getitem__(self, x)

        index = bisect(self._keylist, x)
        if index == len(self._keylist):
            raise KeyError('No next date')

        return dict.__getitem__(self, self._keylist[index])

    def __setitem__(self, x, value):
        if x not in self:
            index = bisect(self._keylist, x)
            self._keylist.insert(index, value)

        dict.__setitem__(self, x, value)

It's true you're better off inheriting from MutableMapping, but the principle is the same, and the above code can be easily adapted.

score 0 · Answer 5 · answered Jul 02 '10 at 02:40

0

Why not just maintain a sorted list from dict.keys() and search that? If you're subclassing dict you may even devise an opportunity to do a binary insert on that list when values are added.

answered Jul 02 '10 at 02:40

andyortlieb

2,326
3
21
33

Python dictionary - binary search for a key?

5 Answers5

Linked