for*_*all 17 javascript sorting computer-science computability
在JavaScript(有些适用于其他地方),你不知道你的代码在哪个目标实现上运行,是否有一种方法可以检测基础排序算法(of Array.sort)是否稳定,只知道它遵循规范？
我可以在webkit (1) (2)中找到2个测试,但这些测试有多可靠？(这可以通过PCP进行检查吗？)我正在寻找一种在数学上合理的解决方案.
这是一个棘手的问题,因为更高级的排序算法可以根据源数组的长度(如Timsort)更改子算法.我一直很困惑,因为我所运行的每一项测试都表明Google Chrome的稳定性,但我见过的所有文档都说它不稳定(来源会告诉你原因).
(通常情况下,我使用此策略使我的排序稳定;它有一个小但有时显着的性能影响)
各种实现中的排序源代码:小智 5
除非您可以测试与该标准相关的所有可能输入,否则黑盒测试不能用于确定程序是否满足任何标准.一个黑盒子可以自由地只有一个查找表,将输入映射到输出(请参阅Pentium FDIV bug以获取真实的查找表错误),因此您无法确定您的测试是否排除了其他输入触发违规的可能性.
运行一个小的内部测试来检查？您可以使用维基百科中的“按等级打牌，然后按花色打牌”示例来检查稳定性。
请参阅： https: //en.wikipedia.org/wiki/Sorting_algorithm#Stability
我不知道你需要多少张卡来检查稳定性——也许5张左右？
| 归档时间： |
|
| 查看次数： |
1369 次 |
| 最近记录： |