Eficiencia/velocidad para funciones trigonométricas

Question

En un juego que estoy haciendo, tengo dos puntos, pt1 y pt2, y quiero calcular el ángulo entre ellos. Ya he calculado la distancia, en un cálculo anterior. La manera obvia sería arctan la distancia horizontal sobre la distancia vertical (tan (theta) = opp/adj).

Me pregunto, sin embargo, como ya he calculado la distancia, ¿sería más rápido usar arcoseno/arcocoseno con la distancia y dx o dy?

Además, ¿podría ser mejor que prefiera calcular en una tabla?

Answer 1

Si va a hacer esto muchas veces, calcule previamente en una tabla. El rendimiento será mucho mejor de esta manera.

Answer 2

Desde el punto de vista de la velocidad pura, una tabla precalculada y una búsqueda de coincidencia más cercana sería lo mejor. Implica un poco de sobrecarga, por supuesto, dependiendo de qué tan fino necesite el ángulo, pero vale la pena si hace mucho este cálculo (o en un ciclo cerrado), ya que esos serán costosos cálculos

Answer 3

Sospecho que existe un riesgo de optimización prematura aquí. Además, ten cuidado con tu geometría. Su enfoque opuesto/adyacente es una propiedad de triángulos en ángulo recto, ¿es eso lo que realmente tiene?

Estoy asumiendo sus puntos son planas, y así para el caso general que tenerlos de manera implícita que representa dos vectores formar el origen (v1 v2 llamar a éstos), por lo que su ángulo es

theta = arccos (punto (v1, v2)/(| v1 || v2 |)) donde |. | es la longitud del vector

Hacer esto más rápido (asumiendo la necesidad) dependerá de muchas cosas. ¿Conoces las longitudes de los vectores, o tienes que calcularlos? ¿Qué tan rápido puede hacer un producto escalar en su arquitectura? ¿Qué tan rápido es acos? En algún momento, trucos como la búsqueda de tablas (probablemente interpolados) podrían ayudar, pero eso le costará precisión.

Sin embargo, todos son intercambios, realmente no hay una respuesta general a su pregunta.

[editar: Comentario añadido]

me gustaría volver a insistir en que a menudo jugando "x es más rápido" es un poco de un juego de tazas con las CPU moderna y compiladores de todos modos. No lo sabrá hasta que lo mida y rebaje el código generado. Cuando llegas al punto en el que realmente te importa a este nivel por un fragmento (con suerte pequeño) de código, puedes descubrir en detalle qué está haciendo tu sistema. Pero es laborioso. Tal vez una mesa es buena. Pero tal vez tengas cálculos rápidos de vectores y un pequeño caché. etc. etc. Todo equivale a "depende". Lo siento por eso. Por otro lado, si no ha alcanzado el que realmente le importa tanto este código ... probablemente no debería estar pensando en este nivel en absoluto. Hacer lo correcto. Hazlo limpio (lo que significa abstracción y código). Entonces preocúpate por la sobrecarga.

Answer 4

¡Consúmala correcta! Y luego perfila y optimiza. La búsqueda de tablas es un buen candidato, pero asegúrese de hacer su cálculo antes de hacer cualquier cosa.

Answer 5

Dado que esto es para un juego, probablemente le interese la velocidad. Una tabla de búsqueda es definitivamente la más rápida pero cambia la precisión de la velocidad con este método. Entonces, ¿qué tan preciso debe ser para cumplir con los requisitos? Solo tú puedes responder eso. Antes de cambiar la precisión, primero determine si tiene un problema de velocidad. Todas las funciones trigonométricas se calculan utilizando métodos numéricos (análisis numérico de investigación para obtener más información).Algunas funciones trigonométricas tienen métodos más costosos que otros porque dependen de series que convergen más lentamente y quién sabe, su computadora puede tener diferentes implementaciones para estas funciones que otra computadora. En cualquier caso, puede descubrir por sí mismo lo caras que son estas funciones escribiendo algunos pequeños programas que recorren tantas iteraciones como desee, con incrementos de su elección, al tiempo que mide el tiempo de los resultados. Entonces puedes elegir el método más rápido.

Answer 6

1. Si usted está interesado en la notación de orden O, todos los métodos que podría utilizar son O (1).

