两种插入排序的实现方式有性能的差异吗?
来源:2-6 换个角度实现插入排序法,作业分析
阿阳2017
2023-02-04 21:10:17
老师你好,本章讲的两种插入排序实现方式,从前往后,从后往前,它们之间有什么性能上的差异吗?如果有,和JVM实现有关系吗?
1回答
liuyubobobo
2023-02-05
没有差异。即使你在某一组数据中可以看到差异,这种差异也不是算法研究的重点,甚至是和算法一点关系都没有。
一个不管实现的有多好的插入排序算法,面对大规模的随机数据,都无法和一个尽管实现地很“烂”的快速排序或者归并排序抗衡,为什么,这就是复杂度的力量。算法领域首要关注的是“复杂度的变化”。
==========
如果你一定要关注这种“细微的实现差别”带来的性能变化:
首先,你应该学习的是各个语言相关的细节。如果一个实现比另一个实现更优,很有可能是语言背后的执行机制带来的,比如你说的 JVM 的优化的不同(JVM 的不同版本处理方式还会有区别);比如脚本语言对于某些调用会转入执行更快的被 C 优化的底层库,而对于另外一些调用这不会;比如编译器对一些 pattern 的识别(如 Java 或者 C++ 等语言都有对尾递归的优化,而 go 没有,但不排除更后续的版本就会添加这一特性,等等。)
其次,你应该学习的是和 CPU 乃至和 微指令相关的内容。因为即便是同样的代码,在不同的硬件环境下,性能也会不同。受影响的因素可能包含是否是多核环境,当前环境是否允许并发。(即便允许,你所使用的语言环境是否会自动做并发优化,也受影响。)包括 CPU 是 RISC 还是 CISC,还是某类特制芯片 ASIC(比如专门针对神经网络优化的 FPGA),全都在影响一个具体实现实际运行的性能。
所有的这些,都不是“算法”探讨的范围。
继续加油!:)
相似问题