正弦值性能的计算与查找表？

Question

假设您必须计算域在0.01到360.01之间的正弦(余弦或正切 - 无论如何).(使用C#)

什么会更高效？

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

我会反驳说,鉴于域名,选项2会快得多.在域精度(0.0000n)的什么时刻,计算的性能超过了查找.

Answer 1

更新:直读到最后.看起来查找表比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的速度至少是查找表的两倍(使用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执行得更差.此外,这个结果更有利于使用Math.Sin,因为SinBuddy.Sin进行乘法以将度数转换为每次调用时的弧度角度,而SinBuddy.SinLookup只进行直接查找.

这是一台便宜的笔记本电脑(没有双核或任何花哨的东西).罗伯特,你这个男人!(但我仍然认为我应该接受检查,因为我做了工作).

更新2:好的,我彻底迟钝了.事实证明停止并重新启动秒表并没有重置经过的毫秒,所以查找只有一半的速度,因为它的时间包括Math.Sin调用的时间.此外,我重读了这个问题,并意识到你正在谈论在一个简单的数组中缓存值,而不是使用Dictionary.这是我修改过的代码(我将旧代码留作后代警告):

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快一点,但不是很多.

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

Answer 2

过去,数组查找是执行快速触发计算的一个很好的优化.

但是对于缓存命中,内置数学协处理器(使用表查找)和其他性能改进,最好自己计算特定代码以确定哪些代码会更好.

Answer 3

对于性能问题,唯一正确的答案是您在测试后达到的答案.但是,在测试之前,您需要确定测试的工作是否值得花时间 - 这意味着您已经确定了性能问题.

如果您只是好奇,可以轻松编写测试来比较速度.但是,您需要记住,使用查找表的内存可能会影响较大应用程序中的分页.因此,即使在小测试中分页速度更快,也可能会在使用更多内存的较大应用中降低速度.