2. Si usted está interesado en lo que funciona más rápido, probarlo. Escriba una función de envoltura, una que llame a su método preferido pero que se pueda cambiar fácilmente y pruebe con eso. Asegúrese de que su aplicación invierta una cantidad considerable de tiempo en hacer esto, para que no pierda su propio tiempo. Prueba lo que te ocurra. Lo ideal es ejecutarlo en más de una CPU diferente.

Me he vuelto muy receloso de predecir lo que tomará más o menos tiempo en los procesadores modernos. Las tablas de búsqueda solían ser la respuesta si necesitaban velocidad, pero no se conocen a priori los efectos en el almacenamiento en caché o cuánto tiempo se tardará en normalizarse y buscar en comparación con el tiempo que tardará en realizar una función trigonométrica en un CPU particular

Answer 7

mientras que otros son muy justo mencionar que está casi seguro que caer en el pozo de la optimización prematura, cuando dicen que las funciones trigonométricas son O (1) no está diciendo toda la historia.

mayoría de las implementaciones de funciones trigonométricas son en realidad O (N) en el valor de la función de entrada. Esto se debe a que las funciones trigonométricas se calculan más eficientemente en un intervalo pequeño como [0, 2π) (o, para las mejores implementaciones, incluso partes más pequeñas de este intervalo, pero esa es suficiente para explicar las cosas). Por lo que el algoritmo es como la siguiente, en pseudo-Python:

def Cosine_0to2Pi(x): 
    #a series approximation of some kind, or CORDIC, or perhaps a table 
    #this function requires 0 <= x < 2Pi 

def MyCosine(x): 
    if x < 0: 
     x = -x 
    while x >= TwoPi: 
     x -= TwoPi 
    return Cosine_0to2Pi(x) 

Incluso microcodificado instrucciones de la CPU como el final de la FSINCOS x87 haciendo algo como esto internamente. Entonces, las funciones trigonométricas, porque son periódicas, generalmente toman O (N) tiempo para hacer la reducción del argumento. Sin embargo, hay dos advertencias:

1. Si tiene que calcular una tonelada de valores fuera del dominio principal de las funciones trigonométricas, su matemática probablemente no esté muy bien pensada.
2. La notación Big-O oculta un factor constante. La reducción de argumentos tiene un factor constante muy pequeño, porque es simple de hacer. Por lo tanto, la parte O (1) va a dominar la parte O (N) para casi cada entrada.

Answer 8

Toneladas de buenas respuestas aquí.

Por cierto, si se utiliza Math.atan2, se obtiene una 2π llena de ángulos fuera de él.

Simplemente lo haría, y luego lo ejecutaré a toda máquina. Si no le gusta la velocidad, y si las muestras muestran que en realidad está en ese código la mayor parte del tiempo y no en otro lugar, intente reemplazarlo con la búsqueda de tablas. Si no necesita precisión más cerca de 1 grado, puede usar una tabla bastante pequeña e interpolación.

Además, es posible que desee memorizar la función. ¿Por qué recalcular algo que ya hiciste recientemente?

Agregado: si utiliza una tabla, sólo tiene que cubrir ángulos de 0-45 grados (y que puede ser modificable). Puedes obtener todo lo demás por simetría.

Answer 9

Aparte de todos los sabios comentarios en relación con la optimización prematura, vamos a suponer que este es el punto de acceso y hacer un frigg'n benchmark:

horas están en nanosegundos, a escala para normalizar 'acos' entre los sistemas.
'acos' simplemente asume unidad de radio es decir acos(adj), mientras que 'acos + div' significa acos(adj/hyp).

sistema 1 es un i5 de 2,4 GHz con Mac OS X 10.6.4 (gcc 4.2.1)
Sistema 2 es un Core 2 Quad 2.83GHz ejecutando Red Hat Linux 2.6.28 7 (gcc 4.1.2)
Sistema 3 es un 1,66 GHz Atom N280 corriendo Ubuntu 10.04 2.6.32 (gcc 4.4.3)
Sistema 4 es un Pentium 2,40 GHz 4 con Ubuntu 10.04 2.6.32 (gcc 4.4.3)

Resumen: el rendimiento relativo está por todo el mapa. A veces atan2 es más rápido, a veces es más lento. Muy extraño, en algunos sistemas hacer acos con una división es más rápido que hacerlo sin ella. Prueba en su propio sistema: -/