logo标签列表

使用计算方法还是查找表来提高正弦值的性能？

c#performancemathsignal-processing
20
假设您需要计算正弦（余弦或正切 - 任何一种）的值，其定义域在0.01到360.01之间。（使用C#）哪种方法更有效？
1. 使用Math.Sin
2. 使用预先计算好的查找数组
鉴于给定的定义域，我预计选项2会更快。在定义域的精度达到多少（0.0000n）时，计算的性能超过了查找数组的性能。
2
计算360000个不同的正弦值，单线程大约需要35毫秒时间（在AMD Quadcore 3 Ghz上）。你是否计算了这么多导致性能问题？你可以将任务分配到多个线程（和CPU内核）上来提升性能。 - Jeroen Landheer
3
这个应用程序是一种不平凡的数学应用，我们需要实现光谱信号的傅里叶变换 - 比如核磁共振。可能会有10^5-10^8次测量...重复计算相同的值似乎是浪费时间的。 - mson
1
这里有一个类似的问题，提供了更多的选择：https://dev59.com/iEjSa4cB1Zd3GeqPGIqn - Nosredna
@mson：很高兴你问了这个问题。我有一个Windows Mobile应用程序，可以对WAV文件进行FFT以呈现特定类型的可视化效果，使用基于数组的Sin函数近似方法似乎可以将此操作加速数倍（请参见我的评论，测试WinMo设备上的结果）。对于音频目的来说，这样的近似不起作用（会产生太多噪音），但对于可视化目的来说，它是完美的。 - MusiGenesis
@MusiGenesis，我的正弦近似不使用LUT，可以内联完成，通常足够快，最高噪声峰值低于信号的70dB。它是为音频设计的。当然不能保证一定会有效。:-) http://www.musicdsp.org/showArchiveComment.php?ArchiveID=241 - Nosredna
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和查找表之间的差异也很大。

不过，我不确定，我的带有Visual Studio的计算机在地下室，而且我太累了，不想花2分钟去确认这一点。

更新: 好吧，测试这个需要超过2分钟（20分钟左右），但看起来Math.Sin至少比使用查找表（使用Dictionary）快两倍。以下是使用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只是简单地查找。

这是在一台廉价笔记本电脑上（没有双核或任何花哨的东西）进行的测试。Robert，你是最棒的！（但我仍然认为我应该拿到支票，因为我做了这项工作）。

更新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要快一点，但差距不大。

请自行验证这些结果，因为我已经证明了我的无能。

1
哈哈，这就是你娶妻的原因...她要么替你做，要么唠叨着逼你去做... - mson
@Nosredna：我觉得你应该取笑我的秒表代码，而不是我的查找表。 :) - MusiGenesis
2
这应该是所选答案。 - San Jacinto
3
好的，我运行了你的基准测试，但没有包含所有无用的部分：没有单独的类来封装查找表，没有方法调用，也没有将双精度数转换为整数等。使用表查找的基准测试需要15毫秒，计算正弦值的基准测试需要415毫秒（在3.0 GHz的Pentium III上）。所以你的基准测试问题在于它测量了很多开销。我的基准测试问题（正如其他人已经指出的）在于整个基准测试期间查找表都被缓存。这两个基准测试都太简单了。 - Accipitridae
1
@Accipitridae，干得好。这正是为什么如果你需要速度，你要写两次代码并在现场测试它的原因。基准测试只能给出提示。我的实际经验是，在实际的dsp应用程序中（其中我的代码是运行在主机上并报告我使用的时间百分比的dll），库sin()是不可用的，但测试总是值得的。 - Nosredna
显示剩余26条评论
17

过去，数组查找是快速三角函数计算的良好优化方式。

但是，随着缓存命中、内置数学协处理器（使用表查找）和其他性能改进的出现，最好自己测试特定代码来确定哪种方法执行更佳。

2
我猜查找操作所需的处理时间要比计算正弦值要少得多。你确定计算sin(90.00001)比从一个小数组中读取sin(90.0)作为0更快吗？从先验上看，这似乎是胡扯... - mson
10
我曾经经常使用记忆化（预先计算的查找表）来加速图形例程（涉及大量正弦/余弦函数）。当他们将数学协处理器添加到CPU中时（使用表格查找），所有计算都可以在硬件上完成，因此成为不再是问题。现在，随着板载缓存的出现，较小的代码块可以为您提供显着的性能提升。如果用于存储表格的内存导致缓存未命中，则性能损失可能会很大。这不再是一个明确的问题。您几乎必须测试您的具体代码才能找出答案。 - Robert Cartaino
1
对于我的DSP用途来说，内置的sin函数只在初始化代码中使用，从不在运行时使用。相反，我使用查找表（LUTs）和各种近似方法。我必须针对每个应用程序决定哪个选择更好。 - Nosredna
@Nosredna - 是的。如果我有一个有限的、明确定义的数字集合，可以在初始化时进行预计算，那么将它们放入查找表以获得更快的运行时性能通常是一个不错的选择。关键是要计时你实际的应用程序。 - Robert Cartaino
即使没有有限的数字集，一个插值汇编LUT对于我的需求几乎总是比内置的sin函数更好。 - Nosredna
1
@henk 哈哈 - 我提出这个问题的原因是想听听那些遇到过这个问题的人的回答，而不是猜测... “去测量一下”这个答案我理解为 - 我对此事几乎没有任何想法或经验。Robert回答中有帮助的部分是他以前做过这种计算，并且结果可能会有两种可能性。 - mson
8

