Эффективность / скорость для тригонометрических функций

Question

В игре, которую я делаю, у меня есть две точки, pt1 и pt2, и я хочу определить угол между ними. Я уже определил расстояние в более раннем расчете. Очевидным способом было бы вычислить горизонтальное расстояние на вертикальном расстоянии (tan (theta) = opp / adj).

Мне интересно, хотя, поскольку я уже рассчитал расстояние, будет ли быстрее использовать арксинус / арккосин с расстоянием и dx или dy?

Кроме того, можно ли мне лучше предварительно рассчитать в таблице?

Answer 1

Помимо всех мудрых комментариев относительно преждевременной оптимизации, давайте просто предположим, что это горячая точка и проведем тест frigg'n :

Время указывается в наносекундах и масштабируется для нормализации «acos» между системами.
«acos» просто предполагает единичный радиус, то есть acos(adj), тогда как «acos + div» означает acos(adj/hyp).

Система 1 - i5 с частотой 2,4 ГГц, работающая под управлением Mac OS X 10.6.4 (gcc 4.2.1)
Система 2 представляет собой Core2 Quad 2,83 ГГц под управлением Red Hat 7 Linux 2.6.28 (gcc 4.1.2)
Система 3 представляет собой процессор Atom N280 с тактовой частотой 1,66 ГГц и Ubuntu 10.04 2.6.32 (gcc 4.4.3)
Система 4 представляет собой Pentium 4 2,40 ГГц, работающий под управлением Ubuntu 10.04 2.6.32 (gcc 4.4.3)

Резюме: Относительная производительность по всей карте. Иногда atan2 быстрее, иногда медленнее. Очень странно, что в некоторых системах выполнение acos с разделением происходит быстрее, чем без него. Тест на собственной системе: - /

Answer 2

Я подозреваю, что здесь есть риск преждевременной оптимизации. Кроме того, будьте осторожны с вашей геометрией. Ваш противоположный / соседний подход - это свойство прямоугольных треугольников, это то, что у вас есть на самом деле?

Я предполагаю, что ваши точки плоские, и поэтому для общего случая они неявно представляют два вектора из начала координат (назовите их v1 v2), поэтому ваш угол равен

theta = arccos (точка (v1, v2) / (| v1 || v2 |)) где |. | длина вектора.

Ускорение (при необходимости) будет зависеть от многих вещей. Вы знаете длины векторов или должны их вычислять? Как быстро вы можете сделать точечный продукт в вашей архитектуре. Насколько быстро acos? В какой-то момент могут помочь такие хитрости, как поиск в таблице (возможно, интерполированный), но это будет стоить вам точности.

Это все компромиссы, хотя, на самом деле, нет общего ответа на ваш вопрос.

[редактировать: добавлен комментарий]

Я хотел бы еще раз подчеркнуть, что частая игра в "x - самый быстрый", в любом случае, немного напоминает игру с современными процессорами и компиляторами. Вы не узнаете, пока не измерите его и не начнете создавать сгенерированный код Когда вы дойдете до того, что на этом уровне действительно заботитесь о (надеюсь, небольшом) фрагменте кода, вы можете детально узнать, что делает ваша система. Но это кропотливо. Может быть, стол это хорошо. Но, возможно, у вас есть быстрые векторные вычисления и небольшой кеш. и т. д. и т. д. Это все зависит Извини насчет этого. С другой стороны, если вы не достигли точки, когда вы действительно сильно заботитесь об этом куске кода ... вам, вероятно, вообще не следует думать об этом на этом уровне. Сделать это правильно. Сделайте это чистым (что означает абстракцию, а также код). Тогда беспокойтесь о накладных расходах.

Answer 3

Если вы собираетесь делать это много раз, предварительно рассчитайте в таблице. Таким образом, производительность будет намного лучше.

Answer 4

Тонн хороших ответов здесь.

Кстати, если вы используете Math.atan2, вы получите 2π углов из него.

Я бы просто сделал это, а затем запустил бы это. Если вам не нравится скорость, и примеры показывают, что вы на самом деле в этом коде большую часть времени, а не где-то еще , попробуйте заменить его поиском по таблице. Если вам не нужна точность ближе 1 градуса, вы можете использовать довольно маленькую таблицу и интерполяцию.

