java使用日期强制TimSort IllegalArgumentException

Question

使用Java8U151

我们正在进行以下工作：

Collections.sort(srs, (sr1, sr2) -> sr1.getValidStartTime().compareTo(sr2.getValidEndTime()));

其中getValidStartTime和getValidEndTime是日期对象

显然，这段代码是错误的，因为我们的目标实际上只是根据开始时间进行排序

然而，不幸的是，导致问题的数据被从数据库中删除，我们得到了臭名昭著的IllegalArgumentException。这似乎合乎逻辑，因为在元素之间，我们没有使用相同的值进行比较（A.start与B.end进行比较，但B.start与C.end进行比较）

我不能做的是找出导致再次抛出此异常的数据集。修正代码以总是比较开始时间是正确的方法，但是关于数据集前后的测试，我还不能证明修正的正确性（即使每个人都同意我们正在进行更改）

我试着研究TimSort的mergeHi方法，它抛出了这个，但是我不能完全理解正在进行的所有gallop和数组复制。因此，虽然我可以知道异常抛出的位置，但要使其可复制却遇到了失败

日期对象在排序之间是静态的。一旦在数据库中设置，它们是不可变的。在排序期间，列表本身也没有改变。所以对我来说，我可能是错的，这指向数据，我们有一些奇怪的开始和结束日期组合，违反了传递子句，但我尝试过的每个组合都会得到一个有效的排序（如果不是有点奇怪的话）

谢谢

Answer 1

最简单的方法就是不断生成随机列表，并尝试排序，直到检查失败。在jdk 1.8.0_111上，导致异常的最短列表是32个元素。以下是可用于初始化Date值并将导致异常的开始/结束时间戳列表：

{start=68208554877356084, end=3791095193142800835}
{start=248264922016936970, end=5326356389367348592}
{start=70847878331153962, end=1329864610265504554}
{start=299053597297857298, end=4543460986676142955}
{start=2075045414748723202, end=1193808915252175698}
{start=1888180037471781608, end=2492314749794483810}
{start=506596727265987351, end=2390472400080050280}
{start=4533260585328085001, end=2273691205607504663}
{start=5678209310012100575, end=959412777775545678}
{start=2732174389724934002, end=1780458709387750881}
{start=3098641550091084357, end=7078749384785410602}
{start=556524021068368297, end=8482788837298542192}
{start=98318333071465581, end=4156661237757928788}
{start=2084735587245502205, end=4379712643293008540}
{start=3165092267008534695, end=3427927233210778860}
{start=3109680552226050258, end=7303065366486904947}
{start=4928610946211198422, end=6426677832945805822}
{start=965369716172656147, end=6219167484686793206}
{start=805041445200191777, end=2942634988195806902}
{start=8045405997433808237, end=6001857015663585724}
{start=6633159983148701791, end=1448351075620872268}
{start=4539362557763873114, end=8432020244491782408}
{start=7435017849572867526, end=5951614001812150640}
{start=9205367993832979048, end=1341233048581746570}
{start=8478026453445310753, end=530855741009189818}
{start=4638397659065784972, end=2597599860193612976}
{start=3683809635722753669, end=8506390941316155399}
{start=5946468237919207244, end=3711093891423756040}
{start=6965128507257577261, end=8627460098134987362}
{start=7493578845247407113, end=8568660839840900159}
{start=7097494652946649557, end=8999069292652823540}
{start=9190087421488513073, end=20737341215892578}

Answer 2

很难拿出数据，导致TimSort抛出“比较法违反了它的总合同！”例外，当给出一个有缺陷的比较器时。作为Misha pointed out（+1），输入必须至少有32个元素长，并且生成随机数据直到得到一个导致异常的数据似乎是一种合理的方法

拥有这样的输入数据似乎有助于显示bug实际上已经修复。毕竟，它与旧的比较器崩溃了，而且它可能不会与固定的比较器崩溃。这是一个证据，但它实际上并没有表明固定的比较器实际上是固定的；它可能不会导致该输入数据出现问题，但也可能会导致其他输入数据崩溃

问题是，你想走多远

依靠图书馆

一种方法是简单地使用Java8构造来创建一个比较器。你可以将声明改写如下：

Collections.sort(srs, Comparator.comparing(SR::getValidStartTime));

如果您相信库的排序例程工作，并且Comparator.comparing例程工作，那么您可能不需要测试这个

测试比较仪合同要求

如果你真的想测试这个比较器（或者你想测试一个更复杂的比较器），另一种方法是根据^{}方法规范中列出的要求为它编写一些单元测试：

• 反对称：对于所有x和y，sgn(compare(x, y)) == -sgn(compare(y, x))

• 及物性：((compare(x, y)>0) && (compare(y, z)>0))意味着compare(x, z)>0

• 可替代性：compare(x, y)==0意味着sgn(compare(x, z))==sgn(compare(y, z))对于所有z

您可以编写一些单元测试，获取一组固定的值，并验证给定比较器对于从值集中获取的所有输入组合是否具有这些属性

验证排序结果的顺序

还有一种方法是获取一些输入数据（真实的或随机生成的），并使用比较器对其进行排序。如果没有崩溃，请验证生成的列表是该比较器施加的顺序。如果比较器的行为不一致，则对项目进行排序的结果可能甚至可能不会产生一个根据比较器进行实际排序的列表。这是因为在排序过程中应用比较器的项目与比较相邻项目时应用比较器的项目不同。当然，这并不能保证找到错误，但它是一种潜在的有用的交叉检查。注意，这并不能测试比较器在语义上是否正确。它只是测试比较器的行为是否一致