Nächster Paar-Algorithmus in JavaScript

Question

Ich versuche, einen Divide and Conquer-Algorithmus zu implementieren, um mithilfe von JavaScript das nächste Punktepaar in einer zufällig generierten Gruppe von Punkten zu finden. Dieser Algorithmus sollte in O (n log n) -Zeit laufen, aber es dauert erheblich länger als ein einfacher Brute-Force-Algorithmus, der O (n^2) sein sollte.

Ich habe zwei jsfiddles geschaffen, dass die Zeit die Algorithmen für eine Reihe von 16000 Punkte:

• Divide and Conquer
• Brute Force

Meine Hypothese ist, dass die Teile und Herrsche so langsam ist, weil JavaScript-Arrays sind tatsächlich Hashtabellen. Ist es möglich, den Algorithmus in JavaScript deutlich zu beschleunigen? Wenn ja, was wäre der beste Weg, dies zu tun?

Answer 1

Auf einen Blick weist Ihre Merge-Funktion viel zu viel Speicher zu (ungefähr Ordnung O (n^2)). Ich machte einen hacky Weg, um diese here zu messen. Die Grundidee ist, ich habe nur einen Zähler im globalen Bereich, und fügen Sie die Größe des Arrays von Merge jedes Mal, wenn es aufgerufen wird. Hoffentlich ist dies genug Info für Sie, um es zu beheben, wenn Sie weitere Probleme auftreten, würde ich gerne ein paar zusätzliche Hinweise geben.

Auch, indem sie mit den Zahlen spielt es ziemlich einfach ist, um auszuschließen, es ein Hash-Tabelle Problem sein * - ein Algorithmus von Hash-Tabelle verlangsamt würde nicht eine schnellere Wachstumsrate als O aufweist (n log n), wäre es nur Beginnen Sie langsam und wachsen Sie in die gleiche Richtung. Wenn Sie jedoch eine Reihe von Werten ausprobieren, sollte sich herausstellen, dass sie schneller wächst, was auf ein anderes Problem hindeutet.

* die interne Implementierung von JavaScript-Arrays ist ein bisschen komplizierter, als sie nur Objekte zu sein, aber für den Punkt Ich versuche es wirklich zu machen egal