python:更新元组列表…最快的方法

因为显然你不在乎 self.sorted_records 事实上 存在 排序(值的顺序是1、45、20、76——这是不排序的!-,而您似乎只关心中的ID updated_records 那也是在 self.sorted_data ,listcomp(如果您想动态更改更新的记录,则带有副作用)将为您提供很好的服务,即:

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

这个 .pop 呼叫从中删除 更新的记录 结束于新的 自排序数据 (以及“以前的价值” recid “ value ,作为pop的第二个参数提供,以确保不更改recid所在的位置。 updated_record );这个离开 更新的记录 “新”内容,以便您可以将其附加到 自排序数据 在重新排序之前,我怀疑你想继续

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

尽管这一部分确实超出了你实际提出的问题(我给出它只是因为我见过你 以前的 问题;-)

您正在扫描所有n条记录。您可以执行二进制搜索,它是O(日志(n))而不是O(n)。你可以使用 bisect 要执行此操作的模块。

这里的某种形式的树(保留排序顺序,同时允许O(log n)替换)可能最适合您。没有内置的平衡树类型,但您可以找到许多第三方示例。或者,您可以:

1. 使用二进制搜索查找节点。二分法模块将这样做,但它是基于正常的Python比较顺序进行比较的,而您似乎是基于每个元组的第二个元素进行排序的。你可以逆转这个过程,或者只写你自己的二进制搜索(或者简单地从二分法左取代码并修改它)

2. 二者兼备 和 一览表。列表包含已排序的 钥匙 只有。您可以轻松地包装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))

由于您希望用字典键替换,但要用字典值对数组进行排序,因此您肯定需要对该键进行线性搜索。从这个意义上说,你的算法是你所能期望的最好的。

如果要保留旧字典的值,则可以使用二进制搜索该值,然后在二进制搜索引导您的位置附近找到键。