20

ドメインが0.01から360.01の間である場合に、正弦（コサインまたはタンジェント-何でも）を計算する必要があるとしましょう。（C＃を使用）

よりパフォーマンスの高いものは何ですか？

  1. Math.Sinの使用
  2. 事前に計算された値を持つルックアップ配列を使用する

ドメインを考えると、オプション2の方がはるかに高速であると予想します。ドメインの精度（0.0000n）のどの時点で、計算のパフォーマンスがルックアップを上回りますか。

4

8 に答える 8

22

更新：最後まで読み通してください。結局、ルックアップテーブルはMath.Sinよりも高速であるように見えます。

ルックアップアプローチはMath.Sinよりも高速だと思います。また、はるかに高速になると思いますが、Robertの回答により、これを確実にベンチマークしたいと思いました。私は多くのオーディオバッファ処理を行っていますが、次のような方法に気づきました。

for (int i = 0; i < audiodata.Length; i++)
{
    audiodata[i] *= 0.5; 
}

よりも大幅に高速に実行されます

for (int i = 0; i < audiodata.Length; i++)
{
    audiodata[i] = Math.Sin(audiodata[i]);
}

Math.Sinと単純な乗算の違いが大きい場合、Math.Sinとルックアップの違いも大きいと思います。

でも、わかりません。VisualStudioを搭載したコンピューターは地下室にあり、疲れすぎて、これを判断するのに2分かかることはありません。

更新：OK、これをテストするのに2分以上（20分程度）かかりましたが、Math.Sinはルックアップテーブル（辞書を使用）の少なくとも2倍の速度であるように見えます。Math.Sinまたはルックアップテーブルを使用してSinを実行するクラスは次のとおりです。

public class SinBuddy
{
    private Dictionary<double, double> _cachedSins
        = new Dictionary<double, double>();
    private const double _cacheStep = 0.01;
    private double _factor = Math.PI / 180.0;

    public SinBuddy()
    {
        for (double angleDegrees = 0; angleDegrees <= 360.0; 
            angleDegrees += _cacheStep)
        {
            double angleRadians = angleDegrees * _factor;
            _cachedSins.Add(angleDegrees, Math.Sin(angleRadians));
        }
    }

    public double CacheStep
    {
        get
        {
            return _cacheStep;
        }
    }

    public double SinLookup(double angleDegrees)
    {
        double value;
        if (_cachedSins.TryGetValue(angleDegrees, out value))
        {
            return value;
        }
        else
        {
            throw new ArgumentException(
                String.Format("No cached Sin value for {0} degrees",
                angleDegrees));
        }
    }

    public double Sin(double angleDegrees)
    {
        double angleRadians = angleDegrees * _factor;
        return Math.Sin(angleRadians);
    }
}

そして、これがテスト/タイミングコードです：

SinBuddy buddy = new SinBuddy();

System.Diagnostics.Stopwatch timer = new System.Diagnostics.Stopwatch();
int loops = 200;

// Math.Sin
timer.Start();
for (int i = 0; i < loops; i++)
{
    for (double angleDegrees = 0; angleDegrees <= 360.0; 
        angleDegrees += buddy.CacheStep)
    {
        double d = buddy.Sin(angleDegrees);
    }
}
timer.Stop();
MessageBox.Show(timer.ElapsedMilliseconds.ToString());

// lookup
timer.Start();
for (int i = 0; i < loops; i++)
{
    for (double angleDegrees = 0; angleDegrees <= 360.0;
        angleDegrees += buddy.CacheStep)
    {
        double d = buddy.SinLookup(angleDegrees);
    }
}
timer.Stop();
MessageBox.Show(timer.ElapsedMilliseconds.ToString());

0.01度のステップ値を使用し、値の全範囲を200回ループする（このコードのように）には、Math.Sinを使用して約1.4秒、辞書ルックアップテーブルを使用して約3.2秒かかります。ステップ値を0.001または0.0001に下げると、Math.Sinに対するルックアップのパフォーマンスがさらに低下します。また、SinBuddy.Sinは乗算を実行して、呼び出しごとに度単位の角度をラジアン単位の角度に変換するのに対し、SinBuddy.SinLookupは単純なルックアップを実行するため、この結果はMath.Sinの使用をさらに支持します。

これは安価なラップトップ上にあります（デュアルコアや派手なものはありません）。ロバート、あなたは男だ！（しかし、私はまだチェックを受けるべきだと思います、私は仕事をしました）。