对于性能问题，唯一正确的答案是在测试之后得出的答案。但是，在测试之前，您需要确定测试的努力是否值得您的时间——这意味着您已经确定了性能问题。

如果您只是好奇，可以轻松编写一个测试来比较速度。但是，请记住，为查找表使用内存可能会影响更大应用程序中的分页。因此，即使在您的小型测试中分页更快，它也可能会减慢使用更多内存的更大应用程序的速度。

3
这取决于您查找表中有多少值。您说“域介于0.01和360.01之间”，但是您没有说在该范围内可能使用多少个值，或者您需要多精确的答案。
为了在非科学环境中传达隐含含义而使用有效数字，请原谅我对此不抱期望。
仍需更多信息才能回答此问题。在0.01到360.01之间的值的预期分布是什么？除简单的sin()计算之外，您是否处理了大量的数据？
36000个双精度值占用超过256k的存储器；查找表太大，无法适合大多数机器上的L1高速缓存；如果直接遍历表格，则每次访问sizeof(cacheline)/sizeof(double)时，都会错过L1，并且可能会击中L2。另一方面，如果您的表格访问比较随机，则几乎每次进行查找时都会错过L1。
这还很大程度上取决于您所在平台的数学库。例如，i386常见的sin函数实现取决于您的确切微架构和库供应商，从约40个周期到400个周期甚至更多。我没有计时微软库，因此不知道C# Math.sin实现将落在哪里。
由于来自L2的负载通常比合理平台上的40个周期更快，因此可以合理地期望在孤立考虑查找表时速度更快。但是，我怀疑您并非孤立计算sin()；如果sin()的参数跳到整个表格上，则会将其他步骤所需的其他数据从高速缓存中清除。虽然sin()计算变得更快，但对计算的其他部分的减速可能超过加速。只有仔细测量才能真正回答这个问题。
请问，您是否正在作为FFT计算的一部分进行此操作？您需要自己制作FFT而不使用已经存在的众多极高质量的实现，有什么原因吗？
1
这是一个关于有效数字的链接...http://zh.wikipedia.org/wiki/有效数字 - mson
在编程中，除非另有说明，否则数字的精度由其类型确定。我也不认为有效数字对问题有任何意义。 - recursive
3
由于您提到傅里叶变换是一个应用程序，因此您可以考虑使用以下方程式计算正弦/余弦： sin(x+y) = sin(x)cos(y) + cos(x)sin(y) cos(x+y) = cos(x)cos(y) - sin(x)sin(y) 也就是说，您可以使用4次乘法从sin((n-1)*x), cos((n-1)*x)和常数sin(x), cos(x)迭代地计算n = 0, 1, 2...的sin(n*x), cos(n*x)。当然，这仅在您需要在算术序列上评估sin(x), cos(x)时才有效。 比较这些方法而不实际实现它们是很困难的。这在很大程度上取决于您的表格适合缓存的程度。
我曾尝试过使用这种方法来实现FFT，这是OP提到的一个应用程序。最终我仍然使用了表格，因为结果不需要很精确，所以一个小表就足够了。 - Accipitridae
使用相位旋转的合成器：http://www.tutututututu.de/synths/dsfsynthesis/dsfsynthesis.html - Nosredna
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倍）。

0

Math.Sin更快。编写此函数的人很聪明，当准确度更高、速度更快时使用表格查找，而当速度更快时使用数学计算。此领域没有什么特别之处，大多数三角函数实现的第一件事就是将其映射到一个有利的领域。

6
查找可能值为36000的域与查找可能值为360000000000000的域有很大的不同。 - mson
5
并非每种情况都需要同样的精度。编写这些函数的人很聪明，但并非神奇。 - Nosredna
啊，我明白了，你说的是域的精度，而不是它的范围。 - RBarryYoung
嗯，那是领域的精度，而不是领域的范围。 - RBarryYoung
0

由于您的查找表可能有数千个值，您可能希望拥有一个字典，在计算值时将其放入字典中，这样您只需要计算每个值一次，并使用C#函数进行计算。

但是，没有理由反复重新计算相同的值。

2
你必须小心处理这个问题。在某些情况下，字典查找可能比正弦计算更慢。 - Nosredna
我的观点是，你不能假设使用字典避免计算会加快速度。你必须尝试并测试它。说“没有理由一遍又一遍地重新计算相同的值”不一定正确，因为有时这样做更快。 - Nosredna
如果您选择使用字典路线，请最好预先加载所有预期的输入值，不要让任何其他输入被使用。如果您允许任意浮点数、双精度或甚至长整型值成为您的键，则可能会填满所有可用内存（或达到编译器允许的键/值对的最大数量）。 - Nosredna
为什么要预加载？如果你只在序列开始时清空字典，那么你只需要计算一次，然后进行查找，但是你不会知道你拥有什么。否则，你将不得不预先加载，然后进行估算，这可能足够接近，但是会增加一些额外的计算。 - James Black
预加载适用于实时应用程序。您希望在初始化过程中执行任何缓慢的操作。但是，真正的问题在于确保所有输入都已知，以便不会用字典填满内存。如果有一些已知的整数值进入，那么您是安全的。但在这种情况下，为什么不使用数组，它是直接地址而不是哈希？ - Nosredna
显示剩余4条评论
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接