代码之家 › 专栏 › 技术社区 › sberry

python:zope的btree-ooset、iiset等等……对这个要求有效吗?

zope python

sberry · 技术社区 · 15 年前

我又问了一个问题: https://stackoverflow.com/questions/1180240/best-way-to-sort-1m-records-in-python 在那里,我试图确定对100万条记录进行排序的最佳方法。在我的情况下,我需要能够添加额外的项目到集合,并让他们诉诸。有人建议我尝试使用Zope的Btrees来完成这项任务。在读了一些书之后,我有点困惑,我会把什么数据放在一个集合中。

基本上,对于每个记录,我都有两个数据块。1。映射到用户和2的唯一ID。排序感兴趣的值。

我看到可以将项目作为元组添加到ooset中,其中排序的值在索引0处。所以, (200, 'id1'),(120, 'id2'),(400, 'id3') 结果集将按 id2, id1 and id3 整齐。

但是,这一要求的一部分是每个ID在集合中只出现一次。我将定期向集合中添加其他数据,新数据可能包含或不包含重复的“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))

外键是字典中的原始数据,每个ID作为键,附加数据的字典作为值。数据是包含排序数据列表的字典。

作为旁注,随着在lb_字段中的for字段的每个i创建的运行,排序时间会增加-不会增加太多…但这是显而易见的。在为16个字段中的每个字段排序了100万条记录后,它使用了大约4个gigs或RAM。最终,这将在一台48千兆的机器上运行。

2 回复 | 直到 15 年前

Alex Martelli 15 年前

我不认为btrees或其他传统的排序数据结构(红黑树等)可以帮助您,因为它们按键而不是按相应的值来排序——换句话说,它们保证唯一的字段与它们排序的字段相同。您的需求是不同的,因为您希望一个字段具有唯一性,而另一个字段具有排序性。

您的性能要求是什么?基于python dicts的简单的纯python实现的唯一性和python排序,在一台速度不太快的笔记本电脑上,我得到了5秒钟的原始结构(基本上是对百万个元素的排序,从dict开始),大约9秒钟的“更新”,20000个新的id/value对,其中一半“重叠”(因此,覆盖)现有的ID和一半是新的(我可以更快地实现更新,大约6.5秒,但该实现有一个异常:如果“新”对中的一对与“旧”对中的一对完全相同(包括ID和值),则它是重复的——避免这种“相同的重复”是将我从6.5秒推到6.5秒的原因。到9点,我想你也需要同样的预防措施)。

这5秒和9秒的时间与您的要求有多远(考虑到您将要运行的机器的实际速度与2.4 GHz核心双核、2GB RAM以及我使用的这台笔记本电脑的典型笔记本电脑性能问题)?看,它是接近“惊人的距离”值得修补和尝试挤出最后几个周期,还是你需要数量级更快的性能?

我已经尝试了其他几种方法(用SQL DB,用C++和它的STD::排序和C,……),但是它们都比较慢,所以如果你需要更高的性能,我不确定你能做什么。

编辑 :因为OP说这个性能会很好,但他不能在任何地方接近它,我想我最好展示一下我用来测量这些时间的脚本…:

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

显然,总运行时间比我测量的总运行时间长几秒,因为它包括用随机数填充容器、随机生成“新数据”、在每次运行结束时销毁和垃圾收集等所需的时间。

这是在Mac OS X 10.5.7、2.4 GHz Intel Core Duo和2GB RAM的MacBook上系统提供的python 2.5.2(当我使用不同版本的python时,时间变化不大)。

ilya n. 15 年前

完全有可能解决你的问题。为此,您应该注意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 ==& gt; x.sort == y.sort