20

假设您必须计算域在 0.01 和 360.01 之间的正弦（余弦或正切 - 随便）。（使用 C#）

什么会更高效？

  1. 使用 Math.Sin
  2. 使用具有预先计算值的查找数组

我预计给定域，选项 2 会快得多。在域的精度（0.0000n）中，计算的性能在什么时候超过了查找。

4

8 回答 8

22

更新：通读到底。看起来查找表毕竟比 Math.Sin 快。

我猜查找方法会比 Math.Sin 更快。我也会说它会快很多，但罗伯特的回答让我觉得我仍然想确定这个基准。我做了很多音频缓冲区处理，我注意到这样的方法：

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 和查找之间的差异也会很大。

不过我不知道，我的装有 Visual Studio 的计算机在地下室，我太累了，无法花 2 分钟时间来确定这一点。

更新：好的，测试这个需要超过 2 分钟（更像 20 分钟），但看起来Math.Sin 至少是查找表的两倍（使用字典）。这是使用 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 秒，使用 Dictionary 查找表大约需要 3.2 秒。将步长值降低到 0.001 或 0.0001 会使查找对 Math.Sin 的性能更差。此外，这个结果更倾向于使用 Math.Sin，因为 SinBuddy.Sin 会在每次调用时将角度（度）转换为弧度（弧度），而 SinBuddy.SinLookup 只是进行直接查找。

这是在便宜的笔记本电脑上（没有双核或任何花哨的东西）。罗伯特，你这个男人！（但我仍然认为我应该得到支票，因为我做了工作）。

更新 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 毫秒，Dictionary 查找表大约需要 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

由于您提到傅立叶变换作为一个应用程序，您也可以考虑使用方程式计算您的正弦/余弦

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 ) 和带有 4 次乘法的常数 sin(x)、cos(x)。当然，这仅在您必须在算术序列上评估 sin(x)、cos(x) 时才有效。

在没有实际实施的情况下比较这些方法是很困难的。这在很大程度上取决于您的表与缓存的匹配程度。

于 2009-09-05T08:24:17.217 回答
2

答案完全取决于查找表中有多少值。您说“域在 0.01 和 360.01 之间”，但您没有说明可以使用该范围内的多少值，或者您需要的答案有多准确。 请原谅我没想到会在非科学背景下看到用于传达隐含含义的有效数字。

仍然需要更多信息来回答这个问题。0.01 和 360.01 之间的值的预期分布是什么？除了简单的 sin() 计算之外，您还在处理大量数据吗？

36000 个双精度值占用 256k 内存；查找表太大而无法放入大多数机器上的 L1 缓存中；如果您直接通过表运行，则每次 sizeof(cacheline)/sizeof(double) 访问都会错过 L1 一次，并且可能会命中 L2。另一方面，如果您的表访问或多或少是随机的，那么您几乎每次进行查找时都会丢失 L1。

它还很大程度上取决于您所在平台的数学库。例如，sin 函数的常见 i386 实现范围从约 40 个周期到 400 个周期甚至更多，具体取决于您的确切微架构和库供应商。我没有为 Microsoft 库计时，所以我不知道 C# Math.sin 实现的确切位置。

由于在一个健全的平台上，来自 L2 的加载通常比 40 个周期快，因此人们有理由期望查找表在孤立的情况下会更快。但是，我怀疑您是在孤立地计算 sin( ) ；如果你对 sin() 的论点越过整个表格，你将把你计算的其他步骤所需的其他数据从缓存中吹出；尽管 sin( ) 计算变得更快，但计算其他部分的减速可能超过加速。只有仔细测量才能真正回答这个问题。

我是否从您的其他评论中了解到您正在将其作为 FFT 计算的一部分？您是否有理由需要推出自己的 FFT，而不是使用已经存在的众多极高质量实现中的一种？

于 2009-09-05T03:56:42.270 回答
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

由于您的查找表中可能有数千个值，您可能想要做的是有一个字典，当您计算一个值时，将其放入字典中，因此您只计算每个值一次，并使用 C# 函数进行计算。

但是，没有理由一遍又一遍地重新计算相同的值。

于 2009-09-05T13:28:32.427 回答