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

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 声明为全局的，因为您没有分配给它。