java - 不可变数组的近似中位数

Question

我需要找到一个 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;
    }       
}

这里我考虑到了数组的大小。如果它很小，那么只需排序并获得真正的中位数。如果它非常大，对其进行采样并获取样本的中值，否则迭代地对值进行分箱并查看中值是否可以缩小到可接受的范围。

我对这段代码没有任何问题。如果有人发现其中有问题，请告诉我。

谢谢。

Answer 1

假设您指的是中位数而不是平均数。还假设您正在使用相当大的 double[]，否则内存不会成为对副本进行排序和执行精确中位数的问题。 ...

只需最少的额外内存开销，您就可以运行一个 O(n) 算法，该算法将进入大致范围。我会试试这个，看看它有多准确。

两次通过。

首先找到最小值和最大值。创建一组表示最小值和最大值之间均匀分布的数字范围的桶。进行第二次传递并“计算”每个箱子中有多少数字。然后您应该能够对中位数做出合理的估计。如果使用 int[] 存储桶，则使用 1000 个桶只需花费 4k。数学应该很快。

唯一的问题是准确性，我认为您应该能够调整桶的数量以进入数据集的误差范围内。

我敢肯定，数学/统计背景比我更好的人可以提供精确的尺寸以获得您正在寻找的误差范围。