更新2：ストップウォッチを停止して再起動しても経過ミリ秒はリセットされないことが判明しました。そのため、Math.Sin呼び出しの時間が含まれていたため、ルックアップは半分の速度でしか見えませんでした。また、質問を読み直して、辞書を使用するのではなく、単純な配列に値をキャッシュすることについて話していることに気付きました。これが私の変更されたコードです（私は将来の世代への警告として古いコードを残しています）：

public class SinBuddy
{
    private Dictionary<double, double> _cachedSins
        = new Dictionary<double, double>();
    private const double _cacheStep = 0.01;
    private double _factor = Math.PI / 180.0;

    private double[] _arrayedSins;

    public SinBuddy()
    {
        // set up dictionary
        for (double angleDegrees = 0; angleDegrees <= 360.0; 
            angleDegrees += _cacheStep)
        {
            double angleRadians = angleDegrees * _factor;
            _cachedSins.Add(angleDegrees, Math.Sin(angleRadians));
        }

        // set up array
        int elements = (int)(360.0 / _cacheStep) + 1;
        _arrayedSins = new double[elements];
        int i = 0;
        for (double angleDegrees = 0; angleDegrees <= 360.0;
            angleDegrees += _cacheStep)
        {
            double angleRadians = angleDegrees * _factor;
            //_cachedSins.Add(angleDegrees, Math.Sin(angleRadians));
            _arrayedSins[i] = Math.Sin(angleRadians);
            i++;
        }
    }

    public double CacheStep
    {
        get
        {
            return _cacheStep;
        }
    }

    public double SinArrayed(double angleDegrees)
    {
        int index = (int)(angleDegrees / _cacheStep);
        return _arrayedSins[index];
    }

    public double SinLookup(double angleDegrees)
    {
        double value;
        if (_cachedSins.TryGetValue(angleDegrees, out value))
        {
            return value;
        }
        else
        {
            throw new ArgumentException(
                String.Format("No cached Sin value for {0} degrees",
                angleDegrees));
        }
    }

    public double Sin(double angleDegrees)
    {
        double angleRadians = angleDegrees * _factor;
        return Math.Sin(angleRadians);
    }
}

そしてテスト/タイミングコード：

SinBuddy buddy = new SinBuddy();

System.Diagnostics.Stopwatch timer = new System.Diagnostics.Stopwatch();
int loops = 200;

// Math.Sin
timer.Start();
for (int i = 0; i < loops; i++)
{
    for (double angleDegrees = 0; angleDegrees <= 360.0; 
        angleDegrees += buddy.CacheStep)
    {
        double d = buddy.Sin(angleDegrees);
    }
}
timer.Stop();
MessageBox.Show(timer.ElapsedMilliseconds.ToString());

// lookup
timer = new System.Diagnostics.Stopwatch();
timer.Start();
for (int i = 0; i < loops; i++)
{
    for (double angleDegrees = 0; angleDegrees <= 360.0;
        angleDegrees += buddy.CacheStep)
    {
        double d = buddy.SinLookup(angleDegrees);
    }
}
timer.Stop();
MessageBox.Show(timer.ElapsedMilliseconds.ToString());

// arrayed
timer = new System.Diagnostics.Stopwatch();
timer.Start();
for (int i = 0; i < loops; i++)
{
    for (double angleDegrees = 0; angleDegrees <= 360.0;
        angleDegrees += buddy.CacheStep)
    {
        double d = buddy.SinArrayed(angleDegrees);
    }
}
timer.Stop();
MessageBox.Show(timer.ElapsedMilliseconds.ToString());

これらの結果はまったく異なります。Math.Sinの使用には約850ミリ秒、ディクショナリルックアップテーブルには約1300ミリ秒、配列ベースのルックアップテーブルには約600ミリ秒かかります。 したがって、（適切に記述された[gulp]）ルックアップテーブルは、実際にはMath.Sinを使用するよりも少し高速ですが、それほど高速ではないようです。

私はすでに自分の無能さを示しているので、これらの結果を自分で確認してください。

于 2009-09-05T03:37:11.217 に答える
16

以前は、配列ルックアップが高速トリガー計算を実行するための優れた最適化でした。

ただし、キャッシュヒット、組み込みの数学コプロセッサー（テーブルルックアップを使用）、およびその他のパフォーマンスの向上により、特定のコードのタイミングを自分で設定して、どちらがパフォーマンスが向上するかを判断するのが最適な場合があります。

于 2009-09-05T03:03:20.677 に答える
8

パフォーマンスに関する質問の場合、正しい答えは、テスト後に到達するものだけです。ただし、テストを行う前に、テストの労力が時間の価値があるかどうかを判断する必要があります。つまり、パフォーマンスの問題を特定したことになります。

