计算正弦值性能与查找表之间的关系? [英] Calculating vs. lookup tables for sine value performance?
问题描述
比方说，您必须计算域在0.01到360.01之间的正弦(余弦或切线-任意值). (使用C#)
Let's say you had to calculate the sine (cosine or tangent - whatever) where the domain is between 0.01 and 360.01. (using C#)
哪个表现更好?
- 使用Math.Sin
- 使用具有预先计算的值的查找数组
我要反驳给定的域，选项2会快得多.在域精度(0.0000n)的哪个点上，计算性能超过了查找范围.
I would anticpate that given the domain, option 2 would be much faster. At what point in the precision of the domain (0.0000n) does the performance of the calculation exceed the lookup.
推荐答案
更新:通读至结尾.看起来查找表毕竟比Math.Sin快.
我猜想查找方法会比Math.Sin快.我还要说，这会快很多，但是罗伯特的回答使我认为我仍然希望以此为基准进行确定.我做了很多音频缓冲区处理，并且我注意到这样的方法:
I would guess that the lookup approach would be faster than Math.Sin. I would also say that it would be a lot faster, but Robert's answer made me think that I would still want to benchmark this to be sure. I do a lot of audio buffer processing, and I've noticed that a method like this:
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与查找之间的差异也会很大.
If the difference between Math.Sin and a simple multiplication is substantial, I would guess that the difference between Math.Sin and a lookup would also be substantial.
我不知道，但是我的装有Visual Studio的计算机在地下室，我太累了，无法花2分钟的时间来确定这一点.
I dunno, though, and my computer with Visual Studio is in the basement, and I'm too tired to take the 2 minutes it would take to determine this.
更新:好的，测试耗时超过2分钟(大约20分钟)，但它看起来像 Math.Sin至少是查询表的两倍(使用字典).这是使用Math.Sin或查找表完成Sin的类:
Update: OK, it took more than 2 minutes (more like 20) to test this, but it looks like Math.Sin is at least twice as fast as a lookup table (using a Dictionary). Here's the class that does Sin using Math.Sin or a lookup table:
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只是进行直接查找.
Using a step value of 0.01 degrees and looping through the full range of values 200 times (as in this code) takes about 1.4 seconds using Math.Sin, and about 3.2 seconds using a Dictionary lookup table. Lowering the step value to 0.001 or 0.0001 makes the lookup perform even worse against Math.Sin. Also, this result is even more in favor of using Math.Sin, since SinBuddy.Sin does a multiplication to turn the angle in degrees into the angle in radians on every call, while SinBuddy.SinLookup just does a straight lookup.
这是在便宜的笔记本电脑上(没有双核或任何奇特的东西).罗伯特，你这个家伙！ (但我仍然认为我应该得到支票，因为我完成了工作.)
This is on a cheap laptop (no dual cores or anything fancy). Robert, you da man! (But I still think I should get the check, coz I did the work).
更新2 :好的，我是个白痴...事实证明，停止并重新启动Stopwatch不会重置经过的毫秒数，因此查找时间似乎只是速度的一半，因为包括Math.Sin调用的时间.另外，我重读了这个问题，意识到您正在谈论将值缓存在一个简单的数组中，而不是使用字典.这是我修改后的代码(我将旧代码留给后代以警告):
Update 2: OK, I am an idiot... It turns out stopping and restarting the Stopwatch doesn't reset the elapsed milliseconds, so the lookup only seemed half as fast because it's time was including the time for the Math.Sin calls. Also, I reread the question and realized you were talking about caching the values in a simple array, rather than using a Dictionary. Here is my modified code (I'm leaving the old code up as a warning to future generations):
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快，但幅度不大.
These results are quite different. Using Math.Sin takes about 850 milliseconds, the Dictionary lookup table takes about 1300 milliseconds, and the array-based lookup table takes about 600 milliseconds. So it appears that a (properly-written [gulp]) lookup table is actually a bit faster than using Math.Sin, but not by much.
由于我已经证明自己的能力不足，请您自己验证这些结果.
Please verify these results yourself, since I have already demonstrated my incompetence.
这篇关于计算正弦值性能与查找表之间的关系?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
