«Копирование и вставка кодирования» (получение исходных кодов bisect в ваш код) не рекомендуется, так как оно несет все виды затрат в будущем (много дополнительного исходного кода для тестирования и сопровождения, трудности, связанные с обновления в исходном коде, который вы скопировали и т. д. и т. п.); лучший способ повторно использовать стандартные библиотечные модули - просто импортировать их и использовать их.
Однако, чтобы сделать один проход, преобразовать словари в значимо сравнимые записи - это O (N), что (хотя каждый шаг прохода прост) в конечном итоге затмевает время O (log N) собственно поиска. Поскольку bisect не может поддерживать key= средство извлечения ключей, как sort, то как решить эту дилемму - как вы можете повторно использовать bisect при импорте и вызове без предварительного шага O (N). .
Как указано здесь , решение заключается в известной поговорке Дэвида Уилера: «Все проблемы в информатике могут быть решены с помощью другого уровня косвенности». Рассмотрим, например, ....:
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()
Вывод (просто запустив этот indexer.py в качестве проверки, затем с timeit, двумя способами):
$ 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
Как видите, даже в скромной задаче с 145 записями в списке подход с косвенной адресацией может иметь производительность, которая в три раза лучше, чем метод "прохода извлечения ключа". Поскольку мы сравниваем O (N) с O (log N), преимущество подхода косвенности растет без границ с ростом N. (Для очень малого N более высокие мультипликативные константы из-за косвенности делают подход извлечения ключей более быстрым, но вскоре он превосходит разницу больших-O). Следует признать, что класс Indexer - это дополнительный код, однако его можно повторно использовать во ВСЕХ задачах двоичного поиска в списке диктов, отсортированных по одной записи в каждом из них, поэтому наличие его в «контейнерах утилит-контейнеров» дает хороший результат. инвестиции.
Так много для основного цикла поиска. Для вторичной задачи преобразования двух записей (одна чуть ниже, а другая чуть выше цели) и цели в количество секунд, снова рассмотрим подход с более высоким повторным использованием, а именно:
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()
Здесь нет никакого преимущества в производительности для подхода повторного использования (действительно, и наоборот, dttosecs быстрее) - но тогда вам нужно всего лишь выполнить три преобразования за поиск, независимо от того, сколько записей включено. ваш список диктов, так что не ясно, является ли эта проблема производительности уместной. Между тем, с simpler вам нужно только написать, протестировать и поддерживать одну простую строку кода, тогда как dttosecs - это дюжина строк; учитывая это соотношение, в большинстве ситуаций (т.е. без учета абсолютных узких мест) я бы предпочел simpler. Важно знать оба подхода и компромиссы между ними, чтобы гарантировать, что выбор сделан мудро.