Java——如何单元测试TimSort和“一般契约违反”问题

Question

这个问题与“比较方法违反了它的一般契约！”——TimSort和GdriLayout以及其他几个类似的“违反一般契约”问题有关。我的问题特别与Ceekay在页面底部关于“如何测试TimSort实现”的回答有关。在我的例子中，我已经修复了由于对称性违反而将我带到这里的应用程序错误，但是我在创建一个单元来暴露该违规（如果修复被注释掉或将来未修复）时遇到了问题。

public class TickNumber implements Comparable<TickNumber> {
    protected String zone;
    protected String track;
}
public class GisTickNumber extends TickNumber implements Comparable<TickNumber> {
    private String suffix;
}

我省略了所有实现细节，但基本上 Tick 数字是一个 4 位数字，其中前两位数字是区域，后两位数字是轨道。GisTickNumbers 可以在区域和/或轨道字段中包含字母字符，并且可以选择具有一个或两个字符的字母后缀。有效刻度是 [0000， 9999] 范围内的所有整数（即使表示为 String）。所有有效的 Tick 编号都是有效的 GIS 刻度编号，但有效的 GIS 刻度也可能看起来像 A912、R123、0123G、A346*。

我的对称性违规是，在GisTick＜code＞compareTo＜/code＞中，我考虑了可能的后缀，但在纯Tick＜code＞compareTo＜/code>中，我没有考虑它。因此，如果“this”是0000Gis Tick，而“that”是0000*Gis Ticket，则0000.compareTo（0000*）将返回0。而如果“thise”是0000*0000Tick，则0000*。compareTo（0000）将返回1。明显的对称违规（一旦护罩拉回）

根据Ceekay在对链接问题的回答中的说法，

< li >创建包含32个或更多对象的列表。 < li >在该列表中，需要运行两次或更多次。 < li >每次运行必须包含3个或更多对象。

一旦您满足这三个标准，您就可以开始测试此故障。

我相信我已经为我的单元测试设置了这样一个TickNumber（和GisTickNumber）对象列表，但我似乎不会让测试失败。尽管列表中有100多个对象，但有两个以上的运行，每个运行包含大约10个对象。因此，我的问题是，为了调用＜code＞Collections，测试对象列表还需要满足哪些特性。排序（testList）是否因“常规（对称）合同违反”而失败？

• 是的，在运行预期失败的单元测试之前，我注释了修复程序。

Answer 1

已解决：
我最终调试到一个断点，在该断点中我可以查看正在排序的列表中对象的 toString（） 表示形式，然后能够从该数据的其余部分中提取 TickNumber 信息，并最终在我的单元测试中使用该提取的数据。最后，我返回并删除了列表项，直到我制作了一个似乎满足触发对称相关“一般合同违规”的“最低要求”的列表。

我不确定如何将我的特定解决方案概括为列表必须满足的通用特征，以触发 TimsSort 和这种“一般合同违规”。但是在这里...

• 列表必须包含64个元素（49 1 12 1 1）
• 列表必须包含50的运行，其中50个元素中的49个比较结果为0（即比较匹配）
  • 在匹配运行的前半部分，必须有一个元素在运行中的所有其他元素之前排序（运行中的所有其他元素在比较时匹配），并且该单个奇数元素也必须在其他运行结束时“对称不匹配”该元素。
  • “对称性不匹配”的另一半必须是4次运行（另一次运行）中的最后一项

  我很确定上面的要点并不是列表在排序时暴露对称破坏所必须满足的全部要求，但是它们在一个特定的情况下对我有效。

  具体来说，我精心制作的测试列表从49个TickNumber对象开始，其中Tick = "9999 "，在49个Tick的前半部分有一个" 9910" Tick，在这个开放的伪运行中总共有50个Tick数字。(伪，因为“9910”打破了49个匹配“9999”记号的未排序运行。)开始运行中的“9910”记号是我测试的对称不匹配的一半。那么测试列表包含12个GisTickNumber对象，作为8的运行(“9915*”、“9920*”、“9922*”、“9931*”、“9933*”、“9934*”、“9936*”、“9939*”)，接着是4的运行(“9907*”、“9908*”、“9909*”、“9910*”)。请注意，4的最后一项是我正在测试的“对称不匹配”的另一半。最后，列表以一个“9901”tick number对象结束，该对象将开始排序列表，还有一个“9978 *”gistick number对象，该对象在中间某处排序。我已经尝试删除和/或重新排列测试列表中的对象，但没有效果。例如，如果从测试列表中删除了“9901”元素，单元测试将开始发布假阳性(成功)结果。(如果将“9901”移动到未排序列表的前面，也会出现误报)

  注意：我怀疑“9910”对称失配的纯TickNumber部分可能出现在MIN_run元素之前的开场运行中的任何位置。换句话说，如果MIN_RUN是32，并且我的测试列表中的前一个运行有50个元素，其中49个元素比较“相同”，那么“9910”对称失配元素可以出现在运行中小于位置32的任何位置。这个假设尚未被证明；但我根据经验确定，对称失配元素不可能出现在领先运行的末尾附近，并且它可能出现在接近领先运行开始的多个位置。（每次测试运行一个不同的点）

  一般来说，如果这些条件中的任何一个不是“完全正确的”，那么即使您正在测试列表数据，比较应该违反合同，您也不会触发“一般合同违反”。

  就我而言，在我的测试列表中匹配的唯一 TickNumber 对象是 49 个“9999”时钟周期和 2 个（“9910”和“9910*”）时钟周期，它们在比较时违反了对称性。