0

別の質問をしました: https://stackoverflow.com/questions/1180240/best-way-to-sort-1m-records-in-python ここで、100万件のレコードをソートするための最良のアプローチを決定しようとしていました。私の場合、コレクションに追加のアイテムを追加して、再ソートできるようにする必要があります。このタスクには Zope の BTree を使用するように勧められました。いくつかの読書をした後、どのデータをセットに入れるかについて少し困惑しています。

基本的に、各レコードには 2 つのデータがあります。1. ユーザーにマップされる一意の ID と 2. 並べ替え対象の値。

アイテムをタプルとして OOSet に追加できることがわかりました。ここで、並べ替えの値はインデックス 0 です。したがって、(200, 'id1'),(120, 'id2'),(400, 'id3')結果のセットはid2, id1 and id3順番に並べ替えられます。

ただし、この要件の一部は、各 ID がセット内で 1 回だけ出現することです。このセットには定期的にデータを追加しますが、新しいデータには重複した「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 ギガまたは RAM を使用しています。最終的に、これは 48 ギグのマシンで実行されます。

4

2 に答える 2

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 に答える
1

BTree やその他の従来のソートされたデータ構造 (赤黒木など) は、対応する値ではなくキーで順序を維持するため、役に立たないと思います。つまり、一意であると保証されるフィールドは同じです。彼らが注文するもの。1 つのフィールドに沿った一意性が必要であり、他のフィールドによる並べ替えが必要なため、要件は異なります。

パフォーマンス要件は何ですか? 一意性のための Python dict と Python ソートに基づくかなり単純な純粋な Python 実装を使用すると、非常に高速ではないラップトップで、元の構成に 5 秒かかります (基本的に、dict として始まる、100 万の要素のソート)。 、および 20,000 個の新しい ID/値のペアによる「更新」に約 9 秒。その半分は既存の ID と「重複」(したがって上書き) し、半分は新しいものです (更新をより高速な方法で実装できます。約 6.5 秒ですが、その実装には異常があります。「新しい」ペアの1つがIDと値の両方で「古い」ペアの1つとまったく同じである場合、それは重複しています-そのような「同一の重複」を防ぐことが、私を6.5秒から押し出すものですから 9 まで、同様の予防措置が必要になると思います)。

これらの 5 秒と 9 秒の時間は、要件からどのくらい離れていますか (実行するマシンの実際の速度と、2.4 GHz Core Duo、2 GB の RAM、およびこのラップトップ I の典型的なラップトップ パフォーマンスの問題を考慮して)使ってる？）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、および 2 GB の RAM を搭載した Macbook でシステム提供の Python 2.5.2 を使用した場合です (異なるバージョンの Python を使用しても、時間はあまり変わりません)。

于 2009-07-26T02:26:44.070 に答える