4

数値のグループでN番目に大きい値を見つけるために必要なプログラムを書いています。これらの番号はプログラムによって生成されますが、N個の番号を保存するのに十分なメモリがありません。ストレージで達成できるNよりも優れた上限はありますか？数値のグループのサイズ（およびN）の上限は約1億です。

注：数値は小数であり、リストに重複を含めることができます。

[編集]：私のメモリ制限は16MBです。

4

5 に答える 5

3

最初から同じグループの数字を再生成できますか? そうであれば、出力に対して複数のパスを作成できます。最大値を見つけることから始め、ジェネレーターを再起動し、それよりも小さい最大値を見つけて、ジェネレーターを再起動し、結果が得られるまでこれを繰り返します。

多くの数があり、多くのパスが必要になるため、実際のパフォーマンスキラーになるでしょう-しかし、メモリに関しては、2つの要素（現在の最大値と「制限」、数最後のパスで見つかった) とパス カウンター。

プライオリティ キューを使用して M 個の最大要素 (メモリに収まる M を選択) を見つけることで高速化でき、必要なパスの数を N/M に減らすことができます。

たとえば、15 個の数値のリストから 10 番目に大きい要素を見つける必要がある場合は、逆の方法で作業することで時間を節約できます。これは 10 番目に大きい要素であるため、この要素よりも 15-10=5 小さい要素があることを意味します。したがって、代わりに 6 番目に小さい要素を探すことができます。

于 2009-07-05T16:55:52.867 に答える
3

これはマルチパス アルゴリズムです (したがって、同じリストを複数回生成するか、リストをセカンダリ ストレージに保存できる必要があります)。

最初のパス:

  • 最高値と最低値を見つけます。それがあなたの最初の範囲です。

最初の後に渡します:

  1. 範囲を等間隔の 10 個のビンに分割します。ビンに数値を保存する必要はありません。ビンのメンバーシップをカウントするだけです。したがって、整数の配列 (または bigint、カウントを正確に保持できるもの) が得られます。10 は、ビンの数として任意に選択されることに注意してください。サンプル サイズと分布によって、最適な選択が決まります。
  2. データ内の各数値をスピンして、表示されている数値を保持しているビンのカウントを増やします。
  3. どのビンに答えがあるかを把握し、そのビンの上にある数字の数を、勝ったビンの上にある数字のカウントに追加します。
  4. 勝者ビンの上部と下部の範囲が新しい範囲です。
  5. 現在のビンに数値を保持するのに十分なメモリが得られるまで、これらの手順を繰り返します。

最後のパス:

  • これで、現在のビンの上にある数字の数を知る必要があります。
  • 現在のビンの範囲内のすべての数値を取得するのに十分なストレージがあるため、スピンして実際の数値を取得できます。それらを並べ替えて、正しい番号を取得してください。

例: 表示される範囲が 0.0 から 1000.0 の場合、ビンの範囲は次のようになります。

 (- 0.0 - 100.0]
 (100.0 - 200.0]
 (200.0 - 300.0]
 ...
 (900.0 - 1000.0)

数値が (100.0 - 2000.0] ビンにあることがカウントによってわかった場合、次のビンのセットは次のようになります。

 (100.0 - 110.0]
 (110.0 - 120.0]
 etc.

別のマルチパスのアイデア:

バイナリ検索を実行するだけです。範囲の中間点を最初の推測として選択します。パスは、次の見積もりを決定するために上/下のカウントを実行するだけで済みます (カウントによって重み付けするか、コードを簡単にするために単純な平均を計算できます)。

于 2009-07-05T18:05:54.463 に答える
1

これは別の質問に似ています-ソートせずに配列内のn番目に小さい要素を検索するCプログラム？-あなたがいくつかの答えを得るかもしれないところ。
ロジックは、N番目に大きい/小さい検索でも同様に機能します。
注：これがその複製であると言っているのではありません。

あなたはたくさんの（ほぼ10億？）数を持っているので、ここにスペース最適化のための別の方法があります。
数値が32ビット値に収まると仮定すると、約10億は32GBに近いスペースを必要とします。現在、約128MBの作業メモリーを購入できる場合は、これを1回のパスで実行できます。

  1. 32ビットワードの配列として格納された10億ビットベクトルを想像してみてください
    • すべてゼロに初期化しましょう
    • 数値の実行を開始し、数値の値の正しいビット位置を設定し続けます
    • 1回のパスが終了したら、このビットベクトルの先頭からN番目のセットビットのカウントを開始します。
    • そのビットの位置は、N番目に大きい数値の値を示します
    • プロセス内のすべての数値を実際に並べ替えました（ただし、重複の数は追跡されません）
于 2009-07-05T16:50:50.140 に答える
0

私がよく理解していれば、プログラムの上限メモリ使用量はO（N）（おそらくN + 1）です。現在のX（これまでのところN番目に大きい値）よりも大きい生成値のリストを、低いものから順に維持できます。新しい大きな値が生成されるとすぐに、現在のXをリストの最初の要素に置き換えて、生成されたばかりの値をリスト内の対応する位置に挿入できます。

于 2009-07-05T16:36:09.170 に答える
0

並べ替え-n| uniq-cおよびN番目はN番目の行である必要があります

于 2009-07-05T16:50:44.710 に答える