在Python中排序100万条记录的最佳方式

Question

myLists = 

    {
      'hits': {'id1':200, 'id2':300, 'id3':100},
      'misses': {'id1':300, 'id2':100, 'id3':400},
      'total': {'id1':400, 'id2':500, 'id3':600}
    }

我有一个服务，它会处理大约一百万个字典（可以理解为一种数据结构，像是一个个小表格），并执行以下操作：

myHashTable = {}
myLists = { 'hits':{}, 'misses':{}, 'total':{} }
sorted = { 'hits':[], 'misses':[], 'total':[] }
for item in myList:
  id = item.pop('id')
  myHashTable[id] = item
  for k, v in item.iteritems():
    myLists[k][id] = v

假设我有以下这些字典的列表：

[ {'id':'id1', 'hits':200, 'misses':300, 'total':400},
  {'id':'id2', 'hits':300, 'misses':100, 'total':500},
  {'id':'id3', 'hits':100, 'misses':400, 'total':600}
]

最后我得到的是：

myHashTable =
{ 
  'id1': {'hits':200, 'misses':300, 'total':400},
  'id2': {'hits':300, 'misses':100, 'total':500},
  'id3': {'hits':100, 'misses':400, 'total':600}
}

然后我需要对每个 myLists 字典中的所有数据进行排序。

目前我做的事情大概是这样的：

def doSort(key):
  sorted[key] = sorted(myLists[key].items(), key=operator.itemgetter(1), reverse=True)

which would yield, in the case of misses:
[('id3', 400), ('id1', 300), ('id2', 200)] 

当记录数量在十万条左右时，这个方法效果很好，但当达到一百万条时，每次排序都需要至少5到10分钟，而我的字典列表总共有16个字段（其实原始字典列表有17个字段，包括被移除的id）。

* 编辑 * 这个服务是一个 ThreadingTCPServer，它有一个方法可以让客户端连接并添加新数据。新数据可能包括新记录（也就是有独特 'id' 的字典，和内存中已有的不同）或者修改过的记录（也就是 'id' 相同但其他数据不同的字典）。

所以，一旦这个服务运行起来，我会传入：

[
  {'id':'id1', 'hits':205, 'misses':305, 'total':480},
  {'id':'id4', 'hits':30, 'misses':40, 'total':60},
  {'id':'id5', 'hits':50, 'misses':90, 'total':20
]

我一直在使用字典来存储数据，这样就不会出现重复的记录。在字典更新了新数据或修改数据后，我会对它们重新排序。

* 编辑结束 *

那么，排序这些数据的最佳方法是什么呢？有没有更好的方法？

Answer 1

这看起来挺快的。

raw= [ {'id':'id1', 'hits':200, 'misses':300, 'total':400},
    {'id':'id2', 'hits':300, 'misses':100, 'total':500},
    {'id':'id3', 'hits':100, 'misses':400, 'total':600}
]

hits= [ (r['hits'],r['id']) for r in raw ]
hits.sort()

misses = [ (r['misses'],r['id']) for r in raw ]
misses.sort()

total = [ (r['total'],r['id']) for r in raw ]
total.sort()

是的，它会对原始数据进行三次处理。我觉得这样比一次性提取数据要快。

Answer 2

你真正想要的是一个有序的容器，而不是无序的。这样的话，插入数据的时候就会自动排序。通常用来实现这个功能的数据结构是树。

不过，在Python中似乎没有这样的结构。我也说不清楚为什么；在任何编程语言中，这都是一个核心的基本数据类型。Python的字典（dict）和集合（set）都是无序的容器，它们对应的基本数据结构是哈希表。其实Python应该有一个优化过的树形数据结构，因为用树可以做很多哈希表做不到的事情，而且实现起来也比较复杂，所以大家一般不想自己去做。

（另外，Python中也没有对应链表的结构，这也是一个应该有的基本数据类型。不是的，双端队列（deque）并不等同于链表。）

我没有现成的有序容器的实现可以推荐给你（而且它应该是原生实现，而不是用Python写的），但希望这些信息能给你一些启发。

一个好的树形实现应该支持按值遍历范围（比如“按顺序遍历所有值从[2,100]”），从任何节点找到下一个或上一个值的时间复杂度是O(1)，高效的范围提取（比如“删除所有值在[2,100]之间的，并把它们放到一个新树里”）等等。如果有人有这样的优化过的数据结构在Python中，我很想知道。（并不是所有操作都能很好地适应Python的数据模型；例如，要从另一个值获取下一个或上一个值，你需要一个节点的引用，而不是值本身。）

Answer 3

你可以看看Guido的这个相关回答： 用Python在2MB内存中排序一百万个32位整数