The closest pair algorithm in JavaScript

Question

I am trying to implement a separation and subjugation algorithm to find the closest pair of points in a randomly generated set of points using JavaScript. This algorithm should run in O (n log n) time, but it takes significantly more time than a simple brute force algorithm, which should be O (n ^ 2).

I created two jsfiddles, the time of which is the algorithms for an array of 16,000 points:

• Divide and conquer
• Brute force

My hypothesis is that separation and victory are so slow because JavaScript arrays are actually hash tables. Is it possible to significantly speed up the algorithm in JavaScript? If so, what would be the best way to do this?

Answer 1

At first glance, your merge function allocates too much memory (roughly of the order of O (n ^ 2)). I made a hacker way to measure this one here . The main idea is that I have a counter in the global scope, and add the size of the array generated by the merge every time it is called. Hope this is enough information for you to fix it, if you have any other problems, I would be happy to provide some additional pointers.

In addition, just playing with numbers, it is quite easy to exclude that this is a hash table problem * - the algorithm noticed by the hash table will not have a faster growth rate than O (n log n), it will just start slowly and grow in the same lines. If you try a series of values, however, it should become obvious that it is growing faster than that, suggesting another problem.

* The internal implementation of javascript arrays is a bit more complicated than just objects, but it doesn't matter what I'm trying to do.