JavaScript を使用して、ランダムに生成されたポイントのセットで最も近いポイントのペアを見つけるために、分割統治アルゴリズムを実装しようとしています。このアルゴリズムは O(n log n) 時間で実行されるはずですが、O(n^2) であるはずの単純なブルート フォース アルゴリズムよりも実行にかなり時間がかかります。
16000 ポイントの配列のアルゴリズムの時間を計測する 2 つの jsfiddles を作成しました。
私の仮説は、JavaScript 配列は実際にはハッシュ テーブルであるため、分割統治が非常に遅いというものです。JavaScript でアルゴリズムを大幅に高速化することは可能ですか? もしそうなら、これを行うための最良の方法は何ですか？
一見すると、あなたのマージ関数はあまりにも多くのメモリを割り当てています (おおよそ O(n^2) のオーダー)。ここでこれを測定するためのハックな方法を作成しました。基本的な考え方は、グローバル スコープにカウンターがあり、呼び出されるたびにマージによって生成された配列のサイズを追加することです。うまくいけば、これで問題を解決するのに十分な情報が得られます。さらに問題が発生した場合は、いくつかの追加のポインターを提供させていただきます.
また、数値をいじるだけで、ハッシュ テーブルの問題である可能性を除外するのは非常に簡単です*。同じ線に沿って。ただし、値の範囲を試してみると、それよりも速く成長していることが明らかになり、別の問題が示唆されます.
*JavaScript配列の内部実装は、単にオブジェクトであるよりも少し複雑ですが、私が作ろうとしている点では、それは実際には問題ではありません