10

少なくとも100000000個の数字のリストから最大の100個の要素を取得したいと思います。

リスト全体を並べ替えて、並べ替えたリストから最後の100個の要素を取得することもできますが、メモリと時間の両方の点で非常にコストがかかります。

これを行うための既存の簡単でpythonicな方法はありますか？

私が欲しいのは、純粋なソートではなく、次の関数です。実際、気にしない要素を並べ替えるのに時間を無駄にしたくありません。

たとえば、これは私が欲しい関数です：

getSortedElements(100, lambda x,y:cmp(x,y))

この要件は、パフォーマンスの観点からのみであることに注意してください。

4

6 に答える 6

27

標準ライブラリのheapqモジュールは、これを行うためのnlargest（）関数を提供します。

top100 = heapq.nlargest(100, iterable [,key])

リスト全体が並べ替えられるわけではないので、不要な要素に時間を浪費することはありません。

于 2009-08-02T13:54:27.990 に答える
6

ここでは、選択アルゴリズムが役立ちます。

非常に簡単な解決策は、100番目に大きい要素を見つけてから、この要素よりも大きい要素を選択してリストを実行することです。それはあなたに100の最大の要素を与えるでしょう。これは、リストの長さにおいて線形です。これが最善です。

より洗練されたアルゴリズムがあります。たとえば、ヒープはこの問題に非常に適しています。ヒープベースのアルゴリズムは、リストの長さであり、n log k選択する最大の要素の数です。nk

この問題については、選択アルゴリズムのWikipediaページで説明されています。

編集：別の投稿者は、Pythonにはこの問題の解決策が組み込まれていると指摘しています。明らかに、それは自分で作成するよりもはるかに簡単ですが、そのようなアルゴリズムがどのように機能するかを知りたい場合に備えて、この投稿を続けます。

于 2009-08-02T13:45:45.473 に答える
5

ヒープデータ構造を使用できます。ヒープは必ずしも順序付けられる必要はありませんが、半順序付けされたデータを保持するためのかなり高速な方法であり、最小のアイテムが常にヒープの最初の要素であるという利点があります。

ヒープには、追加と置換という2つの基本的な操作があります。

基本的には、100個のアイテム（質問ごとの上位N個）に到達するまでアイテムを追加します。その後、新しいアイテムが最初のアイテムよりも大きい限り、最初のアイテムをすべての新しいアイテムに置き換えます。

最初のアイテムをより大きなものに置き換えると、ヒープの内部コードによってヒープの内容が調整され、新しいアイテムが最小でない場合はヒープにバブルアップし、最小のアイテムは次のように「バブルダウン」します。途中で交換する準備ができている最初の要素。

于 2009-08-02T13:53:21.190 に答える
3

これを行うための最良の方法は、100個のエントリが含まれるとポップオフするヒープソート済み優先度キューを維持することです。

結果がソートされているかどうかは気にしませんが、これを無料で入手できることは直感的に明らかです。あなたがトップ100を持っていることを知るために、あなたはいくつかの効率的なデータ構造を介して順番にあなたの現在のトップ番号のリストを注文する必要があります。その構造は、各要素の最小値、最大値、および相対位置を自然な方法で認識し、隣接する要素の隣の位置を表明できます。

Pythonで述べたように、heapqを使用します。java PriorityQueueの場合：http： //java.sun.com/javase/6/docs/api/java/util/PriorityQueue.html

于 2009-08-02T13:59:47.047 に答える
2

これは、ライブラリに依存せず、配列を持つすべてのプログラミング言語で機能する、私が使用したソリューションです。

初期化：

Make an array of 100 elements and initialise all elements
with a low value (less than any value in your input list).

Initialise an integer variable to 0 (or any value in
[0;99]), say index_minvalue, that will point to the
current lowest value in the array.

Initialise a variable, say minvalue, to hold the current 
lowest value in the array.

入力リストの各値、たとえばcurrent_valueについて：

if current_value > minvalue

  Replace value in array pointed to by index_minvalue
  with current_value

  Find new lowest value in the array and set index_minvalue to
  its array index. (linear search for this will be OK as the array
  is quickly filled up with large values)

  Set minvalue to current_value

else
  <don't do anything!>

minvalueはすぐに高い値を取得するため、入力リストのほとんどの値はminvalueと比較するだけで済みます（比較の結果はほとんどfalseになります）。

于 2009-08-02T15:09:29.267 に答える
1

オーディエンスのアルゴリズムウィニーの場合：Tony Hoareのアルゴリズムの単純なバリエーションでこれを行うことができます検索：

find(topn, a, i, j)
   pick a random element x from a[i..j]
   partition the subarray a[i..j] (just as in Quicksort) 
     into subarrays of elements <x, ==x, >x
   let k be the position of element x
   if k == 0 you're finished
   if k > topn, call find(topn, a, i, k)
   if k < topn, call find(topn-k, k, j)

このアルゴリズムは、最大の要素を並べ替えることなく、配列の最初の要素に配置しtopnます。もちろん、それらをソートしたい場合、または単純にするために、ヒープの方が優れており、ライブラリ関数の呼び出しもさらに優れています。しかし、それはクールなアルゴリズムです。topna

于 2009-08-02T16:45:34.963 に答える