java - 将等效公式翻译成代码并不能给出正确的结果

Question

我正在尝试计算一组数据的平均差平均值。我有两个(据说是等价的)公式来计算这个，其中一个比另一个(O^n2)更有效(O^n)。

问题在于，虽然低效的公式可以给出正确的输出，但高效的公式却不能。仅仅通过查看这两个公式，我就有一种预感它们并不等价，但我把它划掉了，因为推导是由一位静态学家在科学期刊上得出的。所以我假设问题出在我的翻译上。谁能帮我正确翻译高效函数吗？

效率低下的公式:

公式翻译效率低下(Java):

    public static double calculateMeanDifference(ArrayList<Integer> valuesArrayList)
    {
        int valuesArrayListSize = valuesArrayList.size();
        int sum = 0;

        for(int i = 0; i < valuesArrayListSize; i++)
        {
            for(int j = 0; j < valuesArrayListSize; j++)
                sum += (i != j ? Math.abs(valuesArrayList.get(i) - valuesArrayList.get(j)) : 0);
        }

        return new Double( (sum * 1.0)/ (valuesArrayListSize * (valuesArrayListSize - 1)));
    }

高效推导公式:

哪里(抱歉，不知道如何在这里使用 MathML):

• x(下标 i) = 第 i 个 order statistic数据集

• x(bar) = 数据集的平均值

高效的导出公式翻译(Java):

public static double calculateMean(ArrayList<Integer> valuesArrayList)
{
    double sum = 0;
    int valuesArrayListSize = valuesArrayList.size();

    for(int i = 0; i < valuesArrayListSize; i++)
        sum += valuesArrayList.get(i);

    return sum / (valuesArrayListSize * 1.0);
}

public static double calculateMeanDifference(ArrayList<Integer> valuesArrayList)
{
    double sum = 0;
    double mean = calculateMean(valuesArrayList);
    int size = valuesArrayList.size();

    double rightHandTerm = mean * size * (size + 1);
    double denominator = (size * (size - 1)) / 2.0;

    Collections.sort(valuesArrayList);
    for(int i = 0; i < size; i++)
        sum += (i * valuesArrayList.get(i) - rightHandTerm);

    double meanDifference = (2 * sum) / denominator;

    return meanDifference;
}

我的数据集由整数集合组成，每个整数都有一个以集合 [0,5] 为界的值。

随机生成这样的集合并对它们使用两个函数会产生不同的结果。低效的似乎是产生与所测量的结果一致的结果:集合中任意两个值之间的绝对平均差。

谁能告诉我我的翻译有什么问题吗？

编辑:我创建了一个更简单的实现，即 O(N)，前提是所有数据的值都限制在相对较小的集合内。该公式坚持第一种方法的方法，因此，给出了相同的结果(与导出公式不同)。如果它适合您的用例，我建议人们使用它而不是派生的有效公式，特别是因为当 N 很小时后者似乎给出负值。

高效、非派生翻译(Java):

public static double calculateMeanDifference3(ArrayList<Integer> valuesArrayList)
{
    HashMap<Integer, Double> valueCountsHashMap = new HashMap<Integer, Double>();

    double size = valuesArrayList.size();

    for(int i = 0; i < size; i++)
    {
        int currentValue = valuesArrayList.get(i);

        if(!valueCountsHashMap.containsKey(currentValue))
            valueCountsHashMap.put(currentValue, new Double(1));
        else
            valueCountsHashMap.put(currentValue, valueCountsHashMap.get(currentValue)+ 1);
    }

    double sum = 0;

    for(Map.Entry<Integer, Double> valueCountKeyValuePair : valueCountsHashMap.entrySet())
    {
        int currentValue = valueCountKeyValuePair.getKey();
        Double currentCount = valueCountKeyValuePair.getValue();

        for(Map.Entry<Integer, Double> valueCountKeyValuePair1 : valueCountsHashMap.entrySet())
        {
            int loopValue = valueCountKeyValuePair1.getKey();
            Double loopCount = valueCountKeyValuePair1.getValue();

            sum += (currentValue != loopValue ? Math.abs(currentValue - loopValue) * loopCount * currentCount : 0);
        }
    }

    return new Double( sum/ (size * (size - 1)));
}

Answer 1

您对 sum += (i * valuesArrayList.get(i) - rightHandTerm); 的解释错了，应该是sum += i * valuesArrayList.get(i); ，然后在您的 for 之后, double meanDifference = ((2 * sum) - rightHandTerm) / denominator;

两个方程产生大约相同的值，但它们不相等。不过，这应该对您有一点帮助。