Lua: Расчет длины вектора оптимизации кода

Question

У меня есть сценарий в игре с функцией, которая вызывается каждую секунду.Расстояния между объектами игрока и другими игровыми объектами рассчитываются каждую секунду.Проблема в том, что за одну секунду может быть до 800 вызовов функций (до 40 игроков * 2 основных объекта (от 1 до 10 подобъектов)).Я должен оптимизировать эту функцию для меньшего количества обработки.это моя текущая функция:

local square = math.sqrt;

local getDistance = function(a, b)
    local x, y, z = a.x-b.x, a.y-b.y, a.z-b.z;
    return square(x*x+y*y+z*z);
end;

-- for example followed by: for i = 800, 1 do getDistance(posA, posB); end

Я обнаружил, что локализация функции math.sqrt через

local square = math.sqrt;

- это большая оптимизация в отношении скорости и кода

x*x+y*y+z*z

быстрее, чем этот код:

x^2+y^2+z^2

Я не знаю, лучше ли локализация x, y и z, чем использование метода класса "."в два раза, так что, возможно, square(a.x*b.x+a.y*b.y+a.z*b.z) лучше, чем код local x, y, z = a.x-b.x, a.y-b.y, a.z-b.z; square(x*x+y*y+z*z);

Есть ли в математике лучший способ рассчитать длину вектора или в Lua есть больше советов по производительности?

Answer 1

Вы должны прочитать Советы по производительности Lua Роберто Иерусалимского (Роберто - главный архитектор Lua). Он касается некоторых небольших оптимизаций, о которых вы спрашиваете (таких как локализация библиотечных функций и замена экспонент их многовариантными эквивалентами). Что наиболее важно, он передает одну из самых важных и упущенных идей в инженерном деле: иногда лучшее решение включает изменение вашей проблемы. Вы не собираетесь исправлять утечку в 30 миллионов вычислений за счет уменьшения количества Циклы ЦП, на которые уходит расчет.

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

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

Или, как гласит открытие цитируемой статьи:

В Lua, как и в любом другом языке программирования, мы всегда должны следовать двум Принципы оптимизации программы:

Правило № 1: Не делайте этого.

Правило № 2: Пока не делайте. (только для экспертов)

Answer 2

Я искренне сомневаюсь, что такие микрооптимизации действительно помогают любому.

Вместо этого вы должны сосредоточиться на своих алгоритмах, как, например, избавиться от некоторых вычислений расстояния с помощью сокращения, прекратить вычислять квадратные корни значений для сравнения (совет: если a^2 <<code>b^2 и a> 0 и b> 0, затем a <<code>b) и т. Д. И т. Д.

Answer 3

Ваш подход "грубой силы" плохо масштабируется.

Под этим я подразумеваю то, что каждый новый объект / игрок, включенный в систему, значительно увеличивает количество операций:

 +---------+--------------+
 | objects | calculations |
 +---------+--------------+ 
 |      40 |        1600  |
 |      45 |        2025  |
 |      50 |        2500  |
 |      55 |        3025  |
 |      60 |        3600  |
...       ...            ...
 |     100 |       10000  |
 +---------+--------------+

Если вы продолжите сравнивать «все со всем», ваш алгоритм начнет занимать все больше и больше циклов ЦП, в квадратичной форме.

Лучшего варианта для оптимизации вашего кода не существует »тонкая настройка "математических операций или использование локальных переменных вместо ссылок.

Что действительно улучшит ваш алгоритм, так это устранение ненужных вычислений.

Наиболее очевидным примером будет невычисление расстояния между Player1 и Player2, если вы уже рассчитали расстояние между Player2 и Player1.Эта простая оптимизация должна сократить ваше время на половину .

Другая очень распространенная реализация состоит в разделении пространства на «зоны».Когда два объекта находятся в одной зоне, вы обычно рассчитываете пространство между ними.Когда они находятся в разных зонах, вы используете приближение.Идеальный способ разделения пространства будет зависеть от вашего контекста;Примером может быть разделение пространства на сетку, и для игроков на разных клетках используйте расстояние между центрами их квадратов, которое вы вычислили заранее.

В программировании есть целая ветвь, связанная сЭта проблема;Это называется космическим разделением.Дайте это посмотреть:

http://en.wikipedia.org/wiki/Space_partitioning

Answer 4

Серьезно?

Выполнение 800 из этих вычислений не должно занимать более 0,001 секунды - даже в Lua на телефоне.

Вы делали какое-то профилирование, чтобы увидеть, действительно ли это замедляет вас? Заменили ли вы эту функцию на «return (0)» для проверки улучшения производительности (да, функция будет потеряна).

Вы уверены, что он запускается каждую секунду, а не каждую миллисекунду?

Я не вижу проблемы с выполнением 800 простых действий за 1 секунду с 1987 года.

Answer 5

Если вы хотите вычислить sqrt для положительного числа a, возьмите рекурсивную последовательность

x_0 = a
x_n+1 = 1/2 * (x_n + a / x_n)

x_n переходит к sqrt(a) с n -> infinity.Первые несколько итераций должны быть достаточно быстрыми.

Кстати!Возможно, вы попытаетесь использовать следующую формулу для длины вектора instesd из стандарта.

local getDistance = function(a, b)
    local x, y, z = a.x-b.x, a.y-b.y, a.z-b.z;
    return x+y+z;
end;

Гораздо проще вычислить, а в некоторых случаях (например, если необходимо расстояние, чтобы узнать, близки ли два объекта)) это может действовать адекватно.