我正在尝试实现分而治之算法,以使用 JavaScript 在随机生成的点集中找到最近的一对点。该算法应该在 O(n log n) 时间内运行,但它比简单的蛮力算法运行时间要长得多,后者应该是 O(n^2)。
我创建了两个 jsfiddle,为 16000 个点的数组计算算法时间:
我的假设是,分而治之之所以如此缓慢,是因为 JavaScript 数组实际上是哈希表。是否有可能显着加快 JavaScript 中的算法?如果是这样,执行此操作的最佳方法是什么?
最佳答案
一眼看去,您的合并函数分配了过多的内存(大致顺序为 O(n^2))。我做了一个 hacky 的方法来测量这个 here .基本思想是我在全局范围内只有一个计数器,并在每次调用时添加由 merge 生成的数组的大小。希望这些信息足以让您修复它,如果您遇到更多问题,我很乐意提供一些额外的建议。
另外,仅仅通过玩弄数字就很容易排除它是哈希表问题* - 被哈希表减慢的算法不会表现出比 O(n log n) 更快的增长率,它只会开始缓慢并沿着相同的路线增长。但是,如果您尝试一系列值,很明显它的增长速度比这快,这表明存在不同的问题。
*javascript 数组的内部实现比它们只是对象要复杂一点,但就我试图说明的观点而言,这并不重要
关于javascript - JavaScript 中的最近对算法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/12926975/