2

doubleの配列の中央値を（Javaで）変更せずに（選択が外れるように）見つけたり、多くの新しいメモリを割り当てたりする必要があります。正確な中央値を見つけることも気にしませんが、10％以内で問題ありません（したがって、中央値がソートされた配列を40％〜60％分割する場合は問題ありません）。

どうすればこれを効率的に達成できますか？

rfreak、ILMTitan、Peterからの提案を考慮して、私は次のコードを作成しました。

public static double median(double[] array) {
    final int smallArraySize = 5000;
    final int bigArraySize = 100000;
    if (array.length < smallArraySize + 2) { // small size, so can just sort
        double[] arr = array.clone();
        Arrays.sort(arr);
        return arr[arr.length / 2];
    } else if (array.length > bigArraySize) { // large size, don't want to make passes
        double[] arr = new double[smallArraySize + 1];
        int factor = array.length / arr.length;
        for (int i = 0; i < arr.length; i++)
            arr[i] = array[i * factor];
        return median(arr);
    } else { // average size, can sacrifice time for accuracy
        final int buckets = 1000;
        final double desiredPrecision = .005; // in percent
        final int maxNumberOfPasses = 10; 
        int[] histogram = new int[buckets + 1];
        int acceptableMin, acceptableMax;           
        double min, max, range, scale,
            medianMin = -Double.MAX_VALUE, medianMax = Double.MAX_VALUE;
        int sum, numbers, bin, neighborhood = (int) (array.length * 2 * desiredPrecision);
        for (int r = 0; r < maxNumberOfPasses; r ++) { // enter search for number around median
            max = -Double.MAX_VALUE; min = Double.MAX_VALUE; 
            numbers = 0;
            for (int i = 0; i < array.length; i ++)
                if (array[i] > medianMin && array[i] < medianMax) {
                    if (array[i] > max) max = array[i];
                    if (array[i] < min) min = array[i];
                    numbers ++;
                }
            if (min == max) return min;
            if (numbers <= neighborhood) return (medianMin + medianMax) / 2;
            acceptableMin = (int) (numbers * (50d - desiredPrecision) / 100);
            acceptableMax = (int) (numbers * (50d + desiredPrecision) / 100);
            range = max - min;
            scale = range / buckets;
            for (int i = 0; i < array.length; i ++)
                histogram[(int) ((array[i] - min) / scale)] ++;
            sum = 0;
            for (bin = 0; bin <= buckets; bin ++) {
                sum += histogram[bin];
                if (sum > acceptableMin && sum < acceptableMax)
                    return ((.5d + bin) * scale) + min;
                if (sum > acceptableMax) break; // one bin has too many values
            }
            medianMin = ((bin - 1) * scale) + min;
            medianMax = (bin * scale) + min;
            for (int i = 0; i < histogram.length; i ++)
                histogram[i] = 0;
        }
        return .5d * medianMin + .5d * medianMax;
    }       
}

ここでは、配列のサイズを考慮に入れています。小さい場合は、並べ替えて真の中央値を取得します。非常に大きい場合は、サンプリングしてサンプルの中央値を取得します。それ以外の場合は、値を繰り返しビンに入れて、中央値を許容範囲に絞り込むことができるかどうかを確認します。

このコードには問題はありません。誰かがそれで何か間違っているのを見たら、私に知らせてください。

ありがとうございました。

4

4 に答える 4

3

平均ではなく中央値を意味すると仮定します。また、かなり大きな double[] を使用していると仮定すると、コピーを並べ替えて正確な中央値を実行するためにメモリが問題になることはありません。...

追加のメモリ オーバーヘッドを最小限に抑えることで、O(n) アルゴリズムを実行して、大まかな範囲内に収めることができます。私はこれを試して、それがどれほど正確かを確認します。

2 つのパス。

最初のパスは、最小値と最大値を見つけます。最小値と最大値の間の等間隔の数値範囲を表すバケットのセットを作成します。2 回目のパスを作成し、各ビンにいくつの数字が入るかを「カウント」します。その後、中央値の妥当な見積もりを作成できるはずです。int[] を使用してバケットを格納する場合、1000 個のバケットを使用しても 4k しかかかりません。計算は高速である必要があります。

唯一の問題は精度であり、バケットの数を調整して、データ セットのエラー範囲に収まるようにする必要があると思います。

あなたが探しているエラー範囲を得るために正確なサイズを提供できるよりも、数学/統計のバックグラウンドが優れている人がいると確信しています.

于 2010-12-29T22:34:26.497 に答える
2

少数の配列要素を無作為に選び、それらの中央値を見つけます。

于 2010-12-29T21:38:57.210 に答える
2

OPの質問に続きます。はるかに大きな配列から N 個の値を抽出する方法。

次のコードは、大きな配列の中央値を見つけるのにかかる時間を示し、次に固定サイズの値の選択範囲の中央値を見つけるのにかかる時間を示します。固定サイズの選択には固定コストがありますが、元の配列のサイズが大きくなるにつれて、ますます不正確になります。

以下のプリント

Avg time 17345 us. median=0.5009231700563378
Avg time 24 us. median=0.5146687617507585

コード

double[] nums = new double[100 * 1000 + 1];
for (int i = 0; i < nums.length; i++) nums[i] = Math.random();

{
    int runs = 200;
    double median = 0;
    long start = System.nanoTime();
    for (int r = 0; r < runs; r++) {
        double[] arr = nums.clone();
        Arrays.sort(arr);
        median = arr[arr.length / 2];
    }
    long time = System.nanoTime() - start;
    System.out.println("Avg time " + time / 1000 / runs + " us. median=" + median);
}
{
    int runs = 20000;
    double median = 0;
    long start = System.nanoTime();
    for (int r = 0; r < runs; r++) {
        double[] arr = new double[301]; // fixed size to sample.
        int factor = nums.length / arr.length; // take every nth value.
        for (int i = 0; i < arr.length; i++)
            arr[i] = nums[i * factor];
        Arrays.sort(arr);
        median = arr[arr.length / 2];
    }
    long time = System.nanoTime() - start;
    System.out.println("Avg time " + time / 1000 / runs + " us. median=" + median);
}

オブジェクトを作成しないという要件を満たすために、固定サイズの配列を ThreadLocal に配置して、進行中のオブジェクト作成がないようにします。関数の速度に合わせて配列のサイズを調整します。

于 2010-12-30T01:04:02.613 に答える
0

1) 新しいメモリの量はどれくらいですか? データのソートされたコピーまたはデータへの参照を排除しますか?

2) データは反復的ですか (多くの異なる値がありますか)? はいの場合、ルックアップ マップと配列を使用して何かを実行できる可能性があるため、(1) に対する回答で問題が発生する可能性は低くなります。

3）「平均に近い」近似の典型的なケースは、O（n.log（n））である可能性が高くなります。ほとんどの並べ替えアルゴリズムは、病理学的データで O(n^2) に低下するだけです。さらに、正確な中央値は、(通常) O(n.log(n)) になるだけで、ソートされたコピーを用意できると仮定します。

4) ランダム サンプリング (a-la dan04) は、分布が適切に動作しない限り、平均値に近い値を選択するよりも正確である可能性が高くなります。たとえば、ポアソン分布と対数正規分布はどちらも平均に対する中央値が異なります。

于 2010-12-29T23:21:55.970 に答える