algorithm - 寻找航路点轨迹的最快部分

Question

运动追踪器应用程序通常会定期记录时间戳和位置，以便存储整个轨迹。然后，分析应用程序可以找到某些统计数据，例如在固定持续时间(例如 5 英里所需的时间)内具有最高速度的轨道分段。反之亦然，在特定时间跨度内经过的最长距离(例如 12 分钟内的 Cooper 距离)。

我想知道计算这些部分的最优雅和/或最有效的方法是什么。

在一种天真的方法中，我会对航点进行归一化和插值以获得更细粒度的航点列表，具有固定的时间间隔或固定的距离步长。然后，移动代表我的时间跨度的滑动窗口。对列表进行距离分割并搜索符合我的条件的最佳子列表。有没有更好的办法？

Answer 1

优雅与高效，见仁见智。

我个人认为你的插值思路很优雅。

我认为插值算法很容易构建，并且您将对后续数据执行的搜索也很容易执行。这会导致代码紧凑，其正确性很容易验证。此外，插值算法可能已经存在并且是多用途的，因此您不必重复自己(DRY)。您建议的解决方案具有将数据处理 与数据分析 分开的好处。这种性质的模块化通常被认为是优雅的组成部分。

效率——我们是在谈论速度、空间还是代码行数？您可以尝试将插值步骤与搜索步骤结合起来以节省空间，但这可能会牺牲速度和代码简洁性。从多个查询无法利用先前计算的意义上来说，当然会牺牲速度。

当您考虑代码的效率时，不要太担心计算机将如何处理它，或者您将如何编码。更深入地思考你的方法的内在时间复杂度。我怀疑插值和搜索都可以在 O(N) 时间内进行，在这种情况下，需要大量数据才能让你陷入困境:很难让 O(N) 算法执行得非常糟糕。

为了支持上述观点，插值只是估计两个值之间的中间点，因此这在值的数量上是线性的，在中间点的数量上也是线性的。搜索可以用 Knuth-Morris-Pratt Algorithm 的数字变体来完成。 , 这也是线性的。