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

这个问题是相对于另一个问题在这里问： Sorting 1M records 的Python：更新一个元组列表...最快的方法

因为我已经想通了，我与排序遇到的问题。每次更新数据时，我都会将字典中的项目排列成列表。后来我意识到，Python排序的很多功能在于它能够更快地对已经部分排序的数据进行排序。

所以，这是问题。假设我有以下内容作为样本集：

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

列表中的每个元组的t[1]是一个唯一的ID。现在我想更新此名单与follwoing：

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

但我确信有一个更快，更优雅的解决方案。

任何帮助？

*编辑原来我用坏exaples的IDS，因为他们最终的排序顺序，当我做我的更新。我实际上对t [0]按排序顺序感兴趣。在执行更新之后，我打算使用更新后的数据，但它看起来像平分线可能是按排序顺序插入的票据。结束编辑*

来源

2009-07-27 sberry

措施小心（溶液在我的答案详细编码，在Brian的，以及有关平分模糊的建议），因为的.sort是通常令人惊讶的快（尤其是已经大部分排序的数据），而对分几乎没有什么好处。 – 2009-07-27 15:05:55

因为显然你不关心的self.sorted_records实际上为排序的终止值（有价值观，以1，45，20，76 - 这是没有排序 - ！），你只出现关心关于updated_records这也是self.sorted_data的ID，一个listcomp（有副作用，如果你想改变在运行过程中updated_record）将竭诚为您服务好，即：

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

的.pop调用从updated_records键（和相应的值），结束于新的self.sorted_data（以及“的先前值“，value，作为弹出的第二个参数提供，以确保在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()

虽然这部分工作超越你的问题其实只是因为我看到你的之前的问题;（）我只是给它。

来源

2009-07-27 05:11:33

您正在扫描所有n条记录。你可以做一个二进制搜索，这将是O（log（n））而不是O（n）。您可以使用bisect模块执行此操作。

来源

2009-07-27 05:07:28

只有插入到已排序的数组中才有`bisect`？如何使用它来进行搜索？ – 2009-07-27 05:29:22

bisect用于搜索数组，插入是常见用例。这只是一个二分查找;在许多人意识到的情况下，在所有情况下都是正确的，所以在标准库中使用它是很有意义的。 – 2009-07-27 05:39:48

既然你想用字典键来替换，但是按字典值排序数组，你绝对需要线性搜索键。从这个意义上说，你的算法是你所期望的最好的。

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

来源

2009-07-27 05:13:55

你可能最好在这里使用某种形式的树（保留排序顺序，同时允许O（log n）替换）。没有内置的树型树，但你可以找到很多第三方的例子。或者，您可以：

使用二进制搜索来查找节点。平分模块会执行此操作，但它会根据正常的python比较顺序进行比较，而您似乎基于每个元组的第二个元素进行排序。您可以反转这一点，或者只是编写自己的二进制搜索（或简单地从bisect_left获取代码并修改它）
同时使用字典和的列表。该列表仅包含排序的键。你可以很容易地包装dict类，以确保它保持同步。这使您可以快速更新字典，同时保持键的排序顺序。这应该可以防止由于字典/列表之间的不断转换而导致丢失排序性能的问题。

这里有一个快速的实现了这样的事情：

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

来源

2009-07-27 13:04:32 Brian

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

回答

相关问题