Kev*_*vin 8 javascript algorithm performance
我正在尝试实现一种分而治之的算法,以使用JavaScript在随机生成的点集中找到最接近的点对.该算法应该在O(n log n)时间内运行,但运行时间比简单的强力算法要长得多,该算法应为O(n ^ 2).
我创建了两个jsfiddles,为16000个点的数组计算时间:
我的假设是分而治之是如此之慢,因为JavaScript数组实际上是哈希表.是否有可能在JavaScript中显着加快算法速度？如果是这样,那么最好的方法是什么？
乍一看，您的合并函数分配了太多内存（大约为 O(n^2)）。我在这里采用了一种巧妙的方法来衡量这一点。基本思想是我只是在全局范围内有一个计数器，并在每次调用时添加 merge 生成的数组的大小。希望这些信息足以帮助您解决问题，如果您遇到更多问题，我很乐意提供一些额外的指导。
此外，仅通过处理数字就很容易排除它是哈希表问题* - 由哈希表减慢的算法不会表现出比 O(n log n) 更快的增长率，它只会开始缓慢并增长沿着同样的路线。不过，如果您尝试一系列值，您会发现它的增长速度明显快于该值，这表明存在不同的问题。
* javascript 数组的内部实现比它们只是对象要复杂一些，但就我试图使其变得并不重要的观点而言
| 归档时间： |
|
| 查看次数： |
1380 次 |
| 最近记录： |