2

我需要找到一个双精度数组的中值（在 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) 算法，该算法会在球场上。我会试试这个，看看它有多准确。

两通。

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

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

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

于 2010-12-29T22:34:26.497 回答
2

随机选择少量数组元素，并找到其中的中位数。

于 2010-12-29T21:38:57.210 回答
2

继 OPs 的问题之后：如何从更大的数组中提取 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 回答