一連の距離と時間から最も速いセグメントを効率的に見つける方法を教えてください。

Question

私の入力は、GPSを使って走ってトラックを記録するように指示したときのような、タイムスタンプのある位置のシーケンスを含むgpxファイルです。

タイムスタンプされた位置は、必ずしも互いに距離が等しくないか、または互いの時間 - デルタが同じである必要はありません。

この入力が与えられると、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トラックをアップロードした場合、そのマラソンで走った最速の100m、最速200m、最速300mなどを知りたいです。

Answer 1

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の異なる距離。

これは、アレイの1回のパスで行うことができます。関心のある距離の現在の合計と最大速度を含む配列を初期化するだけです。各セグメントを読み取るときに、最も古いセグメントの値を減算し、新しいセグメント値を追加し、平均速度を再計算し、必要に応じて最高速度を更新します。

アルゴリズムでは、（n^2-n）/ 2個の個別の分割を見る必要があります。あなたがどのようにそれを行うにしても、あなたが計算したいすべての距離について可能な分割をすべて見なければなりません。あなたはn個のデータポイントを持っており、n個の最良のスプリットタイムを決定しようとしています。それはO（n^2）の方法です。

しかし、あなたが話しているデータの量は、今日の基準では巨大ではありません。マラソンはわずか42165メートルです。 100メートルの解像度が必要な場合は、422の距離の配列が必要です。そしてあなたのコードは178,084回の計算の順番で行います。これは、最近ではローエンドのコンピュータでさえ可能です。

データに関しては、.gpxファイルを前処理して正確に100メートルのデータポイントのストリームを生成することをお勧めします。これを個別に行うこともできますし、分割を計算している間にデータを読み込むこともできます。それは難しいことではなく、コードの残りの部分を扱いやすくします。