Python-Wörterbuch - binäre Suche nach einem Schlüssel?

Question

Ich möchte eine Container-Klasse schreiben, die wie ein Wörterbuch funktioniert (tatsächlich von einem Diktat abgeleitet). Die Schlüssel für diese Struktur sind Daten.

Wenn ein Schlüssel (date) zum Abrufen eines Werts aus der Klasse verwendet wird, wird das nächste verfügbare Datum, das dem Schlüssel vorausgeht, verwendet, um den Wert zurückzugeben, wenn das Datum nicht vorhanden ist.

Folgende Daten sollte das Konzept erklären helfen weiter:

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 

Wenn ich versuche, den Wert mit der Taste (Datum) ‚2001.01.05‘ Ich den Wert bekommen sollte unter dem Schlüssel gespeichert ist, zugeordnet zu holen 2001/01/04 da dieser Schlüssel vor dem Schlüssel "2001/01/05" vorkommt, wenn er im Wörterbuch vorhanden wäre.

Um dies zu tun, muss ich in der Lage sein, eine Suche durchzuführen (idealerweise binär, anstatt naiv durch alle Schlüssel im Wörterbuch zu gehen). Ich habe in den Python-Wörterbüchern nach bsearch-Wörterbuch-Schlüsselsuchen gesucht - aber nichts Nützliches gefunden.

Wie auch immer, ich möchte eine Klasse schreiben, die dieses Verhalten kapselt.

Dies ist, was ich bisher (nicht viel):

# 
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 

Answer 1

Sie wirklich nicht wollen, dict Unterklasse, weil man nicht wirklich eine ihrer Funktionalität wiederverwenden können. Vielmehr, Unterklasse der abstrakten Basisklasse collections.Mapping (oder MutableMapping, wenn Sie in der Lage sein möchten, eine Instanz nach der Erstellung zu ändern), implementieren Sie die unverzichtbare spezielle Methoden für den Zweck, und Sie erhalten andere dict-ähnliche Methoden "kostenlos" aus das ABC.

Die Methoden, die Sie Code benötigen, sind __getitem__ (und __setitem__ und __delitem__ wenn Sie Veränderlichkeit wollen), __len__, __iter__ und __contains__.

Das Modul bisect der Standardbibliothek bietet Ihnen alles, was Sie benötigen, um diese effizient auf einer sortierten Liste zu implementieren. Zum Beispiel ...:

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] 

Sie wollen wahrscheinlich __getitem__ Geige je nachdem, was Sie zurückkommen möchten (oder ob Sie erhöhen) für verschiedene Sonderfälle wie "k größer als alle Tasten in self ".

Answer 2

würde ich ein dict, erweitern und die __getitem__ und __setitem__ Methode eine sortierte Liste von Schlüsseln zu speichern außer Kraft setzen.

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) 

Es ist wahr, du bist besser dran von MutableMapping vererben, aber das Prinzip ist das gleiche, und der obige Code leicht angepasst werden kann.

Answer 3

Warum nicht einfach eine sortierte Liste von dict.keys() verwalten und suchen? Wenn Sie dict unterklassifizieren, können Sie sogar eine Möglichkeit entwickeln, eine binäre Einfügung in diese Liste durchzuführen, wenn Werte hinzugefügt werden.

Answer 4

Das Modul sortedcontainers bietet einen SortedDict Typ, der die Schlüssel in sortierter Reihenfolge verwaltet und die Halbierung dieser Schlüssel unterstützt.Das Modul ist pure-Python und fast-as-C implementations mit 100% Testabdeckung und Stunden Stress.

Zum Beispiel:

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] 

Da SortedDict schnelle Indizierung unterstützt, ist es einfach, wie weit vor oder hinter dem Schlüssel zu suchen. SortedDict ist auch ein MutableMapping, also sollte es in Ihrem Typsystem gut funktionieren.

Answer 5

die floor_key Methode auf bintrees.RBTree Verwendung: https://pypi.python.org/pypi/bintrees/2.0.1