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

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

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

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

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

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

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

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

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

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

Это все компромиссы,

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

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

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

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

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

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

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

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

В то время как другие совершенно правы, говоря, что вы почти наверняка попадете в яму преждевременной оптимизации, когда они говорят, что тригонометрические функции - это 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)

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

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