"Kopieren und Einfügen von Codes" (um bisect Quellen in den eigenen Code zu kopieren) ist nicht empfehlenswert, da es alle möglichen Kosten mit sich bringt (viel zusätzlicher Quellcode, den Sie testen und warten müssen, Schwierigkeiten bei der Handhabung von Upgrades im Upstream-Code, den Sie kopiert haben, usw.); der beste Weg, Standard-Bibliotheksmodule wiederzuverwenden, ist, sie einfach zu importieren und zu verwenden.
Die Umwandlung der Wörterbücher in sinnvoll vergleichbare Einträge in einem Durchgang ist jedoch O(N), was (auch wenn jeder Schritt des Durchgangs einfach ist) schließlich die O(log N)-Zeit der eigentlichen Suche übersteigt. Da bisect nicht unterstützen kann key= Schlüsselauszieher wie sort was die Lösung für dieses Dilemma ist - wie kann man die Daten wiederverwenden? bisect durch Import und Aufruf, ohne vorherigen O(N)-Schritt...?
Wie zitiert aquí Die Lösung liegt in dem berühmten Ausspruch von David Wheeler: "Alle Probleme in der Informatik können durch eine weitere Ebene der Indirektion gelöst werden". Nehmen wir z.B. ....:
import bisect
listofdicts = [
{'dt': '2009-%2.2d-%2.2dT12:00:00' % (m,d) }
for m in range(4,9) for d in range(1,30)
]
class Indexer(object):
def __init__(self, lod, key):
self.lod = lod
self.key = key
def __len__(self):
return len(self.lod)
def __getitem__(self, idx):
return self.lod[idx][self.key]
lookfor = listofdicts[len(listofdicts)//2]['dt']
def mid(res=listofdicts, target=lookfor):
keys = [r['dt'] for r in res]
return res[bisect.bisect_left(keys, target)]
def midi(res=listofdicts, target=lookfor):
wrap = Indexer(res, 'dt')
return res[bisect.bisect_left(wrap, target)]
if __name__ == '__main__':
print '%d dicts on the list' % len(listofdicts)
print 'Looking for', lookfor
print mid(), midi()
assert mid() == midi()
Die Ausgabe (gerade ausgeführt indexer.py als Kontrolle, dann mit timeit (zwei Möglichkeiten):
$ python indexer.py
145 dicts on the list
Looking for 2009-06-15T12:00:00
{'dt': '2009-06-15T12:00:00'} {'dt': '2009-06-15T12:00:00'}
$ python -mtimeit -s'import indexer' 'indexer.mid()'
10000 loops, best of 3: 27.2 usec per loop
$ python -mtimeit -s'import indexer' 'indexer.midi()'
100000 loops, best of 3: 9.43 usec per loop
Wie Sie sehen, kann der indirekte Ansatz selbst bei einer bescheidenen Aufgabe mit 145 Einträgen in der Liste eine dreimal bessere Leistung erzielen als der Ansatz "Schlüsselextraktionsdurchgang". Da wir O(N) mit O(log N) vergleichen, wächst der Vorteil des Indirektionsansatzes unbegrenzt mit zunehmendem N. (Für sehr kleine N machen die höheren multiplikativen Konstanten aufgrund der Indirektion den Schlüsselextraktionsansatz schneller, aber dies wird bald durch den Big-O Unterschied übertroffen). Zugegeben, die Indexer-Klasse ist zusätzlicher Code - aber sie ist wiederverwendbar für ALLE Aufgaben der binären Suche in einer Liste von Dicts, die nach einem Eintrag in jedem Dict sortiert sind, so dass es sich lohnt, sie in den "Container-Utilities Back of Tricks" zu haben.
So viel zur Hauptsuchschleife. Für die sekundäre Aufgabe, zwei Einträge (den direkt unter und den direkt über dem Ziel) und das Ziel in eine Anzahl von Sekunden umzuwandeln, ist wiederum ein Ansatz mit höherer Wiederverwendung zu erwägen, nämlich:
import time
adt = '2009-09-10T12:00:00'
def dttosecs(dt=adt):
# string to seconds since the beginning
date,tim = dt.split('T')
y,m,d = date.split('-')
h,mn,s = tim.split(':')
y = int(y)
m = int(m)
d = int(d)
h = int(h)
mn = int(mn)
s = min(59,int(float(s)+0.5)) # round to neatest second
s = int(s)
secs = time.mktime((y,m,d,h,mn,s,0,0,-1))
return secs
def simpler(dt=adt):
return time.mktime(time.strptime(dt, '%Y-%m-%dT%H:%M:%S'))
if __name__ == '__main__':
print adt, dttosecs(), simpler()
assert dttosecs() == simpler()
Hier gibt es keinen Leistungsvorteil für die Wiederverwendung (im Gegenteil, dttosecs schneller ist) - aber dann müssen Sie nur drei Konvertierungen pro Suche durchführen, egal wie viele Einträge in Ihrer Dict-Liste sind, also ist es nicht klar, ob dieses Leistungsproblem von Bedeutung ist. Inzwischen, mit simpler müssen Sie nur eine einfache Codezeile schreiben, testen und pflegen, während dttosecs ist ein Dutzend Zeilen; angesichts dieses Verhältnisses würde ich in den meisten Situationen (d. h. unter Ausschluss absoluter Engpässe) die simpler . Wichtig ist, dass man sich der beiden Ansätze und der Kompromisse zwischen ihnen bewusst ist, um sicherzustellen, dass man eine kluge Wahl trifft.
