c# - trigonometricas - tabla de secante

¿Cálculo frente a tablas de búsqueda para el rendimiento del valor seno?

Question

Digamos que tuvo que calcular el seno (coseno o tangente, lo que sea) donde el dominio está entre 0.01 y 360.01. (usando C #)

¿Qué sería más performante?

1. Usando Math.Sin
2. Usando una matriz de búsqueda con valores precalculados

Supongo que dado el dominio, la opción 2 sería mucho más rápida. En qué punto de la precisión del dominio (0.0000n) el rendimiento del cálculo supera la búsqueda.

Answer 1

Como menciona las transformadas de Fourier como una aplicación, también podría considerar calcular sus senos / cosenos usando las ecuaciones.

sin (x + y) = sin (x) cos (y) + cos (x) sin (y)

cos (x + y) = cos (x) cos (y) - sin (x) sin (y)

Es decir, puedes calcular sin (n * x), cos (n * x) para n = 0, 1, 2 ... iterativamente desde sin ((n-1) * x), cos ((n-1) * x ) y las constantes sin (x), cos (x) con 4 multiplicaciones. Por supuesto, eso solo funciona si tienes que evaluar sin (x), cos (x) en una secuencia aritmética.

Es difícil comparar los enfoques sin la implementación real. Depende mucho de cómo encajan sus tablas en los cachés.

Answer 2

Como puede tener miles de valores en su tabla de búsqueda, lo que puede hacer es tener un diccionario, y cuando calcule un valor, colóquelo en el diccionario, de modo que solo calcule cada valor una vez y use la función C # para hacer el cálculo.

Pero, no hay razón para volver a calcular el mismo valor una y otra vez.

Answer 3

Math.Sin es más rápido. Las personas que escribieron son inteligentes y utilizan las búsquedas de tablas cuando son precisas y más rápidas, y usan las matemáticas cuando es más rápido. Y no hay nada en ese dominio que lo haga particularmente más rápido, lo primero que hacen la mayoría de las implementaciones de funciones trigonométricas es mapear un dominio favorable de todos modos.

Answer 4

Para las preguntas de desempeño, la única respuesta correcta es la que llega después de las pruebas. Pero, antes de realizar la prueba, debe determinar si el esfuerzo de la prueba vale su tiempo, lo que significa que ha identificado un problema de rendimiento.

Si solo tienes curiosidad, puedes escribir fácilmente una prueba para comparar las velocidades. Sin embargo, deberá recordar que el uso de la memoria para la tabla de búsqueda puede afectar la paginación en aplicaciones más grandes. Entonces, incluso si la paginación es más rápida en su prueba pequeña, podría ralentizar las cosas en una aplicación más grande que usa más memoria.

Answer 5

Solía ​​ser que una búsqueda de matriz era una buena optimización para realizar cálculos rápidos de trigonometría.

Pero con los resultados de la memoria caché, los coprocesadores matemáticos integrados (que utilizan búsquedas de tablas) y otras mejoras de rendimiento, podría ser mejor programar su código específico para determinar cuál funcionará mejor.

Answer 6

La respuesta a esto depende completamente de cuántos valores hay en su tabla de búsqueda. Dice "el dominio está entre 0.01 y 360.01", pero no dice cuántos valores en ese rango podrían usarse, o qué tan precisa necesita que sean las respuestas. Perdóneme por no esperar ver dígitos significativos utilizados para transmitir un significado implícito en un contexto no científico.

Todavía se necesita más información para responder a esta pregunta. ¿Cuál es la distribución esperada de valores entre 0.01 y 360.01? ¿Está procesando una gran cantidad de datos que no sean el simple cálculo sin ()?

36000 valores de doble precisión toman más de 256k en la memoria; la tabla de búsqueda es demasiado grande para caber en el caché L1 en la mayoría de las máquinas; si está ejecutando directamente a través de la tabla, perderá L1 una vez por tamaño de acceso (cacheline) / sizeof (doble), y probablemente presione L2. Si, por otra parte, sus accesos a la mesa son más o menos aleatorios, le faltará L1 casi cada vez que realice una búsqueda.

También depende mucho de la biblioteca de matemáticas de la plataforma en la que estás. Las implementaciones comunes de i386 de la función sin, por ejemplo, van desde ~ 40 ciclos hasta 400 ciclos o incluso más, dependiendo de su proveedor exacto de microarquitectura y biblioteca. No he cronometrado la biblioteca de Microsoft, así que no sé exactamente dónde caerá la implementación de C # Math.sin.

Dado que las cargas de L2 son generalmente más rápidas que 40 ciclos en una plataforma sana, uno razonablemente espera que la tabla de búsqueda se considere más rápidamente de forma aislada. Sin embargo, dudo que estés calculando sin () en forma aislada; Si sus argumentos para sin () saltan por encima de la tabla, se eliminarán de la caché otros datos necesarios para otros pasos de su cálculo; Aunque el cálculo de sin () se acelera, la ralentización a otras partes de su cálculo puede superar con creces la aceleración. Sólo una medición cuidadosa puede responder esta pregunta.

¿Debo entender de tus otros comentarios que estás haciendo esto como parte de un cálculo de FFT? ¿Hay alguna razón por la que necesite rodar su propia FFT en lugar de usar una de las numerosas implementaciones de alta calidad que ya existen?

Answer 7

Actualización: leer hasta el final. Parece que la tabla de búsqueda es más rápida que Math.Sin, después de todo.

Supongo que el enfoque de búsqueda sería más rápido que Math.Sin. También diría que sería mucho más rápido, pero la respuesta de Robert me hizo pensar que todavía quería comparar esto para estar seguro. Hago mucho procesamiento de búfer de audio, y he notado que un método como este:

for (int i = 0; i < audiodata.Length; i++)
{
audiodata[i] *= 0.5;
}

se ejecutará significativamente más rápido que

for (int i = 0; i < audiodata.Length; i++)
{
audiodata[i] = Math.Sin(audiodata[i]);
}

Si la diferencia entre Math.Sin y una simple multiplicación es sustancial, supongo que la diferencia entre Math.Sin y una búsqueda también sería sustancial.

No sé, sin embargo, y mi computadora con Visual Studio está en el sótano, y estoy demasiado cansado para tomar los 2 minutos que tomaría determinar esto.

Actualización : OK, tomó más de 2 minutos (más como 20) probar esto, pero parece que Math.Sin es al menos el doble de rápido que una tabla de búsqueda (usando un Diccionario). Aquí está la clase que hace Sin usando Math.Sin o una tabla de búsqueda:

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);
}
}

