問題タブ [quickselect]

私は宿題に苦労していて、少しプッシュする必要があります-問題は、O(nlogm) 時間で複数の最小要素1<k1<k2<...<knを見つけ、m * k を持つアルゴリズムを設計することです。単純な選択アルゴリズムでは、k 番目の要素を見つけるのに o(n) の時間がかかることはわかっていますが、再帰の m をどのように削減しますか? 私は各実行で k1 と kn の両方を実行することを考えましたが、それは m/2 ではなく 2 だけを取り出します。

いくつかの指示をいただければ幸いです。ありがとう

問題:特定のログの最終日に最も頻繁に繰り返される「パターン」を確認する必要にしばしば直面します。Tomcat ログの小さなサブセットのように:

最も頻繁に使用される URL を (メソッドと retcode とともに) 知りたい場合は、次のようにします。

同じファイルから最も頻繁に使用されるユーザー名を見つけたい場合は、次のようにします。

上記は小さなデータセットでは非常にうまく機能しますが、より大きな入力セットの場合 - のパフォーマンス (複雑さ)sort|uniq -c|sort -rn|head -$Nは耐えられません (約 100 台のサーバー、サーバーあたり約 250 個のログ ファイル、ログ ファイルあたり約 1mln 行)。

解決しようとする: |sort|uniq -c部分は awk 1-liner に簡単に置き換えることができ、次のようになります。

しかし、部品を最適化するための「クイック選択アルゴリズム」（ここで説明）の標準/シンプ​​ルでメモリ効率の高い実装を見つけることができませんでした|sort -rn|head -$N。GNU バイナリ、rpm、awk 1 ライナー、または簡単にコンパイルできる Ansi C コードを探していました。

に (N=3 の場合):

サンプル Java コードを取得して、上記の stdin 形式に移植することもできます (ちなみに、.quickselect(...)コア Java 内に不足していることに驚きました)。サンプル (配列ベース) の C スニペットも取得して、上記の stdin 形式に適応させてから、しばらくの間、リークなどをテストして修正することができます。または、awk でゼロから実装することもできます。BUT(!) - この単純な必要性は、おそらく 1% を超える人々が定期的に直面している可能性があります - 標準的な (事前にテストされた) 実装が存在するはずでした?? 希望...おそらく私はそれを調べるために間違ったキーワードを使用しています...

その他の障害:また、大規模なデータセットを回避するためにいくつかの問題に直面しました。

• ログ ファイルは、NFS でマウントされた最大 100 台のサーバーのボリュームに配置されているため、作業を並列化して小さなチャンクに分割することは理にかなっています。
• 上記にawk '{S[$0]+=1}...はメモリが必要です-16GBを消費するたびに死ぬのを見ています（48GBの空きRAMと十分なスワップがあるにもかかわらず...おそらく見落としていたLinuxの制限）

私の現在のソリューションはまだ信頼性が低く、最適ではありません (進行中) は次のようになります。

quickselectとして知られているアルゴリズムの github でこのコードを見つけましたorder-statistics。このコードは正常に動作します。

medianOf3最初、中間、最後のインデックスをソート順に並べる方法がわかりません。しかし、実際には、メソッドを呼び出した後に配列を出力するときはそうではありませんmedianof3。の最後の呼び出しを除いて、このメソッドが何をしているのかについては、このメソッドに従うことができますswap(list, centerIndex, rightIndex - 1);。誰かがなぜこれが呼び出されたのか説明できますか?

たとえば、51 要素の中央値を抽出するには、51 を 25 の H(ead) グループに分割し、その後に中央値、25 の T(ail) が続きます。私が知っているすべてのアルゴリズムは、 H と T が [min(H), max(H)[ と ]min(T), max(T)] がオーバーラップしないような追加のプロパティ。

この追加のプロパティは必須であることが証明されていますか (私はそう思います)? どこで証拠を見つけることができますか（長い間行われていると思います）？

（これはアルゴリズムへの愛のためだけです）

n サイズのソートされていないセットから任意の要素を見つけるために、なぜ QuickSelect がこれほど優れたパフォーマンスのアルゴリズムであると思われるのか疑問に思っています。つまり、すべての要素を 1 つずつ調べて、目的の要素が見つかるまで O(n) 回の比較が必要でした。

これについて重要な何かが欠けていますか？線形検索よりも QiuckSelect の方が優れている場合はありますか?

ソートされていないリストでおおよその中央値を見つけたい、2つのアルゴリズムを知っている

アルゴリズム 1 - クイックセレクト

アルゴリズム 2 - 中央値の中央値

私のプロジェクトでは、最悪の場合 O(n^2) かかるため、クイック選択を使用できません。中央値の中央値について聞いたことがありますが、私の同僚は、一定の係数を持つ O(n) が必要であることを示唆しています。中央値の中央値に関連付けられている定数要因は何ですか?また、中央値の中央値が9要素の疑似中央値を使用しないのはなぜですか?
または、線形時間 O(n) でおおよその中央値を見つけるための他のアルゴリズムですか?

k入力配列から最上位の要素を返す効率的な方法を探しています。1 つの方法は、配列をソートし、配列の末尾から要素
を返すことです。k

hereで提案されている他の方法があり、そのうちの 1 つはquickselect アルゴリズムを使用しますが、私の理解では、quickselect はkソートされていない配列の 番目の要素のみを返します。戻った後、左右の要素kはまだソートされていません。

したがって、次のようになります。

クイック選択はO(n)であり、それを2k回行うので、全体的な時間の複雑さはO(n*k)です。
しかし、投稿のデータは、これが よりも優れていることを示唆していますO(n log n)。
100 万のサンプルから上位 200 を選択すること200 millionは、前者の場合を意味しますが20 million、後者の場合を意味します。明らかに、これははるかに優れています。

上位 200 個の要素を選択するために quickselect を使用する方法を理解していますか?

プログラムは、クイック選択を使用して、一連の整数値の中央値を返すことになっています。

質問: プログラムを実行すると、k が定義されていないと表示されます。中央値を取得するには、k をどのように定義すればよいですか?

クイック セレクト アルゴリズムの理解に問題があります。私はそれがクイックソートアルゴリズム（私がよく知っている）に基づいていることを知っており、おそらく配列の一部をソートせずに残して必要な結果が得られることを知っています。問題は、次の配列から 2 番目に小さい要素を見つけることです。

ここで、ピボットをランダムに選択するとします。この投稿によると、次の条件があります。

• k == pivot. 次に、すでに k 番目に小さいことがわかりました。これは、パーティションの動作方法が原因です。k 番目の要素よりも小さい要素がちょうど k - 1 個あります。

• k < pivot. 次に、k 番目に小さいものがピボットの左側にあります。

• k > pivot. 次に、k 番目に小さいものがピボットの右側にあります。そして、それを見つけるには、実際に右側の k-pivot 最小数を見つける必要があります。

k==pivot k番目（私の場合は2番目に小さい要素）を見つけたことを誰かがどのように意味するかを説明できれば幸いです。またk < pivot、ピボットの左側に対してプロセスを繰り返す場合は?