4

ただし、同様のタイプの質問が他の人から尋ねられています。here、しかしそれらはわずかに異なり、実際には私の問題を解決できなかったので、ここでもう一度行きます。

N 個のリスト (N>20,000) があり、各リストには M 個のリスト ( M >20,000) が次のように含まれています (データはダミーです)。

Key1: [ [4,3,1], [5,1,0] ...... [43,21,0 ] ]   # List 1 with collection of M smaller lists
:
:
KeyN: [ [5,4,1], [55,1,1] ...... [ 221, 0, 0] ] # Nth list

データはソートされていません。しきい値のリストを 1 つずつ反復処理します。たとえばThreshold =[2, 3, 5, 7, 8]、しきい値が中央の要素に適用される場合、すべてのキーについて、しきい値より大きいすべての要素を抽出します。たとえば。Threshold = 2私が上に書いたデータによると、

 For Key1: [ [4,3,1], [43,21,0]]
 :
 : 
 For KeyN: [[5,4,1]]

他のしきい値についても同様です。リストが多すぎるため、並べ替えが多くのオーバーヘッドに寄与しているため、回避したいと考えています。Pythonでこれを行う最適な方法は何ですか?. もう 1 つの重要な点は、私は自分でデータを構築しているので、最初にデータを格納するためのより良いデータ構造がある可能性があるということです。私は現在、ここで提案されたコンテナPersistentList内の形式でデータを保存しています。以下は、それに使用されるコードのスニペットです。BtreeZODB

for Gnodes in G.nodes():      # Gnodes iterates over N values 
    Gvalue = someoperation(Gnodes)
    for Hnodes in H.nodes():  # Hnodes iterates over N values 
        Hvalue =someoperation(Hnodes,Gnodes)
        score = SomeOperation on (Gvalue,Hvalue)
        btree_container.setdefault(Gnodes, PersistentList()).append([Hnodes, score, -1 ])
    transaction.savepoint(True)  
transaction.commit()

それを行うための最も効率的な方法について何か提案はありますか? 最初にソートするのが本当に最適な方法ですか?

4

2 に答える 2

4

生成内包表記を使用します。

(sublist for sublist in Key1 if sublist[1] > Threshold)

ジェネレーターは必要に応じて要素を計算するだけで、リストの要素を順番に処理するため、並べ替える必要はありません。(つまり、並べ替えの M*log(M) ではなく、各 の長さで線形時間で実行されます。)Keyn

同様に、関数型スタイル (Python 3 でのみ同等。Python 2 の場合は を使用itertools.ifilter):

filter(lambda sublist: sublist[1] > Threshold, Key1)

リストがリスト (または他の添え字付け可能なオブジェクト) に格納されている場合は、それらをすべて一度に処理できます (いくつかの代替スタイルを示します)。Keyn

filtered_Keys = [(sublist for sublist in Key if sublist[1] > Threshold)
    for Key in Keys
]

また

filtered_Keys = list(map(
    lambda Key: filter(lambda sublist: sublist[1] > Threshold, Key1),
    Keys
))

ソートに対するこのメソッドのパフォーマンス

この方法がソートよりも速いかどうかは、Mと使用しているしきい値Tの数によって異なります。(各Keyリストの) 実行時間は O(M * T) です。リスト (O(M * log(M))) を並べ替えると、各しきい値に対してバイナリ検索を使用でき、全体の実行時間は O(M * log(M) + T * log(M)) = になります。 O(max(M, T) * log(M))。TがMに対して十分に大きい場合、並べ替えは高速になります。先験的に定数を知ることはできないため、両方の方法をテストして、データが与えられた場合に一方が高速かどうかを確認してください。

どちらも十分に高速でない場合は、独自の線形時間ソートを作成することを検討してください。たとえば、基数ソートは、(負でない) float で動作するように一般化できます。ここでのパフォーマンスが本当に気になる場合は、これを C または Cython 拡張機能として作成する必要があるかもしれません。

于 2012-07-01T01:58:19.920 に答える
2

numpy では、NxMx3 配列を使用してこれを簡単に行うことができます。

data = array([
    [ [4,3,1], [5,1,0],  [43,21,0]    ],
    [ [5,4,1], [55,1,1], [ 221, 0, 0] ]
    ])
data[ data[:,:,1]>2 ]

これは以下を返します:

array([[ 4,  3,  1],
   [43, 21,  0],
   [ 5,  4,  1]])

しきい値を超えた要素の位置が必要な場合は、argwhere() を使用します。

編集：

複数のしきい値比較を同時に行うこともできます。

>>> mask = data[:,:,1,np.newaxis] > array([[[2, 3, 4]]])
>>> data[mask[...,0]]
array([[ 4,  3,  1],
   [43, 21,  0],
   [ 5,  4,  1]])

>>> data[mask[...,1]]
array([[43, 21,  0],
   [ 5,  4,  1]])

>>> data[mask[...,2]]
array([[43, 21,  0]])
于 2012-07-01T02:30:15.670 に答える