простой способ для поиска списка по целому числу временные метки

Question

У меня есть список записей лесозаготовительных вида:

[{'time': 199920331000, 'message': 'message1'}, {'time': 199920331001, 'message': 'message2'}...] 

где значение времени постоянно растет список. Если я хочу, чтобы получить журналы позже, чем заданное метку времени, я мог ходить элементы, пока я не вижу время штамповать больше заданной временной метки:

def getLog(timestamp): 
    global logs 
    for x in range(len(logs)): 
     if logs[x]['time'] > timestamp: 
      return logs[x:] 
    return [] 

Я предполагаю, что это уже быстрый механизм поиска в Python 3, но дон Не знаю, где искать.

Answer 1

Если вы правильно поняли, вы ищете bisect module, который реализует эффективный алгоритм поиска точки, в которой значение в отсортированном списке больше или меньше заданного значения.

Ваши записи в журнале должны быть классом, который реализует какую-либо форму заказа. Что-то вроде этого:

from functools import total_ordering 

@total_ordering 
class LogEntry(object): 
    def __init__(self, time, message): 
     self.time = time 
     self.message = message 

    def __eq__(self, other): 
     if not isinstance(other, self.__class__): 
      return NotImplemented 
     return self.time == other.time and self.message == other.message 

    def __lt__(self, other): 
     if not isinstance(other, self.__class__): 
      return NotImplemented 
     if self.time == other.time: 
      return self.message < other.message 
     return self.time < other.time 

Эти LogEntry классы упорядочиваема (с помощью functools.total_ordering class decorator), и, таким образом, bisect модуль знает, что записи имеют «более низкое» значение по сравнению с другими значениями.

Ваша функция становится:

def getLog(timestamp): 
    dummy_entry = LogEntry(timestamp, '') 
    index = bisect.bisect_right(logs, dummy_entry) 
    return logs[index:] 

Обратите внимание, что мы не должны объявить logs глобальный, как вы не назначая ему.

Answer 2

Если вы знаете, что время всегда увеличивается, вы можете гарантировать, что ваш список отсортирован. Тогда я хотел бы использовать ответ от here и попытаться адаптировать его, как это:

def binary_search(log_list, timestamp, lo=0, hi=None): 
    if hi is None: 
     hi = len(log_list) 
    while lo < hi: 
     mid = (lo+hi)//2 
     midval = log_list[mid]['time'] 
     if midval < timestamp: 
      lo = mid+1 
     elif midval > timestamp: 
      hi = mid 
     else: 
      return mid 
    return -1 

(не проверял, хотя)

Answer 3

Учитывая, что Python пытается b.__gt__(a) когда a.__lt__(b) не реализован вы не» т необходимо изменить класс записи в журнале, она должна быть достаточной, чтобы обеспечить достаточно смарт-ключа:

import bisect 
from functools import total_ordering 
from operator import itemgetter 

log = [ 
    {'time': 199920331000, 'message': 'message1'}, 
    {'time': 199920331001, 'message': 'message2'}, 
    # ... 
] 

@total_ordering 
class Key(object): 
    def __init__(self, keyfunc, keyval): 
     self.keyfunc = keyfunc 
     self.keyval = keyval 

    def __eq__(self, other): 
     return self.keyval == self.keyfunc(other) 

    def __lt__(self, other): 
     return self.keyval < self.keyfunc(other) 

start = bisect.bisect(log, Key(itemgetter("time"), 199920331000)) 
print log[start:] 

в качестве альтернативы вы можете обернуть вокруг представления списка dicts:

def keyed(items, key): 
    class View(object): 
     def __getitem__(self, index): 
      return key(items[index]) 
     def __len__(self): 
      return len(items) 
    return View() 

start = bisect.bisect(keyed(log, itemgetter("time")), 199920331000) 
print log[start:] 

(Это урезанная от Smart way to delete tuples)