tem*_*def 5 java stack-overflow arrays sorting quicksort
前几天,我看到演讲者使用了McIlroy的文章"Quickort的杀手对手"中概述的技术,Arrays.sort为原始类型生成了一个触发O(n 2)行为的输入.该序列导致pivot选择总是只减少一个常量的数组大小,这导致Java Arrays.sort函数导致堆栈溢出.
根据JDK的源文件,Arrays.sort1quicksort实现函数无法防止堆栈溢出.通过使排序例程不会触发两个递归调用,总是可以使快速排序永远不会堆栈溢出,而是使用while循环来重用当前堆栈帧以用于更大的子数组并且仅递归一次(在较小的子数组上).这导致最小的性能下降,并且使得不可能导致任何合理大小的输入的堆栈溢出,因为堆栈深度从不超过大小为n的输入上的O(log n)堆栈帧.作者还可以使用introsort算法,当快速排序递归深度超过某个限制时,它会修改快速排序以切换到最坏情况的O(n log n)排序算法,以防止这种情况发生.
有没有理由为什么作者Arrays.sort没有选择这样做呢？内置排序算法可能会导致堆栈溢出,这似乎是一个严重的问题,因为它可以通过触发重复的堆栈溢出来启动针对此类系统的DoS攻击.
为什么？因为解决这个问题会有点矫枉过正.
所使用的算法在所有但非常特殊的情况下都是稳定的,并且如果这些情况通常可能发生,那么情况将在外部得到防范.这就是为什么他们有API文档来定义幕后使用的算法.所以你可以防御它.
打破所呈现算法的特定顺序的可能性非常小.
我希望如果你仔细观察会有数据集导致几乎所有的标准JVM结构中断.保护他们的成本是多少,并且由于防御措施,成本值得努力并且算法不可避免地退化.