5

此问题与“比较方法违反其总合同！”有关。- TimSort 和 GridLayout 以及其他几个类似的“一般合同违规”问题。我的问题与页面底部关于“如何测试 TimSort 实现”的 Ceekay 的回答特别相关。在我的情况下，我已经修复了由于对称违反而导致我出现在这里的应用程序错误，但是我无法创建一个单元测试来公开该违反（如果修复被注释掉或将来未修复）。

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]（即使表示为字符串）。所有有效的 Tick 数字都是有效的 Gis Tick 数字，但有效的 Gis Ticks 也可能看起来像A912, R123, 0123G, A346*。

我的对称违规是在 GisTick 中compareTo，我考虑了可能的后缀，但在普通的 Tick 中compareTo我没有考虑它。因此，如果 'this' 是0000Tick 并且 'that' 是0000*Gis Tick，0000.compareTo(0000*)将返回 0。而如果 'this' 是0000*Gis Tick 而 'that' 是0000Tick，0000*.compareTo(0000)将返回 1。 明显的对称性违反（一旦护罩被拉回）

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

  1. 创建一个包含 32 个或更多对象的列表。
  2. 在该列表中，需要 [be] 两次或多次运行。
  3. 每次运行必须包含 3 个或更多对象。

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

我相信我已经为我的单元测试设置了这样一个 TickNumber（和 GisTickNumber）对象列表，但我似乎无法让测试失败。即使该列表有超过 100 个对象，也有两次以上的运行，并且每次运行包含大约 10 个对象。所以，我的问题是，被测对象列表需要满足哪些其他特征才能使调用Collections.sort(testList)因“一般（对称）违反合同”而失败？

  • 是的，我在运行我预计会失败的单元测试之前注释掉了修复。
4

1 回答 1

-1

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

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

  • 列表必须包含 64 个元素 (49 + 1 + 12 + 1 + 1)
  • 该列表必须包含 50 个运行，其中 50 个元素中有 49 个的比较结果为 0（即比较匹配）
    • 在该“匹配运行”的前半部分中，必须有 1 个元素在运行中的所有其他元素之前排序（运行中的所有其他元素在比较时都匹配），并且该单个奇数元素也必须“对称不匹配”元素其他运行结束。
  • 该列表必须包含至少 2 个其他三个或更多元素的运行（我的测试列表有 8 个运行，然后是 4 个运行）
    • “对称不匹配”的另一半必须是 4 运行中的最后一项（第二次其他运行）。
  • 列表必须在 (end - 1) 位置包含一个元素，该元素排序到排序列表的开头
  • 列表必须在（结束）位置包含一个元素，该元素在排序列表的中间某处进行排序

我很确定上面的项目符号不是一个列表必须满足的一般要求的详尽列表，以在列表排序时暴露对称性违规，但它们在一个特定情况下对我有用。

具体来说，我制作的测试列表从 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”TickNumber 对象结束，该对象将引导排序列表，以及一个“9978*”GisTickNumber 对象，该对象在中间某处进行排序。我尝试删除和/或重新排列测试列表中的对象，但无济于事。例如，如果从测试列表中删除“9901”元素，则单元测试将开始发出假阳性（成功）结果。（如果将“9901”移到未排序列表的前面，也会出现误报）例如，如果从测试列表中删除“9901”元素，则单元测试将开始发出假阳性（成功）结果。（如果将“9901”移到未排序列表的前面，也会出现误报）例如，如果从测试列表中删除“9901”元素，则单元测试将开始发出假阳性（成功）结果。（如果将“9901”移到未排序列表的前面，也会出现误报）

注意：我怀疑“9910”对称不匹配的普通 TickNumber 部分可能出现在第 MIN_RUN'th 元素之前的开场运行中的任何位置。换句话说，如果 MIN_RUN 是 32 并且我的测试列表中的前导运行有 50 个元素与 49 比较“相同”，那么“9910”对称不匹配元素可以出现在运行中小于位置 32 的任何位置。这个假设没有被证明；但我凭经验确定对称失配元素不能出现在前导运行结束附近，并且它可以出现在前运行开始附近的多个位置。（每次测试运行一个不同的位置）

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

在我的例子中，在我的测试列表中匹配的唯一 TickNumber 对象是 49 个“9999”刻度和 2 个（“9910”和“9910*”）在比较时违反对称性的刻度。

于 2015-12-28T22:59:19.063 回答