パイソン:Zope の BTree OOSet、IISet など…この要件には効果的ですか?

StackOverflow https://stackoverflow.com/questions/1183428

  •  19-09-2019
  •  | 
  •  

質問

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

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

項目をタプルとして 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))

external_keys は、各 ID をキー、追加データの辞書を値とする辞書内の元のデータです。data は、ソートされたデータのリストを含むディクショナリです。

余談ですが、lb_fields の for フィールドの反復が実行されるたびに、並べ替えにかかる時間が増加します (それほど長くはなりません)。しかしそれは目立ちます。100 万件のレコードが 16 フィールドごとにソートされると、約 4 ギガバイトまたは RAM が使用されます。最終的には、これは 48 ギガバイトのマシンで実行されることになります。

役に立ちましたか？

解決

私は、彼らがいない値を、対応することで、キーによって秩序を維持するために、あなたを助けるのbtreeや他の伝統的なソートされたデータ構造（赤黒木など）を考えていない - つまり、フィールドは、彼らが独自の保証します彼らはによって注文と同じです。あなたの要件は、あなたが一つのフィールドに沿って独自性をしたいので、異なっているが、他のことでsortednessます。

あなたのパフォーマンス要件は何ですか？独自性やPythonの並べ替えのためのPythonのdictsに基づいてではなく、単純な純粋なPython実装では、-驚異-速くないラップトップ上で、私は（辞書として始まる、百万個の要素にわたって本質的にソート）元建設のための5秒を取得します半分「オーバーラップ」20,000新しいID /値ペアと「更新」のために、約9秒（従って上書き）既存のIDと半分が新規である（私は約6.5秒、より高速な方法で更新を実施することができるが、その実装は、異常を持っている：「新」ペアの一つが「古い」ものの一つ、idと値の両方と全く同じであれば、それが重複しています - そのような「identicalsの重複」に対するウォードは6.5秒から私をプッシュするものです9に、私は想像して、あなたは）念の同じ種類が必要になります。

どのくらいの要件からこれらの5-と-9秒の時間が（アカウントにあなたは2.4GHzのCore Duoプロセッサ、2GBのRAM、および典型的なノートパソコンのパフォーマンスの問題対上で実行されますマシンの実際の速度を取っています私が使用しているこのラップトップ）？ IOWは、いじりとのうちの最後の数サイクルを絞るしようとしている価値があると「射程」に十分な、それは近く、またはあなたは大きさより高速なパフォーマンスの注文が必要なのでしょうか？

私は（...、C ++およびそのSTDとSQL DBと、::ソート＆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でのMacbook、2.4 GHzのIntel Core Duoプロセッサ、およびRAMの2ギガバイト（Iは、Pythonの異なるバージョンを使用するときに時間があまり変化していない）の上に、システム提供のPython 2.5.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
ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top