寻找航点轨迹中最快的部分

Question

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

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

在一个天真的方法中，我会标准化和插入航点，以获得一个更精细的航点的列表，无论是固定的时间间隔或固定距离的步骤。然后，移动代表我的时间跨度的滑动窗口。将距离分开，并搜索符合我的标准的最佳子列表。有没有更好的方法？

Answer 1

优雅和高效在旁观者的眼中。

就我个人而言，我认为你的插值思想是优雅的。

我想象插值算法很容易建立，你将在后续数据上执行的搜索很容易执行。这可能会导致严密的代码，其正确性可以轻松验证。此外，插值算法可能已经存在并且是多用途的，所以您不必重复自己（DRY）。您建议的解决方案有利于将数据处理与数据分析分开。这种性质的模块化通常被认为是优雅的一个组成部分。

效率 - 我们在谈论速度，空间或代码行吗？您可以尝试将插值步骤与搜索步骤相结合以节省空间，但这可能会牺牲速度和代码简单性。当然，速度牺牲是因为多个查询无法利用先前的计算。

当您考虑代码的效率时，不用担心计算机如何处理它，或者如何编写代码。更深入地思考你的方法的内在时间复杂性。我怀疑插值和搜索都可以在O（N）时间内完成，在这种情况下，需要大量的数据才能使你陷入困境：很难使O（N）算法的性能非常糟糕。

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