Lua: 代码优化向量长度计算

2011-6-6 19:42:54
收藏：0
阅读：194
评论：5

我在游戏中有一个脚本，其中有一个函数每秒钟都会被调用。这里每秒钟计算一次玩家对象和其他游戏对象之间的距离。问题在于，在1秒钟内，理论上可能会有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 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性能提示吗？

原文链接 https://stackoverflow.com/questions/6257148

点赞
stackoverflow用户108796
stackoverflow用户108796

我真的怀疑这些微小的优化是否真的有所帮助。你应该专注于你的算法，比如通过修剪消除一些距离计算，停止计算用于比较的数值的平方根（提示：如果 a^2 < b^2 并且 a >0 且 b >0，则 a < b），等等。

2011-06-06 19:56:51
stackoverflow用户224848
stackoverflow用户224848

真的吗？

运行 800 个这样的计算不应该超过 0.001 秒——即使在手机上使用 Lua。

您是否进行了一些性能分析以查看它是否真的会减慢您的速度？您是否用“return（0）”替换了该函数以验证性能是否有所提高（是的，函数将丢失）。

您确定它是每秒而不是每毫秒运行？

自 1987 年以来，我还没有见过在 1 秒钟内运行 800 个简单的任何东西的问题。

2011-06-06 20:13:30
stackoverflow用户34799
stackoverflow用户34799

你应该阅读罗伯托·耶鲁萨利姆斯基（Lua 的首席架构师）的Lua 性能技巧。它涉及一些你所询问的小优化（例如将库函数本地化和用它们的乘法等价物替换指数）。最重要的是，它传达了工程中最重要但常被忽视的思想之一：有时改变问题是最好的解决方案。通过减少计算所需的 CPU 周期，你无法修复 3000 万次计算泄漏。

对于你特定的距离计算案例，你会发现最好让你的基础计算返回表示平方距离的中间和，而允许使用案例仅在需要时调用最终的勾股定理步骤，这通常是不需要的（例如，你不需要执行平方根操作来比较两个平方长度哪个更长）。

然而，在讨论优化之前，你应该考虑此问题：不要担心不是“问题”的问题。与其搜寻你代码中任何“可能”的问题，直接解决最“大”的问题。如果性能超过缺失功能、错误和／或用户体验缺陷并成为你最突出的瓶颈语句，那么微小的低效率很难累积到超过这个瓶颈。

正如引用文章开头所述：

在 Lua 中，就像在任何其他编程语言中一样，我们应该始终遵循两个最大化程序的优化规则：

规则 # 1： 不要这样做。

规则 # 2： _还不要这样做。_（仅适用于专家）

2011-06-06 20:16:21
stackoverflow用户574686
stackoverflow用户574686

如果你想计算正数a的平方根，则采用递归序列

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

当n -> infinity时，x_n趋近于sqrt(a)。前几次迭代应该足够快。

顺便说一句！也许你会尝试使用以下向量长度公式，而不是标准公式。

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;

这样计算更加容易，在某些情况下（例如，需要知道距离以确定两个物体是否接近），它也可能会表现得很好。

2011-06-06 20:43:22
stackoverflow用户312586
stackoverflow用户312586

你的“暴力”方法不会很好地扩展。

我的意思是每个新的对象/玩家加入系统，都会显著增加操作数量：

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

如果你一直在“所有东西都与所有东西进行比较”，你的算法将会成二次复杂度地增长。

优化你的代码最好的选择并不是“微调”数学操作或使用本地变量而不是引用。

真正推动你的算法的事情将是消除你不需要的计算。

最显而易见的例子就是如果你已经计算出Player2与Player1的距离，那么就不要再计算Player1和Player2之间的距离。这个简单的优化应该能将你的时间减少一半。

另一个非常常见的实现方法是将空间分为“区域”。当两个对象在同一区域内时，你正常计算它们之间的距离。当它们在不同的区域内时，你则使用近似值计算。理想的空间分割方式将取决于你的环境；一个例子是将空间分割成网格，在不同方格的玩家之间，使用他们方格中心之间的距离，这个你预先计算过）。

有一整个编程分支正在处理这个问题；它被称为空间划分。看看这个：

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

2011-06-06 21:23:07

作者:

stackoverflow用户786442

stackoverflow用户786442
推荐文章