Кроме того, вы можете запомнить функцию. Зачем пересчитывать то, что вы уже сделали недавно?

Добавлено: если вы используете таблицу, она должна охватывать только углы от 0 до 45 градусов (и может быть жестко запрограммирована). Вы можете получить все остальное по симметрии.

Answer 5

1. Если вас интересует нотация big-O, все методы, которые вы можете использовать, это O (1).

2. Если вам интересно, что работает быстрее всего, протестируйте его. Напишите функцию-обертку, которая вызывает предпочитаемый вами метод, но которую можно легко изменить, и протестируйте ее. Убедитесь, что ваше приложение тратит на это заметное количество времени, чтобы не тратить свое время впустую. Попробуйте любые способы, которые происходят с вами. В идеале, запустите его на нескольких разных процессорах.

Я стал очень осторожно предсказывать, что займет больше или меньше времени на современных процессорах. Раньше таблицы поиска служили ответом, если вам нужна скорость, но вы априори не знаете, как влияет кэширование или сколько времени потребуется, чтобы нормализоваться и посмотреть, по сравнению с тем, сколько времени потребуется, чтобы выполнить функцию триггера в конкретный процессор.

Answer 6

Получите это правильно первым! А потом профиль и оптимизировать. Таблица поиска является хорошим кандидатом, но обязательно сделайте правильный расчет, прежде чем делать что-то причудливое

Answer 7

С точки зрения скорости, лучше всего рассчитать предварительно рассчитанную таблицу и поиск с наиболее близким соответствием. Конечно, это связано с некоторыми накладными расходами, в зависимости от того, насколько точным является требуемый угол, но это того стоит, если вы выполняете этот расчет много (или в узком цикле), так как это будет дорогие расчеты.

Answer 8

Хотя другие очень правы, когда упоминают, что вы почти наверняка попадете в яму преждевременной оптимизации, когда они говорят, что тригонометрические функции - это O (1), они не рассказывают всю историю.

Большинство реализаций тригонометрических функций фактически равно O (N) в значении входной функции. Это связано с тем, что функции триггера наиболее эффективно рассчитываются на небольшом интервале, таком как [0, 2π) (или, для лучших реализаций, даже на меньших участках этого интервала, но этого достаточно для объяснения). Таким образом, алгоритм выглядит примерно так, в псевдо-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)

Даже микрокодированные инструкции процессора, такие как FSINCOS в x87, в конечном итоге делают что-то подобное внутри. Таким образом, тригональные функции, поскольку они являются периодическими, обычно требуют O (N) времени для сокращения аргументов. Однако есть две оговорки:

1. Если вам нужно вычислить тонну значений из основной области функций триггера, ваша математика, вероятно, не очень хорошо продумана.
2. Система обозначений Big-O скрывает постоянный коэффициент. Сокращение аргумента имеет очень маленький постоянный фактор, потому что это просто сделать. Таким образом, часть O (1) будет доминировать над частью O (N) практически для каждого входа.

Answer 9

Учитывая, что это для игры, вы, вероятно, заботитесь о скорости. Таблица поиска, безусловно, самая быстрая, но вы торгуете точностью за скорость с помощью этого метода. Итак, насколько точно вы должны соответствовать требованиям? Только ты можешь ответить на это. Прежде чем торговать с точностью, сначала определите, есть ли у вас проблемы со скоростью. Все тригонометрические функции рассчитываются с использованием численных методов (исследуйте численный анализ, чтобы узнать больше). Некоторые функции триггера имеют более дорогие методы, чем другие, потому что они основаны на последовательностях, которые сходятся медленнее, и кто знает, что ваш компьютер может иметь различные реализации этих функций, чем другой компьютер. В любом случае, вы можете узнать сами, насколько дорогими являются эти функции, написав несколько небольших программ, которые повторяют столько итераций, сколько пожелаете, с приращениями по вашему выбору, в то же время синхронизируя результаты. Тогда вы можете выбрать самый быстрый метод.