Y aquí está el código de prueba / tiempo:

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());

El uso de un valor de paso de 0.01 grados y la repetición completa del rango de valores 200 veces (como en este código) toma aproximadamente 1.4 segundos con Math.Sin, y aproximadamente 3.2 segundos con una tabla de búsqueda en el Diccionario. Bajar el valor del paso a 0,001 o 0,0001 hace que la búsqueda tenga un desempeño aún peor contra Math.Sin. Además, este resultado es aún más favorable al uso de Math.Sin, ya que SinBuddy.Sin realiza una multiplicación para convertir el ángulo en grados en el ángulo en radianes en cada llamada, mientras que SinBuddy.SinLookup solo realiza una búsqueda directa.

Esto es en una computadora portátil barata (sin núcleos duales o algo sofisticado). Robert, tu hombre! (Pero sigo pensando que debería recibir el cheque, porque hice el trabajo).

Actualización 2 : OK, estoy completamente retrasado. Resulta que detener y reiniciar el Cronómetro no restablece los milisegundos transcurridos, por lo que la búsqueda solo pareció la mitad de rápida porque era hora de incluir el tiempo para las llamadas de Math.Sin. Además, volví a leer la pregunta y me di cuenta de que estaba hablando de almacenar en caché los valores en una matriz simple, en lugar de usar un Diccionario. Aquí está mi código modificado (dejaré el código antiguo como una advertencia para las generaciones futuras):

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);
}
}

Y el código de prueba / tiempo:

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());

Estos resultados son bastante diferentes. El uso de Math.Sin toma aproximadamente 850 milisegundos, la tabla de búsqueda del Diccionario toma aproximadamente 1300 milisegundos, y la tabla de búsqueda basada en matriz toma alrededor de 600 milisegundos. Así que parece que una tabla de búsqueda (correctamente escrita [gulp]) es en realidad un poco más rápida que usar Math.Sin , pero no mucho.

Por favor verifique estos resultados, ya que ya he demostrado mi incompetencia.