2

データの幾何平均を見つけたいのですが、パフォーマンスは重要です。
どちらを選ぶべきか

  1. 単一変数の乗算を維持し、計算の最後に N 乗根を取る 

    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 より大きい多数の数値を掛け合わせると、積を格納する 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

したがって、乗算はより高速に表示されます。

ただし、乗算はオーバーフローとアンダーフローで非常に問題があるため、積がオーバーフローせず、積がゼロに近づきすぎないことを保証できない限り、対数アプローチをお勧めします。

于 2012-09-12T23:01:47.010 に答える