2

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

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

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

4

1 回答 1

1

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

就个人而言，我认为您的插值想法很优雅。

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

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

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

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

于 2012-12-08T16:38:24.967 回答