Ich versuche, einen Divide and Conquer-Algorithmus zu implementieren, um mithilfe von JavaScript das nächste Punktepaar in einer zufällig generierten Menge 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 erstellt, die Zeit die Algorithmen für ein Array von 16000 Punkten:
Meine Hypothese ist, dass das Teilen und Überwinden so langsam ist, weil JavaScript-Arrays tatsächlich Hash-Tabellen sind. Ist es möglich, den Algorithmus in JavaScript deutlich zu beschleunigen? Wenn ja, was wäre der beste Weg, dies zu tun?
Auf einen Blick weist Ihre Merge-Funktion viel zu viel Speicher zu (ungefähr in der Reihenfolge O (n ^ 2)). Ich habe einen Hacky-Weg gemacht, um dieses hier 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 wenn man nur mit den Zahlen spielt, ist es ziemlich einfach auszuschließen, dass es sich um eine Hash-Tabelle handelt * - ein Algorithmus, der durch eine Hash-Tabelle verlangsamt wird, würde keine schnellere Wachstumsrate als O (n log n) aufweisen langsam und in der gleichen Richtung wachsen. 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, den ich versuche, macht es nicht wirklich wichtig
Tags und Links javascript algorithm performance