有没有黑盒方法来检测排序算法是否稳定?

问题描述 投票:0回答:5

在 JavaScript(在其他地方也适用)中,您不知道代码运行在哪个目标实现上,有没有一种方法可以检测底层排序算法(

Array.sort
)是否稳定,仅知道这一点它遵循规范

我可以在 webkit 中找到 2 个测试 (1) (2),但是这些测试的可靠性如何? (这个检查可以用PCP来完成吗?)我正在寻找一个在数学上合理的解决方案。

这是一个棘手的问题,因为更高级的排序算法可以根据源数组的长度更改子算法(如 Timsort)。我一直很困惑,因为我运行的每个测试都显示 Google Chrome 的类型是稳定的,但我看到的所有文档都说它不稳定(来源会告诉你原因)。

(通常,我使用这个策略来使我的排序稳定;它对性能的影响很小,但有时很明显)

各种实现中排序的源代码:
javascript sorting computer-science computability
5个回答
5
投票

黑盒测试不能用于确定程序满足任何标准,除非您可以测试与该标准相关的所有可能的输入。 黑盒可以自由地简单地拥有一个将输入映射到输出的查找表(有关现实世界的查找表错误,请参阅Pentium FDIV bug),因此您无法确定您的测试排除了某些其他输入触发违规的可能性.


1
投票

数学上合理,是吗?这需要证明算法中的每一条路径以及它们的每一个组合都是稳定的。对于任何可能的数据。

确实存在这样的算法 - 但它们很可能是为了满足该要求而设计的。所以如果是的话,它可能说它在某个地方。

至于证明类似问题的测试,可能属于与停止问题类似的问题。

http://en.wikipedia.org/wiki/Halting_problem


1
投票

为什么要冒险? 对于大多数合理的数据集,合并排序的 JavaScript 实现应该足够快。 挑选几个并对它们进行基准测试并使用最好的一个。


0
投票

运行一个小型内部测试来检查?您可以使用维基百科中的“按等级打牌,然后按花色打牌”示例来检查稳定性。

参见:https://en.wikipedia.org/wiki/Sorting_algorithm#Stability

我不知道你需要多少张卡来检查稳定性——也许5张左右?


0
投票

截至 ES 2019,

sort
方法 根据规范是稳定的。然而,规范中似乎存在疏忽,因为没有考虑检查
sort
在运行时是否稳定,这意味着你必须假设它不是稳定的,缺少 UA 嗅探。这违背了提供稳定排序的目的。

如果您同意 UA 嗅探,则只需检查 Chrome、Firefox 和 Edge 版本 100 或更高版本,或者 Safari 版本 10 或更高版本即可简化操作。这并不包括所有包含稳定排序的浏览器版本,但将覆盖绝大多数用户。

/Chrome\/(1\d{2,})|Firefox\/(1\d{2,})|Edg\/(1\d{2,})|Version\/(1[0-9]|[2-9]\d+)\.\d+ Safari\//.test(navigator.userAgent)
© www.soinside.com 2019 - 2024. All rights reserved.