这个问题与这里提出的另一个问题有关: Sorting 1M records
从那时起,我就发现了分类的问题。每次更新数据时,我都会把字典里的条目整理成一个列表。我后来意识到Python排序的强大之处在于它可以更快地对已经部分排序的数据进行排序。在
所以,问题来了。假设我有以下示例集:
self.sorted_records = [(1, 1234567890), (20, 1245678903),
(40, 1256789034), (70, 1278903456)]
列表中每个元组的t[1]
都是唯一的id。现在我想用以下内容更新此列表:
对我来说,最快的方法是什么
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可能是按排序顺序插入的罚单。 结束编辑*
因为显然你不关心
self.sorted_records
的结束值,实际上是被排序的(你有顺序为1、45、20、76的值——这不是排序的!-),而且您似乎只关心updated_records
中的id,而listcomp(如果您想动态更改更新的记录,则会有副作用)会很好地为您服务,例如:
^{pr2}$.pop
调用从updated_records
中删除结束于新的self.sorted_data
中的键(和相应的值),“recid
”的前一个值,value
,作为pop的第二个参数提供给pop,以确保在updated_record
中没有recid时不会发生任何更改;这样就留下了updated_record
中的“新”内容,这样您可以在重新排序之前将其附加到self.sorted_data
中,也就是说,我怀疑您想继续类似的操作尽管这一部分确实超出了你实际提出的问题(我之所以给出它只是因为我看过你以前的问题;-)。在
你正在扫描所有n条记录。您可以改为执行二进制搜索,即O(log(n))而不是O(n)。您可以使用^{} 模块来执行此操作。在
这里可能最好使用某种形式的树(在允许O(logn)替换的同时保持排序顺序)。或者,您可以:
使用二进制搜索查找节点。bisect模块将执行此操作,但它基于普通python比较顺序进行比较,而您似乎是根据每个元组的第二个元素进行排序的。您可以将其颠倒过来,或者编写自己的二进制搜索(或者简单地从左二等分取代码并进行修改)
同时使用dict和列表。该列表只包含排序的键。您可以很容易地包装dict类,以确保它保持同步。这允许您在保持键的排序顺序的同时快速更新dict。这可以防止由于dict/list之间的不断转换而导致排序性能下降的问题。
下面是这样一件事的快速实现:
相关问题 更多 >
编程相关推荐