興味がある場合は、速度を比較するためのテストを簡単に作成できます。ただし、ルックアップテーブルにメモリを使用すると、大規模なアプリのページングに影響を与える可能性があることに注意する必要があります。そのため、小さなテストではページングが高速であっても、より多くのメモリを使用する大きなアプリでは速度が低下する可能性があります。

于 2009-09-05T03:02:14.613 に答える
2

これに対する答えは、ルックアップテーブルにある値の数に完全に依存します。「ドメインは0.01から360.01の間です」と言いますが、その範囲内の値がいくつ使用されるか、または答えがどれほど正確である必要があるかについては言いません。 非科学的な文脈で暗黙の意味を伝えるために使用される有効数字を見ることを期待していないことを許してください。

この質問に答えるには、さらに多くの情報が必要です。0.01から360.01の間の値の予想される分布は何ですか？単純なsin（）計算以外の多くのデータを処理していますか？

36000の倍精度値は、メモリ内で256kを超えます。ルックアップテーブルが大きすぎて、ほとんどのマシンのL1キャッシュに収まりません。テーブルをまっすぐ実行している場合、sizeof（cacheline）/ sizeof（double）アクセスごとに1回L1を見逃し、おそらくL2に到達します。一方、テーブルアクセスが多かれ少なかれランダムである場合、ルックアップを実行するたびにL1が失われます。

また、使用しているプラ​​ットフォームの数学ライブラリにも大きく依存します。たとえば、sin関数の一般的なi386実装は、正確なマイクロアーキテクチャとライブラリベンダーに応じて、最大40サイクルから最大400サイクルまたはそれ以上の範囲になります。私はMicrosoftライブラリの時間を計っていないので、C＃Math.sinの実装がどこにあるのか正確にはわかりません。

L2からのロードは、通常、正常なプラットフォームでは40サイクルよりも高速であるため、ルックアップテーブルを単独で検討する方が高速であると合理的に予想されます。ただし、sin（）を単独で計算しているとは思えません。sin（）の引数がテーブル全体にジャンプすると、計算の他のステップに必要な他のデータがキャッシュから吹き飛ばされます。sin（）の計算は高速化されますが、計算の他の部分への減速は、高速化を上回る可能性があります。注意深い測定だけがこの質問に本当に答えることができます。

他のコメントから、FFT計算の一部としてこれを行っていることを理解できますか？すでに存在する非常に高品質の実装の1つを使用する代わりに、独自のFFTをロールする必要がある理由はありますか？

于 2009-09-05T03:56:42.270 に答える
2

アプリケーションとしてフーリエ変換について言及しているので、方程式を使用して正弦/余弦を計算することも検討してください。

sin（x + y）= sin（x）cos（y）+ cos（x）sin（y）

cos（x + y）= cos（x）cos（y）-sin（x）sin（y）

つまり、sin（n * x）、cos（n * x）for n = 0、1、2 ...をsin（（n-1）* x）、cos（（n-1）*xから繰り返し計算できます。 ）および定数sin（x）、cos（x）と4回の乗算。もちろん、これは、等差数列でsin（x）、cos（x）を評価する必要がある場合にのみ機能します。

実際の実装なしでアプローチを比較することは困難です。それはあなたのテーブルがキャッシュにどれだけうまく収まるかに大きく依存します。

于 2009-09-05T08:24:17.217 に答える
1

Math.Sinの方が高速です。書いた人々は賢く、正確で速いときにテーブルルックアップを使用し、それが速いときに数学を使用します。そして、そのドメインについて特に高速にするものは何もありません。ほとんどの三角関数の実装が最初に行うことは、とにかく好ましいドメインにマップすることです。

于 2009-09-05T03:02:04.313 に答える
1

重大な調査を行って申し訳ありませんが、ルックアップテーブルのインデックスをすばやく作成するための優れたソリューションがあります： https ：//jvm-gaming.org/t/fast-math-sin-cos-lookup-tables/36660

Javaですが、C＃に移植するのに数分しかかかりません。テストを行ったところ、100000回の反復で次の結果が得られました。

Math.Sin: 0.043 sec
Mathf.Sin: 0.06 sec (Unity`s Mathf lib)
MathTools.Sin: 0.026 (lookup tables static class).

おそらくJavaでは50倍のブーストが得られます（または2011年にはそうなりましたが、2021年のC＃では違いは約2倍にすぎません）。

于 2021-09-14T09:07:48.513 に答える
0

ルックアップテーブルには数千の値がある可能性があるため、必要なのはディクショナリを用意することです。値を計算するときは、ディクショナリに入れて、各値を1回だけ計算し、C＃関数を使用します。計算を行います。

ただし、同じ値を何度も再計算する理由はありません。

于 2009-09-05T13:28:32.427 に答える