Python:更新元组列表。。。最快方法

Question

这个问题与这里提出的另一个问题有关： Sorting 1M records

从那时起，我就发现了分类的问题。每次更新数据时，我都会把字典里的条目整理成一个列表。我后来意识到Python排序的强大之处在于它可以更快地对已经部分排序的数据进行排序。在

所以，问题来了。假设我有以下示例集：

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

列表中每个元组的t[1]都是唯一的id。现在我想用以下内容更新此列表：

^{pr2}$

对我来说，最快的方法是什么

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（logn）替换的同时保持排序顺序）。或者，您可以：

1. 使用二进制搜索查找节点。bisect模块将执行此操作，但它基于普通python比较顺序进行比较，而您似乎是根据每个元组的第二个元素进行排序的。您可以将其颠倒过来，或者编写自己的二进制搜索（或者简单地从左二等分取代码并进行修改）

2. 同时使用dict和列表。该列表只包含排序的键。您可以很容易地包装dict类，以确保它保持同步。这允许您在保持键的排序顺序的同时快速更新dict。这可以防止由于dict/list之间的不断转换而导致排序性能下降的问题。

下面是这样一件事的快速实现：

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))