NodeJS 为什么冒泡排序效率不高?

wgxvkvu9  于 2023-11-17  发布在  Node.js
关注(0)|答案(2)|浏览(109)

我正在使用node.js开发后端项目,并将实现排序产品功能。我研究了一些文章,有几篇文章说冒泡排序效率不高。冒泡排序在我以前的项目中使用过,我很惊讶为什么它不好。有人能解释为什么它效率低下吗?如果你能用c编程或汇编命令来解释,我将不胜感激。

ar5n3qh5

ar5n3qh51#

时间复杂度为O(N^2),所以它对于大型数组来说是垃圾,而对于大型数组来说,时间复杂度为O(N log N)。
在JS中,如果可能的话,使用内置的排序函数,JS运行时可以使用预编译的自定义代码来处理,而不是必须JIT编译你的排序函数。标准库排序应该(通常?)为JS解释器/ JIT进行良好的调整,以有效地处理,并使用高效算法的高效实现。
这个答案的其余部分是假设一个用例,比如在一个预先编译的语言中对一个整数数组进行排序,比如C编译成原生asm。如果你对一个以一个成员为键的结构数组进行排序,没有太大的变化,尽管比较和交换的代价可能会有所不同,如果你是对char*字符串和包含int的大型结构进行排序的话。(冒泡排序对所有这些交换的情况都不好。

请参阅Bubble Sort: An Archaeological Algorithmic Analysis,了解为什么它是最糟糕的O(N^2)排序之一,但却“流行”(或被广泛教授/讨论)的更多信息,包括历史/教学法的一些意外。还包括一个有趣的定量分析,即它是否 * 实际上 *(有时声称)是最容易编写或理解的代码之一。

对于简单的O(N^2)排序是一个合理的选择的小问题(例如快速排序或合并排序的N <= 32个元素的基本情况),插入排序经常被使用,因为它具有良好的最佳情况性能(在已经排序的情况下快速通过,在几乎排序的情况下有效)。
冒泡排序(对于没有进行任何交换的遍历,有一个提前出来)在某些几乎排序的情况下也不是很糟糕,但比插入排序更糟糕。但是一个元素每遍只能向列表的前面移动一步,所以如果最小的元素接近末尾但完全排序,它仍然需要冒泡排序的O(N^2)工作。维基百科解释了兔子和乌龟。
插入排序没有这个问题:靠近末尾的小元素将被插入(通过复制早期的元素来打开间隙)。(到达它只需要比较已经排序的元素来确定这一点,然后继续前进,实际插入工作为零)。一个靠近开始的大元素最终会快速向上移动,只需要稍微多一点的工作:每一个新的元素都必须被插入到那个大元素之前,然后再插入到其他元素之后。所以这是两次比较,实际上是一次交换,不像冒泡排序在它的“好”方向上每一步交换一次。尽管如此,插入排序的“坏”方向还是比冒泡排序的“坏”方向好得多。
有趣的事实:用于在真实的CPU上进行小阵列排序的现有技术可以包括使用打包的最小/最大指令的SIMD网络排序,以及并行地进行多个“比较器”的向量混洗。

为什么冒泡排序在真实的CPU上不好:

交换的模式可能比插入排序更随机,并且对于CPU分支预测器来说更不可预测。因此导致比插入排序更多的分支错误预测。
我自己还没有测试过这个,但是想想插入排序是如何移动数据的:每次完整的内部循环都将一组元素向右移动,为一个新元素打开一个间隙。在外部循环迭代中,该组的大小可能保持相当恒定,因此有合理的机会预测内部循环中循环分支的模式。
但是冒泡排序并没有创建太多的部分排序的组;交换的模式不太可能重复1。
我搜索了对这个猜测的支持,并找到了一些:插入排序比冒泡排序更好?引用维基百科:
冒泡排序与现代CPU硬件的交互也很差,它产生的写入至少是插入排序的两倍,缓存未命中的两倍,以及渐近更多的分支误预测。
(IDK如果“写入次数”是基于源代码简单分析,或者查看适当优化的asm):
这就引出了另一点:冒泡排序可以很容易地编译成低效的代码。交换的名义实现实际上是存储到内存中,然后重新读取它刚刚写入的元素。根据编译器的智能程度,这可能实际上发生在asm中,而不是在下一次循环迭代中重用寄存器中的值。在这种情况下,你会在内部循环中遇到存储转发延迟,并且还在高速缓存读取端口/加载指令吞吐量上产生潜在的瓶颈。

**Footnote 1:**除非你重复地对同一个小数组进行排序;我曾经在我的Skylake CPU上尝试过一次,使用了我为这个代码高尔夫问题编写的简化的x86 asm实现Bubble Sort(代码高尔夫版本故意对性能进行了可怕的优化,只针对机器码大小进行了优化;我测试的IIRC版本避免了存储转发 stallslock ed指令,如xchg mem,reg)。

我发现每次输入相同的数据(在重复循环中复制了一些SIMD指令),Skylake中的IT-TAGE分支预测器“学习”了特定的~13元素冒泡排序的整个分支模式,导致perf stat报告低于1%的分支错误预测,IIRC。所以它并没有展示我所期望的冒泡排序的大量错误预测,直到我增加了数组的大小。:P

mdfafbf1

mdfafbf12#

时间复杂度:O(n)时间复杂度:O(nlog(n))时间复杂度:O(nlog(n))
请参阅:complexity of bubble sort

相关问题