2

我想找到数据的几何平均值，性能确实很重要。
我应该选择哪一个

  1. 保持对单个变量的乘法并在计算结束时取 Nth-root 

    X = MUL(x[i])^(1/N)

    因此，O(N) x Multiplication Complexity + O(1) x Nth-root

  2. 使用对数 

    X = e ^ { 1/N * SUM(log(x[i])) }

    因此，O(N) x Logarithm Complexity + O(1) x Nth-division + O(1) Exponential

  3. 几何平均的专门算法。请告诉我是否有。

4

1 回答 1

1

我想我会尝试对此进行基准测试并进行比较，这是我的尝试。

比较很困难，因为数字列表需要足够大以使时间合理，因此 N 很大。在我的测试中，N = 50,000,000 个元素。

但是，将许多大于 1 的数字相乘会溢出存储乘积的双精度数。但是将小于 1 的数字相乘得到的总乘积非常小，除以元素的数量得到零。

还有几件事：确保所有元素都不为零，并且 Log 方法不适用于负元素。

（如果 C# 有一个带有第 N 个根函数的 BigDecimal 类，则乘法将不会溢出。）

无论如何，在我的代码中，每个元素都在 1 到 1.00001 之间

另一方面，日志方法没有溢出或下溢的问题。

这是代码：

class Program
{
    static void Main(string[] args)
    {
        Console.WriteLine("Starting...");
        Console.WriteLine("");

        Stopwatch watch1 = new Stopwatch();
        Stopwatch watch2 = new Stopwatch();

        List<double> list = getList();

        double prod = 1;

        double mean1 = -1;

        for (int c = 0; c < 2; c++)
        {
            watch1.Reset();

            watch1.Start();

            prod = 1;

            foreach (double d in list)
            {
                prod *= d;
            }

            mean1 = Math.Pow(prod, 1.0 / (double)list.Count);

            watch1.Stop();

        }

        double mean2 = -1;

        for (int c = 0; c < 2; c++)
        {
            watch2.Reset();

            watch2.Start();

            double sum = 0;

            foreach (double d in list)
            {
                double logged = Math.Log(d, 2);
                sum += logged;
            }

            sum *= 1.0 / (double)list.Count;

            mean2 = Math.Pow(2.0, sum);

            watch2.Stop();

        }
        Console.WriteLine("First way gave: " + mean1);
        Console.WriteLine("Other way gave: " + mean2);

        Console.WriteLine("First way took: " + watch1.ElapsedMilliseconds + " milliseconds.");
        Console.WriteLine("Other way took: " + watch2.ElapsedMilliseconds + " milliseconds.");

        Console.WriteLine("");
        Console.WriteLine("Press enter to exit");
        Console.ReadLine();
    }

    private static List<double> getList()
    {
        List<double> result = new List<double>();

        Random rand = new Random();

        for (int i = 0; i < 50000000; i++)
        {
            result.Add( rand.NextDouble() / 100000.0 + 1);
        }

        return result;
    }
}

我的计算机输出描述了两个几何平均值相同，但是：

Multiply  way took: 466 milliseconds
Logarithm way took: 3245 milliseconds

因此，乘法似乎更快。

但是乘法在溢出和下溢时非常有问题，所以我会推荐 Log 方法，除非你能保证乘积不会溢出并且乘积不会太接近于零。

于 2012-09-12T23:01:47.010 回答