ソートされた配列を入力からawk/gawkに読み取り、中央値を取得する必要があります。配列全体を格納したくなく、計算のために一定のスペースを取得しようとしています。
これを行うアルゴリズムを知っていますか？配列はソートされていますが、そのサイズは不明です。
前もって感謝します！
2124 次
3 に答える
4
固定量のメモリで実行される未知の長さの並べ替えられたシーケンスの中央値を正確に見つけるアルゴリズムはありません。
これを見るために、そのようなアルゴリズムを考えてみましょう。Nシーケンスからのアイテムを保持するための長さのバッファーがあるとします。このバッファがいっぱいになるまで、アルゴリズムは単純に項目をバッファに入れ、その間に中央値を追跡します。
アルゴリズムがN+1th 番目以降のアイテムをスキャンするとき、各ステップでドロップするアイテムを 1 つ選択する必要があります。既に2Nアイテムをスキャンし、半分をドロップしたとします。入力ストリームの中央値をまだ下回っていないとしましょう。
2N+1番目のアイテムをいつスキャンするかを考えてみましょう。どのアイテムをドロップする必要がありますか? このアイテムの後に入力が使い果たされる可能性があるため、これまでに保持した最小の要素を削除することはできません。その場合、最小値が中央値になる可能性があります。同様に、ドロップされる可能性のある要素については、このドロップされた要素を中央値にする入力シーケンスへの未来があります。
おおよその結果を取得したい場合は、この推定器が役立つ場合があります。
于 2011-10-11T06:00:26.120 に答える
4
最初のパスを使用して配列のサイズを計算し、必要に応じてデータをファイルに保存します。それ以外の場合は、配列を保存せずにそれを行うことはできません.n個のアイテムを読み取った後にプログラムの状態を取得すると、非常に大きな数を与えることで、最後のn / 2個のアイテムのいずれかを中央値として取得できるため、実際、プログラムは少なくともそれらの項目を記憶している必要があります。
于 2011-10-11T04:48:34.903 に答える
2
基本的に、あなたが求めているのはN、配列のサイズを見つけるための「アルゴリズム」です。これは、中央値が要素番号になるため(N+1)/2です（今のところ、偶数/奇数の詳細は無視されます）。
2 つのパスを含まないアルゴリズムは考えられません。定義上、 を把握するには最初のパスが必要ですN。
element をスキャンしている間、前の要素i+1のバッファを保持できます。i/2配列の最後に到達すると、中央値はバッファ内の最初の値になります。つまり、必要なパスは 1 つだけです。N/2これの問題は、バッファに要素を格納するのに十分なメモリを割り当てなけれNばならないということです。またN、質問で述べているように、値が大きすぎて保存できない場合は、おそらくN/2値も大きすぎて保存できません（そうでない場合は、RAMを2倍にするだけです）。
したがって、このバッファ アプローチはオプションではありません。2パスです。把握するNもの、要素を取得するもの(N+1)/2。
于 2011-10-11T06:18:52.283 に答える