c# - Math.Log 与几何平均数的乘法复杂度哪个更好？

Question

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

1. 保持对单个变量的乘法运算，并在计算结束时取 N 次方根

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

   因此，O(N) x 乘法复杂度 + O(1) x N 次根

2. 使用对数

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

   因此，O(N) x 对数复杂度 + O(1) x N 次除法 + O(1) 指数

3. 几何平均数的专用算法。有的话请告诉我。

Answer 1

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

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

但是，将许多大于 1 的数字相乘会使存储乘积的 double 溢出。但是，将小于 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 方法，除非您可以保证乘积不会溢出并且乘积不会太接近于零。