ファイル内の上位n個の数字を見つける

何千もの数字を含むファイルで上位n個の数字を見つけるためにアルゴを見つけようとしていました。その前に、配列の上位n個の数値を確認したが、具体的な解決策が得られなかった。ソートは明白なオプションですが、他の方法がありますか？ファイルに同じロジックを適用できるかもしれませんファイル内の上位n個の数字を見つける

出典

2012-02-02 Akshay

どのツールを使用できますか？ファイルはどのように整理されていますか？ –

ここで同じ質問：http://stackoverflow.com/questions/9074463/most-suitable-sorting-algorithm –

ファイルはランダムな順序で数字で整理されています... 私は前の投稿に答えがあると思います...バリエーションmax heap sort shudがsolfの1つになる – Akshay

あなたのファイルは次のように見えます。

123 448 28239 
1299 23729 71829 
18283 75723 817 
93993 1791 9

標準のUNIXツールを使用して、私はこのようにします。

$ tr " " "\n" < in.txt | sort -n -r | head -5 
93993 
75723 
71829 
28239 
23729

説明：

trが改行にすべての空間を変換\n
sort -n -r種類今数値的に、1つの番号毎を含む行、および折返し
head -5はのトップ5を取りますこれらのソートされた行

もちろん、これはあなたのアルゴリズムの質問には答えません。

編集：Comparison of Internal Sorting Algorithms 2008からは、さまざまなツールで使用されているアルゴリズムの詳細が示されています。

出典

2012-02-02 07:53:41

内部ソートツールを使用できますが、膨大な数のファイルに対しては、時間の複雑さが大幅に増加しますシングルスキャンが最適なソリューションです。 – Akshay

'sort 'の実装方法は知っていますか？さらに、入力の* size *はアルゴリズムの複雑さ*を絶対に増加させません。 –

UNIXで内部的にどのように処理されているか...最も効率的な方法であるはずです。 – Akshay

それはtopN内のすべてのn番号より小さいだ場合は、長さnとし、ファイルのチェック中のすべての数のために（topN[n]言う）の配列を維持することができます。
そうでない場合は、これをtopTenの最小値に置き換えてください。

このアルゴリズムの複雑さがO(n*k)であるため、nがあまり大きくない場合、これは良い解決策です。ここで、Kはファイル内の数字の数です。

それがソートされたままになりますようにあなたがtopNに新しい番号を追加する必要がありますたびに（次の番号を追加するとき、それが役立ちます。）

1.は、次の番号

を取得しているため、実際の複雑さがO(n*(k+1))です2.あなたtopN配列のバイナリ検索して、それを検索し、その場所（nextNumberその後、小さい配列内の最大項目）

を見つけます

nextNumberをその位置に挿入し、 topNの次の項目をすべて右に移動します。

topNの最後の項目はアレイから削除されます。fは、ファイル内の数字の数であり、nはあなたが抽出する必要がある番号であれば、あなたはO(n + f lg n)でそれを行うことができます

出典

2012-02-02 07:54:54 shift66

hmm私はsolnを考えていましたが、ここでは配列全体を検索するオーバーヘッドがありますヒープソートlog nの複雑さを達成してください。配列をソート順で維持し、バイナリ検索を使用すると複雑さが軽減されます – Akshay

私の答えは編集しました。 – shift66

Hmm ..この配列の実装はmaxheapと似ています。要素を削除するためのオーバーヘッドがないので、Maxheapはこれより効率的です要素を削除する – Akshay

（実際n <= fとして、O(f lg n)である）を次のように

ビルドファイル内の最初のn番号の（バイナリ）min-heap。（O(n)）
ファイル内の残りの数値については、ヒープ内の先頭の要素と比較してください。新しい番号が大きい場合は、一番上の要素をオフにして新しい要素を挿入します。（O(f)回、O(lg n)操作）。
完了すると、ヒープにはnというファイル内で最大の数字が含まれます。

出典

2012-02-02 07:56:11

ファイル内の上位n個の数字を見つける

答えて

関連する問題