3

次の形式のログ エントリのリストがあります。

[{'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 には既にクイック検索メカニズムがあると思いますが、どこを見ればよいかわかりません。

4

3 に答える 3

4

bisect私があなたを正しく理解していれば、あなたはモジュールを探しています。これは、ソートされたリスト内の値が特定の値よりも大きいまたは小さいポイントを見つけるための効率的なアルゴリズムを実装しています。

ただし、ログ エントリは、何らかの形式の順序付けを実装するクラスである必要があります。このようなもの：

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_orderingbisect

関数は次のようになります。

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

logsグローバルに割り当てていないため、グローバルを宣言する必要がないことに注意してください。

于 2012-09-13T11:18:37.920 に答える
2

b.__gt__(a)が実装されていないときに Python が試行することを考えると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:]

別の方法として、dict のリストをビューでラップすることもできます。

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-13T12:37:32.530 に答える
1

時間が常に増加することがわかっている場合は、リストがソートされていることを保証できます。次に、ここからの回答を使用して、次のように適応させます。

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-13T11:30:58.640 に答える