搜索由整数排序的列表简单的方法时间戳

我有如下形式的日志条目列表：搜索由整数排序的列表简单的方法时间戳

[{'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，但穿上快速搜索机制不知道去哪里看。

来源

2012-09-13 Max

如果我的理解正确，您正在寻找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全球你不是分配给它。

来源

2012-09-13 11:18:37

如果您知道时间总是增加，您可以保证您的列表已排序。然后我会使用的答案从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

（没有测试虽然）

来源

2012-09-13 11:30:58

虽然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:]

另外，您可以环绕类型的字典列表视图：

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剥离下来）

来源

2012-09-13 12:37:32

搜索由整数排序的列表简单的方法时间戳

回答

相关问题