如何从一系列距离和时间中有效地找到最快的路段？
How do I efficiently find the fastest segments from a sequence of distances and times?
我的输入是一个 gpx 文件，其中包含一系列带时间戳的位置，就像你使用 GPS 运行 并告诉它记录你的轨迹时得到的那样。
带时间戳的位置彼此之间的距离不一定相等，或者彼此之间的时间增量不一定相等。
鉴于此输入，我想有效地找到 gpx 文件指示的所有不同距离的最高速度。
示例：
12:00:00 start
12:00:05 moved 100m
12:00:15 moved 100m
12:00:35 moved 200m
在这个例子中，正确答案是：
20.0 m/s at 100m
13.3 m/s at 200m
11.4 m/s at 400m
什么是（最好是相当有效地）计算这个的好算法？
澄清：我不仅仅在寻找最快的路段，那是微不足道的。我正在寻找赛道代表的最快速度，所有距离总计达到赛道长度。
如果有人上传了他们 运行 的马拉松 gpx 赛道，我想知道他们 运行 在那个马拉松比赛中最快的 100 米，最快的 200 米，最快的 300 米等等上。
假设您有一个 1,500 米的 gpx 航迹 运行，并且您想要这样做。所以你想要最快的 100、200、300、400，... 1,500 米。有：
15 100-meter segments
14 200-meter segments
13 300-meter segments
12 400-meter segments
...
2 1,400-meter segments
1 1,500-meter segment
计算出 15+14+13+12+...2+1 = (15^2-15)/2，或 105 个不同的线段以检查是否要计算 15 个不同的距离。
您可以在一次数组传递中完成此操作。只需初始化一个数组，其中包含您感兴趣的每个距离的当前 运行ning 总速度和最大速度。读取每个段时，减去最旧段的值，添加新的段值，重新计算平均速度，并在适当时更新最大速度。
该算法将要求您查看 (n^2-n)/2 个单独的拆分。无论如何，您都必须针对要计算的每个距离查看每个可能的拆分。您有 n 个数据点，并且您正在尝试确定 n 个不同的最佳分段时间。无论如何切片都是 O(n^2)。
但是您所说的数据量并不大，按照今天的标准肯定不是。一场马拉松只有42165米。如果您想要 100 米的分辨率，则需要 422 个距离的数组。您的代码将执行大约 178,084 次计算。现在即使是低端电脑也能做到这一点。
至于数据，我建议对 .gpx 文件进行预处理以生成恰好 100 米的数据点流。您可以单独执行此操作，也可以在计算拆分时将其作为读取数据的一部分来执行。这并不困难，而且会让您的其余代码更易于使用。
我的输入是一个 gpx 文件，其中包含一系列带时间戳的位置，就像你使用 GPS 运行 并告诉它记录你的轨迹时得到的那样。
带时间戳的位置彼此之间的距离不一定相等，或者彼此之间的时间增量不一定相等。
鉴于此输入，我想有效地找到 gpx 文件指示的所有不同距离的最高速度。
示例：
12:00:00 start
12:00:05 moved 100m
12:00:15 moved 100m
12:00:35 moved 200m
在这个例子中，正确答案是：
20.0 m/s at 100m
13.3 m/s at 200m
11.4 m/s at 400m
什么是（最好是相当有效地）计算这个的好算法？
澄清：我不仅仅在寻找最快的路段，那是微不足道的。我正在寻找赛道代表的最快速度，所有距离总计达到赛道长度。
如果有人上传了他们 运行 的马拉松 gpx 赛道，我想知道他们 运行 在那个马拉松比赛中最快的 100 米，最快的 200 米，最快的 300 米等等上。
假设您有一个 1,500 米的 gpx 航迹 运行，并且您想要这样做。所以你想要最快的 100、200、300、400，... 1,500 米。有：
15 100-meter segments
14 200-meter segments
13 300-meter segments
12 400-meter segments
...
2 1,400-meter segments
1 1,500-meter segment
计算出 15+14+13+12+...2+1 = (15^2-15)/2，或 105 个不同的线段以检查是否要计算 15 个不同的距离。
您可以在一次数组传递中完成此操作。只需初始化一个数组，其中包含您感兴趣的每个距离的当前 运行ning 总速度和最大速度。读取每个段时，减去最旧段的值，添加新的段值，重新计算平均速度，并在适当时更新最大速度。
该算法将要求您查看 (n^2-n)/2 个单独的拆分。无论如何，您都必须针对要计算的每个距离查看每个可能的拆分。您有 n 个数据点，并且您正在尝试确定 n 个不同的最佳分段时间。无论如何切片都是 O(n^2)。
但是您所说的数据量并不大，按照今天的标准肯定不是。一场马拉松只有42165米。如果您想要 100 米的分辨率，则需要 422 个距离的数组。您的代码将执行大约 178,084 次计算。现在即使是低端电脑也能做到这一点。
至于数据，我建议对 .gpx 文件进行预处理以生成恰好 100 米的数据点流。您可以单独执行此操作，也可以在计算拆分时将其作为读取数据的一部分来执行。这并不困难，而且会让您的其余代码更易于使用。