java - 为什么快速排序的 JDK 实现存在堆栈溢出的风险?

标签 java arrays sorting stack-overflow quicksort

前几天我看到一个演讲,演讲者使用了 McIlroy 的论文 A Killer Adversary for Quicksort 中概述的技巧。生成对 Arrays.sort 的输入对于会触发 O(n2) 行为的原始类型。该序列导致枢轴选择始终仅将数组大小减少一个常量,从而导致 Java Arrays.sort函数导致堆栈溢出。

根据 the source files from the JDK , Arrays.sort1快速排序实现函数没有防止堆栈溢出的保护。通过让排序例程不触发两次递归调用,而是使用 while 循环为较大的子数组重用当前堆栈帧并且只递归一次(在较小的子数组上),总是可以使快速排序永远不会堆栈溢出。这会导致最小的性能下降,并且不可能导致任何大小合理的输入的堆栈溢出,因为堆栈深度永远不会超过大小为 n 的输入的 O(log n) 堆栈帧。作者也可以使用 introsort算法,当快速排序递归深度超过某个限制时,它修改快速排序以切换到最坏情况 O(n log n) 排序算法,以防止这种情况。
Arrays.sort的作者有什么原因吗?没有选择这样做?内置排序算法会导致堆栈溢出似乎是一个严重的问题,因为它可以通过触发重复的堆栈溢出来对这样的系统发起 DoS 攻击。

最佳答案

为什么?因为解决这个问题会矫枉过正。

所使用的算法在除异常情况外的所有情况下都是稳定的,如果这些情况比通常更可能发生,则外部情况将受到保护。这就是为什么他们有 API 文档来定义幕后使用的算法。所以可以防御它。

破坏所呈现算法的特定顺序的可能性微乎其微。

我希望如果您仔细观察,就会发现几乎所有标准 JVM 结构都被破坏的数据集。防范它们的成本是多少,该成本是否值得付出努力以及由于防御措施而不可避免地导致算法降级。

关于java - 为什么快速排序的 JDK 实现存在堆栈溢出的风险?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/16492105/

相关文章:

java - 从 cucumber 4.2.3 升级到 5.1.3 后 Cucumber runner 类初始化错误

java - 简单的 GWT RequestFactory 崩溃

java - 在 JButton 单击时打印特定值

c# - 如何在Cudafy GPU内核中声明固定大小的数组

c# - 合并多个列表,每个列表具有可变长度 "popping"个元素

java - 更新android studio 3.0.1时安装区发现一些冲突

c# - List<double> 到 double[,] 用于 ALGLIB

c - 如何解决“参数类型不完整”错误?

algorithm - 快速选择算法适用于只读输入以在CUDA上运行

python - 如何使用 Python 按排序顺序在字典中显示字典?