0

2 億の floatがあり、重複しているものもあります。

それらのすべての要素のランクを取得するための効率的な方法 (たとえば、1G メモリ未満) は何ですか (最初は並べ替えられていません)。

このような：

入力: [3.2、3.2、3.4、7.81、1.0]

出力: [2, 2, 4, 5 ,1]

私はビットマップ sortを考えていますが、この状況ではメモリ効率が悪いようです。

4

5 に答える 5

1

1Gで全部できるとは思えない。200 Mvalue データセットは最大 763 MiB かかり、補助データに使用できるのは最大 261 MiB だけになることに注意してください。200 個の Mvalues へのインデックスには少なくとも 28 ビットかかるため、値と同時にインデックスを格納する必要があるアプローチは除外されます。実際には、元の (おそらく 32 ビット) 浮動小数点値と同じスペースを取る 32 ビットが本当に必要です。

考慮すべきアプローチの 1 つは、決定情報をビットマップに記録しながら元のデータの並べ替えを実行し、次に元のデータをランク インデックスに置き換え、ログを使用して順列を逆にすることです。

ただし、結果の順列には、最悪の場合、少なくともlog2(N!) > N log2(N) - N log2(e)ビットのストレージが必要になります (したがって、基数ソートなどを使用してそれを回避する方法はありません)。指定された問題については、元のデータセットとほぼ同じ大きさで、指定された補助スペースよりもはるかに大きなlog2(200M)>27ログが必要になる可能性があることに注意してください。(200M * 25.5) / (8bits/byte) ~ 608 MiB

決定ログをディスクに書き込み、それを読み直して回答を生成できます。ただし、ディスク I/O を許可している場合は、代わりに外部ソートを実行することもできます。これにより、メモリが保持できるよりもはるかに大きな問題を解決できるようになります。

于 2012-08-23T00:00:40.407 に答える
0

ウィキペディアで説明されているように、外部ソーティングを試みることができます。

floatデータを処理するときは、メモリマップトファイルを使用してみてください。

public static void main(String[] args) throws IOException {
    RandomAccessFile raf = new RandomAccessFile("floats.dat", "rw");
    FileChannel fc = raf.getChannel();
    MappedByteBuffer mbb = fc.map(FileChannel.MapMode.READ_WRITE, 0, 1024 * 1024 * 1024);
    FloatBuffer fb = mbb.asFloatBuffer();
    Random random = new Random();
    for (int i = 0; i < 200000000; i++) {
        float rand = random.nextFloat();
        fb.put(rand);
    }
    fb.flip();

    // Read data in chunks, tune the size
    float[] f = new float[100000];
    fb.get(f, 0, f.length);

    // Process the data using some merge strategy
}

私が理解しているように、float配列自体はソートされるべきではありません。メモリマップトファイルを使用してint配列も保存します。

于 2012-08-22T21:27:38.117 に答える
0

int値に基づいてフロートの範囲を並べ替えることができますFloat.floatToRawInt(float)。

1 GBがあり、値ごとに8バイトを格納する場合、最大1億2800万または2^27の値のグループをソートできます。これは、2^5または32パスでそれらすべてをランク付けできることを意味します。

于 2012-08-22T21:26:35.903 に答える
0

標準の Java ソート方法と float の配列を使用している場合は、スペース効率が高く高速な (n lg(n)) ソート方法 ( TimSort、MergeSort ) を既に使用しているため、~1.2GB の IMO で問題ありません。配列を参照してください。選別。

さらに高速にするには、浮動小数点数を整数に変換し (ただし、事前に精度を知っておく必要があります)、整数ソートまたは前述の基数ソートを適用します。

于 2012-09-02T21:35:54.530 に答える
0

配列を並べ替えたくはありませんが、並べ替え後の位置にあるインデックスの配列を取得したいと考えています。1 GB 以上のメモリが必要であり、おそらく後処理を行って、等しい要素を同じランクにする必要がありますが、このソリューションを出発点として使用できるはずです:インデックスを取得するソート後の配列の？

于 2012-08-22T21:19:27.067 に答える