与计算正弦值表现的查找表？(Calculating vs. lookup tables for si

2019-07-04 23:23发布

站内文章 / 后端开发
65 0 0

比方说，你必须计算正弦（余弦或正切 - 什么的），该域名是0.01和360.01之间。 （使用C＃）

什么是更好的性能？

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

我会anticpate，鉴于域，选项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分，将采取确定这一点。

更新 ：OK，花了超过2分钟（更像20）来测试这一点，但它看起来像Math.Sin至少快两倍，查找表 （使用词典）。 下面是用做或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;

    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：OK，我是一个白痴......原来，停止和重新启动秒表不会重置经过毫秒，因此查找似乎只是一半的速度，因为它的时间，包括为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毫秒。 所以才出现一个（正确设计的[一饮而尽]）查找表实际上是有点比使用Math.Sin快 ，但不是很大。

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



Answer 2:

它曾经是一个数组的查找是执行快速TRIG计算一个很好的优化。

但与高速缓存命中，内置的数学协处理器（使用查表）和其他性能方面的改进，它可能是最好的自己的时间特定的代码，以确定这将有更好的表现。



Answer 3:

出于性能方面的问题，唯一正确的答案是你测试后达到一个。 但是，你测试之前，你需要确定测试的努力是否值得你的时间 - 这意味着你已经确定性能问题。

如果你只是好奇，你可以很容易地编写一个测试来比较速度。 但是，你要记住，使用内存的查找表可以在较大的应用程序影响分页。 所以，即使寻呼是在你的小测试速度更快，它可能会在使用更多的内存较大的应用程序慢下来。



Answer 4:

既然你提到傅立叶变换为一个应用程序，你也可以考虑使用公式来计算你的正弦/余弦

的sin（x + Y）=的sin（x）cos（y）的+ COS（x）的SIN（y）的

COS（X + Y）= COS（x）的余弦（Y） - 的sin（x）SIN（y）的

即可以计算罪（N * X），COS（π* X），其中n = 0，1，2 ...反复从罪（第（n-1）* X），COS（第（n-1）* X ）和常量的sin（x），COS（x）的4个乘法。 当然，这前提是你必须评估工作的罪（x）的，在一个等差数列COS（X）。

该方法没有实际执行的比较是困难的。 这在很大程度上取决于你的表的匹配程度缓存。



Answer 5:

这个问题的答案完全取决于多少值都在你的查找表。 你说“的域名是0.01和360.01之间”，但你不说怎么在这个范围内的许多值可能被使用，或者你如何准确需要的答案是。 原谅我不希望看到用来传达一个非科学的语境隐含意义显著数字。

仍然需要更多的信息来回答这个问题。 什么是价值的0.01和360.01之间的预期分布？ 你处理了很多比简单的罪（）计算的其他数据的？

36000个精度值接管256K在存储器中; 查找表是太大，无法在大多数机器L1缓存; 如果你直接通过表运行，你就会错过一次L1的sizeof每（缓存行）/的sizeof（双）访问，并可能触及L2。 如果，另一方面，你的表的访问都或多或少随机的，你将几乎每次你做一个查找时间丢失L1。

这也取决于你的平台的数学库了很多。 正弦函数的通用i386的实现，例如，范围为40〜周期高达400次，甚至更多，这取决于你的确切微架构和库供应商。 我没有超时微软库，所以我完全不知道C＃的Math.sin实现将下降。

由于从L2载荷通常是在健全平台快于40个循环，一个合理的预计，查找表以孤立地更快考虑。 不过，我怀疑你计算在隔离罪（）; 如果你的论点罪（）活蹦乱跳的表，你会被吹需要为您计算出缓存的其他步骤的其他数据; 虽然罪（）计算变快，放缓你计算的其他部分可能超过大于加速。 只有仔细测量才能真正回答这个问题。

我是从你的其他意见要明白，你这样做是为FFT计算的一部分？ 是否有你需要推出的，而不是使用大量的极高质量的实现已经存在的一个自己的FFT理由吗？



Answer 6:

Math.Sin更快。 谁写的人是聪明的，用查表的时候都准确，速度更快，使用数学时速度更快。 并有关于域名没有什么使得它更快particularily，最三角函数的实现做的第一件事是无论如何下来映射到一个有利的域。



Answer 7:

正如你可能有成千上万的值在查找表中，你可能想要做的是有一本字典，当你计算的值，把它的字典，所以你只有每个值一次计算，并使用C＃功能做计算。

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



文章来源: Calculating vs. lookup tables for sine value performance?
标签： c# performance math signal-processing
举报

收藏的人(0)

Ta的文章 更多文章
登录 后发表评论
0条评论
还没有人评论过~