0

我问了另一个问题： 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 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))

foreign_keys 是字典中的原始数据，每个 id 为键，附加数据的字典为值。data 是一个包含排序数据列表的字典。

附带说明一下，随着 lb_fields 中 for 字段的每次迭代运行，排序时间会增加 - 不会增加很多......但它很明显。在为 16 个字段中的每一个字段排序了 100 万条记录后，它使用了大约 4 Gigs 或 RAM。最终这将在具有 48 Gigs 的机器上运行。

4

2 回答 2

1

我认为 BTree 或其他传统的排序数据结构（红黑树等）不会对您有所帮助，因为它们通过键而不是对应值来保持顺序——换句话说，它们保证唯一的字段是相同的他们订购的一个。你的要求是不同的，因为你想要一个领域的唯一性，但另一个领域的排序。

您的性能要求是什么？通过基于 Python dicts 的唯一性和 Python 排序的相当简单的纯 Python 实现，在一台速度不快的笔记本电脑上，我得到了 5 秒的原始构造（基本上是对数百万个元素的排序，从它们作为 dict 开始） ，大约 9 秒用于“更新”，其中包含 20,000 个新的 id/value 对，其中一半“重叠”（从而覆盖）现有 id 和一半是新的（我可以以更快的方式实现更新，大约 6.5 秒，但是该实现有一个异常：如果“新”对之一与“旧”对之一完全相同，无论是 id 还是值，它都是重复的——防止这种“重复相同”是让我从 6.5 秒到 9，我想你需要同样的预防措施）。

这 5 秒和 9 秒的时间距离您的要求有多远（考虑到您将运行的机器的实际速度与 2.4 GHz Core Duo、2GB 的 RAM 以及这台笔记本电脑的典型笔记本电脑性能问题）正在使用）？IOW，它是否足够接近“惊人的距离”以值得修补并试图挤出最后几个周期，或者您是否需要数量级更快的性能？

我尝试了其他几种方法（使用 SQL DB，使用 C++ 及其 std::sort &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 时，时间变化不大）。

于 2009-07-26T02:26:44.070 回答
1

完全有可能解决您的问题。为此，您只需注意 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
于 2009-08-09T22:40:32.320 回答