Python保持排序数据的最有效方法

Question

按升序/降序跟踪数据的最有效方法是什么。假设我有一个数据流，假设它非常大。示例流:

key,mod,value
5,add,1
2,add,3
4,add,2
2,add,2
2,rem,5

当我阅读流时，我将其放入字典中以跟踪内容。例如，在上面的迷你流的末尾，我将有一个包含 {5:1, 4:2} 的字典。其中 add 表示该值增加了该值，而 rem 表示您要从该键中删除那么多。如果该值变为 0，则从字典中删除该键。但我也希望能够按顺序打印数据(但不必一直如此。)我确实想跟踪最高/最低键，以便我知道最高/最低值何时发生变化。 key 已更改或其值已更改。

我现在的做法是相应地从字典中填充/删除键。这应该是常数 O(1)。跟踪 sorted_keys 列表，其中每个流检查新数字是否在字典中，如果不在，将执行 bisect.insort_right(sorted_keys, key)。所以 sorted_keys 始终是排序的。假设在排序列表中添加 1 个值很快，尽管它确实需要扩展大小，所以这可能仍然需要 O(n)。我跟踪 prev_highest 或 prev_lowest，并分别对照 sorted_keys[0] 或 sorted_keys[-1] 检查它。

我尝试将双端队列与 bisect.insort_right、来自 sortedcontainers 的 SortedDict、链表、OrderedDict 一起使用，但似乎上面的方法效果最好。是否有另一种可以更优化的潜在实现？或者我应该按顺序跟踪某个级别，比如按顺序跟踪 10 个项目。并相应地更新它。但问题是，如果有一把新 key ，我怎么知道它是不是新 key ？似乎有一个 heapq 会有所帮助，但在弹出它们之前我无法获得排序的值。如果我需要按顺序打印整个内容，我只需对整个字典的键进行排序。

编辑:在下面使用 bisect 和 SortedDict 添加我的测试:

import timeit
import bisect
import random
from sortedcontainers import SortedDict

NUM_ITERATION_TEST = 10
TOTAL_NUM_DATA = 1000000
MODS = ['add', 'rem']
QUANTITY = [1, 5, 10, 20, 100, 200, 300, 500, 1000]

DATA = [{'mod': random.choice(MODS),
         'key': random.randint(0, 1000),
         'val': random.choice(QUANTITY)} for x in range(TOTAL_NUM_DATA)]


def method1(DATA):
    d = {}
    sorted_keys = []

    for data in DATA:
        if data['mod'] == 'add':
            key = data['key']
            if key in d.keys():
                d[key] += data['val']
            else:
                d[key] = data['val']
                bisect.insort_right(sorted_keys, key)
        elif data['mod'] == 'rem':
            key = data['key']
            if key in d.keys():
                if d[key] <= data['val']:
                    del d[key]
                    sorted_keys.remove(key)           
                else:
                    d[key] -= data['val']
            else:
                pass # Deleting something not there yet

def method2(DATA):
    d = SortedDict()

    for data in DATA:
        if data['mod'] == 'add':
            key = data['key']
            if key in d.keys():
                d[key] += data['val']
            else:
                d[key] = data['val']
        elif data['mod'] == 'rem':
            key = data['key']
            if key in d.keys():
                if d[key] <= data['val']:
                    del d[key]
                else:
                    d[key] -= data['val']
            else:
                pass  # Deleting something not there yet


if __name__ == "__main__":
    # METHOD 1
    print("Method 1 Execution Time:")
    print(timeit.timeit("test_timeit.method1(test_timeit.DATA)",
                        number=NUM_ITERATION_TEST,
                        setup="import test_timeit"))

    # METHOD 2
    print("Method 2 Execution Time:")
    print(timeit.timeit("test_timeit.method2(test_timeit.DATA)",
                        number=NUM_ITERATION_TEST,
                        setup="import test_timeit"))

上面的结果是:

Method 1 Execution Time:
4.427699800000001
Method 2 Execution Time:
12.7445671

Answer 1

对于适合内存的数据，“SortedDict from sortedcontainers”(您已经尝试过)通常可以很好地保持这样的字典按排序顺序排列。但是查找时间(大致)是 O(log N)(请参阅末尾的编辑 - 这似乎是错误的!)。

Assuming adding 1 value in a sorted list is quick, though it does need to extend the size so this may take O(n) still.

在 Python 列表 L 中，在索引 i 处插入一个元素必须 - 至少 - 物理移动 len(L) - i 指针，这意味着 64 位盒子上字节数的 8 倍。这就是 sortedcontainers 在数据变得“大”时获得巨大优势的地方:它需要物理移动的指针的最坏情况数量受一个独立于 len(L) 的常数的限制。在 len(L) 达到数千之前，很难注意到差异。但是当 len(L) 达到数百万时，差异就很大了。

我会尝试折衷:使用 sortedcontainers SortedList 来跟踪当前键，并使用普通的 Python 字典来记录实际的字典。然后:

对于“key add value”:看key是否在dict中。非常快。如果是，则无需触摸 SortedList。只是改变字典。如果键不在字典中，则需要将其添加到 SortedList 和字典中。

对于“key rem value”:查看字典中的key。如果不是，我不知道你想做什么，但你会想出来的 ;-) 但如果它在字典中，请减去该值。如果结果不为零，你就完成了。否则(结果为 0)，从字典和 SortedList 中删除键。

注意:我建议使用 SortedList 而不是 SortedSet 不是出于语义原因，而是因为 SortedSet 需要更多内存，以便与排序列表并行维护一个集合。你对这套没用。

除了字典之外，您可能真正想要的是 double-ended ("min max") heap .从您所说的内容中猜测是不可能的 - 这取决于，例如，与您想要具体化整个排序顺序的频率相比，您只想知道“最小和/或最大”的频率。但我不知道为速度而构建的 Python 最小-最大堆实现 - 它们是编码的困惑野兽，很少使用。

编辑

再三考虑，sortedcontainer 的 SortedDict 似乎已经将 SortedList 与普通 Python dict(的子类)组合在一起。例如，在 SortedDict 中设置一个值是这样实现的:

def __setitem__(self, key, value):
    if key not in self:
        self._list_add(key)
    dict.__setitem__(self, key, value)

因此，如果键不在字典中，它只会触及 SortedList。如果您维护自己的 对，就没有 太多改进的机会。

自己动手

这是另一个尝试:

def method3(DATA):
    sorted_keys = SortedList()
    d = {}

    for data in DATA:
        if data['mod'] == 'add':
            key = data['key']
            if key in d:
                d[key] += data['val']
            else:
                d[key] = data['val']
                sorted_keys.add(key)
        elif data['mod'] == 'rem':
            key = data['key']
            if key in d:
                if d[key] <= data['val']:
                    del d[key]
                    sorted_keys.remove(key)
                else:
                    d[key] -= data['val']
            else:
                pass  # Deleting something not there yet

这实现了我最初的建议:使用普通 Python dict 维护你自己的一对 SortedList。它具有与使用 SortedDict 相同的 O() 行为，但显示速度明显快于常数因子。这似乎部分是因为 dict 操作现在都是用 C 编码的(SortedDict 是用 Python 编码的)，其余部分是因为我们只为每个 data 项测试一次 dict 成员资格。例如，在

if key in d:
    d[key] += data['val']

当 d 是一个 SortedDict 时，key in d 显式测试一次，但是 d.__setitem__() 的实现必须测试再次调用它，以便它可以在键未知时将 key 添加到其隐藏的 SortedList 中。从更高层次的角度来看，我们已经知道键在 if 正文中的字典中，因此可以完全忽略我们显式的 SortedList。