Python: Zope的BTree OOSet、IISet等... 适合这个需求吗？
我问了另一个问题：https://stackoverflow.com/questions/1180240/best-way-to-sort-1m-records-in-python，我想找出排序100万条记录的最佳方法。在我的情况下，我需要能够向集合中添加额外的项目，并让它们重新排序。有人建议我尝试使用Zope的BTrees来完成这个任务。看了一些资料后，我对应该在集合中放什么数据有点困惑。
简单来说，对于每条记录，我有两部分数据。1. 一个唯一的ID，代表一个用户；2. 一个用于排序的值。
我看到可以将这些项目作为元组添加到一个OOSet中，其中用于排序的值在索引0的位置。所以，比如说(200, 'id1'),(120, 'id2'),(400, 'id3')，结果集合会按照id2, id1和id3的顺序排序。
但是，要求之一是每个ID在集合中只能出现一次。我会定期向集合中添加额外的数据，而新数据可能会包含重复的'ids'。如果有重复的ID，我想更新它的值，而不是添加一个新的条目。所以，基于上面的元组，我可能会添加(405, 'id1'),(10, 'id4')到集合中，并希望输出的顺序是id4, id2, id3, id1。
有没有什么建议可以实现这个目标？抱歉我对这个主题还不太熟悉。
* 编辑 - 额外信息 *
这里是项目中的一些实际代码：
for field in lb_fields:
t = time.time()
self.data[field] = [ (v[field], k) for k, v in self.foreign_keys.iteritems() ]
self.data[field].sort(reverse=True)
print "Added %s: %03.5f seconds" %(field, (time.time() - t))
foreign_keys是原始数据，以字典形式存储，每个ID作为键，额外数据的字典作为值。data是一个包含已排序数据列表的字典。
顺便提一下，随着每次for field in lb_fields的迭代，排序所需的时间会增加——虽然增加不多，但还是能感觉到。对每个16个字段排序100万条记录后，大约使用了4GB的内存。最终这将在一台有48GB内存的机器上运行。
2 个回答
解决你的问题是完全可能的。你只需要记住，Python中的容器类型总是通过调用对象的方法来比较对象。因此，你可以这样做：
class Record:
'Combination of unique part and sort part.'
def __init__(self, unique, sort):
self.unique = unique
self.sort = sort
def __hash__(self):
# Hash should be implemented if __eq__ is implemented.
return hash(self.unique)
def __eq__(self, other):
return self.unique == other.unique
def __lt__(self, other):
return self.sort < other.sort
records = btree((Record(u, s) for u, s in zip(unique_data, sort_data)))
print(records.pop())
注意事项：
- 根据你喜欢的容器类型的实现方式，你可能还需要添加!=、<=、>和>=这些方法。
- 只要
x.unique == y.unique等于x.sort == y.sort，这不会破坏==和<=之间的关系。
我觉得BTrees或者其他传统的排序数据结构（比如红黑树等）对你没有帮助，因为它们是根据键来保持顺序的，而不是根据对应的值。换句话说，它们保证唯一性的字段和排序的字段是同一个。你的需求不一样，因为你想要在一个字段上保持唯一性，而在另一个字段上保持排序。
你的性能需求是什么？我在一台不是特别快的笔记本上，用纯Python实现了一个简单的方案，基于Python字典来保证唯一性，使用Python的排序功能。对于一百万个元素的原始构建，我大约花了5秒钟（基本上是对这些元素进行排序，开始时它们是一个字典），而对于“更新”操作，添加了20,000个新的id/value对，其中一半是“重叠”的（也就是覆盖了已有的id），另一半是新的，这个过程大约花了9秒钟。我可以用更快的方法来实现更新，大约6.5秒，但这种实现有个问题：如果其中一个“新”的对和一个“旧”的对完全相同（包括id和value），就会出现重复。为了防止这种“完全相同的重复”，我的时间从6.5秒增加到了9秒，我想你也需要采取类似的预防措施。
这5秒和9秒的时间距离你的需求有多远？要考虑你将要运行的机器的实际速度，比如我用的这台2.4 GHz的Core Duo，2GB的内存，以及这台笔记本的典型性能问题。换句话说，这个时间是否接近“可以接受的范围”，值得你去调整和尝试挤出最后的几毫秒，还是说你需要快几个数量级的性能？
我尝试过几种其他的方法（用SQL数据库、用C++和它的std::sort等），但它们都更慢，所以如果你需要更高的性能，我不太确定你该怎么做。
编辑：因为提问者说这个性能是可以接受的，但他无法达到接近这个水平，我想我最好展示一下我用来测量这些时间的脚本...：
import gc
import operator
import random
import time
nk = 1000
def popcon(d):
for x in xrange(nk*1000):
d['id%s' % x] = random.randrange(100*1000)
def sorted_container():
ctr = dict()
popcon(ctr)
start = time.time()
ctr_sorted = ctr.items()
ctr_sorted.sort(key=operator.itemgetter(1))
stend = time.time()
return stend-start, ctr_sorted
def do_update(ctr, newones):
start = time.time()
dicol = dict(ctr)
ctr.extend((k,v) for (k,v) in newones if v!=dicol.get(k,None))
dicnu = dict(newones)
ctr.sort(key=operator.itemgetter(1))
newctr = [(k,v) for (k,v) in ctr if v==dicnu.get(k,v)]
stend = time.time()
return stend-start, newctr
def main():
random.seed(12345)
for x in range(3):
duration, ctr = sorted_container()
print 'dict-to-sorted, %d: %.2f sec, len=%d' % (x, duration, len(ctr))
newones = [('id%s' % y, random.randrange(nk*100))
for y in xrange(nk*990,nk*1010)]
duration, ctr = do_update(ctr, newones)
print 'updt-to-sorted, %d: %.2f sec, len=%d' % (x, duration, len(ctr))
del ctr
gc.collect()
main()
这是一次典型的运行：
$ time python som.py
dict-to-sorted, 0: 5.01 sec, len=1000000
updt-to-sorted, 0: 9.78 sec, len=1010000
dict-to-sorted, 1: 5.02 sec, len=1000000
updt-to-sorted, 1: 9.12 sec, len=1010000
dict-to-sorted, 2: 5.03 sec, len=1000000
updt-to-sorted, 2: 9.12 sec, len=1010000
real 0m54.073s
user 0m52.464s
sys 0m1.258s
总的耗时比我测量的总时间多几秒，显然是因为它还包括了填充容器所需的时间、随机生成“新数据”的时间、每次运行结束时销毁和垃圾回收的时间等等。
这是在一台Macbook上，使用系统自带的Python 2.5.2，运行Mac OS X 10.5.7，2.4 GHz的Intel Core Duo和2GB的内存（当我使用不同版本的Python时，时间变化不大）。