13

Pythonでファイルを読み込んで、いくつかの文字列といくつかの数値を含むデータを取得しています。この情報を次のようなリストのリストとして保存しています。

dataList = [

['blah', 2, 3, 4],

['blahs', 6, 7, 8],

['blaher', 10, 11, 12],

]

dataListをサブリストの2番目の要素であるdataList[][1]でソートしたままにしておきたい

追加したいときにinsortまたはbisectを使用できると思いましたが、サブリストの2番目の要素をどのように表示するかがわかりません。

ここで何か考えはありますか？最後にデータを追加し、後で物事を見つけるために線形ソートを実行していました。しかし、ここに数万のサブリストを入れてから、10万のアイテムを検索すると、しばらく時間がかかります。

4

2 に答える 2

10 
dataList.sort(key=lambda x: x[1])

これにより、各アイテムの2番目の要素でリストが並べ替えられます。

コメントで指摘されているように、1回だけ（最後に）ソートする方がはるかに効率的です。Pythonの組み込みの並べ替えメソッドは、高速に動作するように大幅に最適化されています。テスト後、組み込みのソートは、さまざまなサイズリスト（最大600000のサイズをテストしました）で、他の回答で提案されているヒープ方式を使用するよりも一貫して約3.7倍高速であるように見えます。

于 2012-09-07T19:51:55.020 に答える
8

いくつかのことに依存しますが、最初に頭に浮かぶのは、heapqモジュールを使用することです。

import heapq
heap = []
for row in rows:
    heapq.heappush(heap, (row[1], row))

これにより、タプルでいっぱいのヒープが作成されます。最初の要素は並べ替える要素で、2番目の要素は行です。

それらをヒープから読み戻す最も簡単な方法は、それをコピーしてからアイテムをポップすることです。

new_heap = list(heap)
while new_heap:
    _, row = heapq.heappop(new_heap)
    print row

各アイテムをヒープに挿入する実行時間はO(lg N)であるため、ヒープの作成には時間がかかりO(N lg N)、ヒープからのアイテムのポップにも時間がO(lg N)かかるため、ヒープO(N lg N)をトラバースするのに時間がかかります。

これらのトレードオフが理想的でない場合は、バイナリ検索ツリーを使用できます（標準ライブラリには存在しませんが、簡単に見つけることができます）。または、他のコメント提供者が示唆しているように、行を読んだ後に並べ替えますrows.sort(key=lambda row: row[1])。

さて、実際には、非常に多くの行を処理している場合を除いて、リストをロードした後（つまり、.sort()メソッドを使用して）、リストをインプレースで並べ替える方がほぼ確実に高速です。何が最も効果的か。

最後に、bisectPythonリストへの挿入にはO(N)時間がかかるため、これはお勧めできません。したがって、bisectを使用してアイテムを挿入するには、アイテムごとO(N lg N)に時間が必要になるため、合計時間になります。O((N lg N) * N) = O(N**2)

于 2012-09-07T19:53:35.300 に答える