Python：更新元组列表...最快方法

Question

这个问题和这里的另一个问题有关：如何在Python中排序100万条记录

我现在已经搞清楚了我在排序时遇到的问题。我每次更新数据时，都是把字典里的项目排序到一个列表里。后来我意识到，Python的排序功能很强大，特别是在处理已经部分排序的数据时，它的速度会更快。

那么，问题来了。假设我有以下这个样本数据：

self.sorted_records = [(1, 1234567890), (20, 1245678903), 
                       (40, 1256789034), (70, 1278903456)]

列表中每个元组的t[1]都是一个唯一的ID。现在我想用以下数据更新这个列表：

updated_records = {1245678903:45, 1278903456:76}

我想知道最快的更新方法是什么，最后得到的结果是：

self.sorted_records = [(1, 1234567890), (45, 1245678903),
                       (40, 1256789034), (76, 1278903456)]

目前我正在做的事情是这样的：

updated_keys = updated_records.keys()
for i, record in enumerate(self.sorted_data):
    if record[1] in updated_keys:
        updated_keys.remove(record[1])
        self.sorted_data[i] = (updated_records[record[1]], record[1])

但我相信一定有更快、更优雅的解决方案。

有人能帮帮我吗？

* 编辑 结果我用的ID示例不太好，因为在我更新时它们会变成排序好的顺序。其实我更关心的是t[0]的排序。在更新后，我本来打算重新排序更新的数据，但看起来使用bisect模块可能是个好办法，可以按顺序插入。 编辑结束 *

Answer 1

在这种情况下，使用某种树结构可能是最好的选择，这样可以保持排序的同时，实现O(log n)的替换速度。虽然Python没有内置的平衡树类型，但你可以找到很多第三方的例子。或者，你可以选择以下两种方法：

1. 使用二分查找来找到节点。Python的bisect模块可以做到这一点，但它是根据普通的比较顺序来比较的，而你似乎是根据每个元组的第二个元素来排序的。你可以反转这个顺序，或者自己写一个二分查找（或者直接拿bisect_left的代码来修改一下）。

2. 同时使用字典和列表。列表只包含已排序的键。你可以很容易地封装字典类，以确保它们保持同步。这样可以让你快速更新字典，同时保持键的排序。这可以避免因为在字典和列表之间不断转换而导致的排序性能下降。

下面是这种方法的一个简单实现：

import bisect

class SortedDict(dict):
    """Dictionary which is iterable in sorted order.

    O(n) sorted iteration
    O(1) lookup
    O(log n) replacement  ( but O(n) insertion or new items)
    """

    def __init__(self, *args, **kwargs):
        dict.__init__(self, *args, **kwargs)
        self._keys = sorted(dict.iterkeys(self))

    def __setitem__(self, key, val):
        if key not in self:
            # New key - need to add to list of keys.
            pos = bisect.bisect_left(self._keys, key)
            self._keys.insert(pos, key)
        dict.__setitem__(self, key, val)

    def __delitem__(self, key):
        if key in self:
            pos = bisect.bisect_left(self._keys, key)
            del self._keys[pos]
        dict.__delitem__(self, key)

    def __iter__(self):
        for k in self._keys: yield k
    iterkeys = __iter__

    def iteritems(self):
        for k in self._keys: yield (k, self[k])

    def itervalues(self):
        for k in self._keys: yield self[k]

    def update(self, other):
        dict.update(self, other)
        self._keys = sorted(dict.iterkeys(self)) # Rebuild (faster if lots of changes made - may be slower if only minor changes to large dict)

    def keys(self): return list(self.iterkeys())
    def values(self): return list(self.itervalues())
    def items(self): return list(self.iteritems())

    def __repr__(self):
        return "%s(%s)" % (self.__class__.__name__, ', '.join("%s=%r" % (k, self[k]) for k in self))

Answer 2

你正在查看所有的n条记录。其实你可以用二分查找，这样效率会更高，时间复杂度是O(log(n))，而不是O(n)。你可以使用bisect模块来实现这个功能。

Answer 3

看起来你并不在乎 self.sorted_records 最终的值是否真的被排序了（你现在的值是 1, 45, 20, 76 -- 这可不是排序好的！），而且你只关心 updated_records 中的 ID 是否也在 self.sorted_data 中，所以用列表推导式（如果你想实时修改 updated_record 的话）会对你很有帮助，也就是说：

self.sorted_data = [(updated_records.pop(recid, value), recid) 
                    for (value, recid) in self.sorted_data]

这里的 .pop 调用会从 updated_records 中移除那些最终会出现在新的 self.sorted_data 中的键（和对应的值），而且“那个 recid 的之前的值” value 会作为 pop 的第二个参数传入，以确保当 recid 不在 updated_record 中时不会发生变化）；这样就会把 updated_record 中的“新”内容留下来，比如你可以在重新排序之前把它添加到 self.sorted_data 中，也就是说我猜你想继续做类似这样的事情：

self.sorted_data.extend(value, recid 
                        for recid, value in updated_records.iteritems())
self.sorted_data.sort()

不过这部分确实超出了你实际提问的内容（我之所以提到是因为我看过你之前的问题;-）。