问题标签 [timsort]

Java 7更改了排序算法，使其抛出

java.lang.IllegalArgumentException：“比较方法违反了它的一般约定！”

在某些情况下，当使用的比较器有问题时。是否可以判断比较器中的哪种错误导致了这种情况？在我的实验中，如果 x != x 无关紧要，如果 x < y 和 y < z 但 z < x 也无关紧要，但对于某些值，如果 x = y 和 y = z 但 x < z x，y，z。一般是这样吗？

（如果有一个通用规则，在比较器中查找错误可能会更容易。但当然最好修复所有错误。:-)）

特别是，以下两个比较器并没有让 TimSort 抱怨：

但是下面的比较器确实让它抛出了：

更新：在一些现实生活中的数据中，我们遇到了一个失败，其中没有 x,y,z 且 x = y 和 y = z 但 x < z 。所以看来我的猜测是错误的，而且似乎不仅仅是这种特定的失败。有更好的想法吗？

看看这段代码

ba.compareTo(ab) 有效，但 ab.compareTo(ba) 失败。它抛出一个 IllegalArgumentException 引用违反比较器合同。我相信这是因为传递性属性不满足。有人可以解释一下 Java 在 Strings 的情况下如何使用传递性属性吗？这与 Timsort 的工作方式有什么关系吗？

编辑：这是我在 Leetcode 在线法官上遇到的错误

同样，当我使用 ba.compareTo(ab) 时，我没有收到此错误。一世

编辑：为什么我认为这不是重复的：正如biziclop(a>b & b>c => a>c)所写，这里的问题不像这里提到的其他问题那样不及物，而是a>b => -(b>a)违反了该条款，所以这是一个不同的问题。

我收到以下错误消息：

这就是它发生的地方：

这是定义对象 RegretProfit 的类：

该错误仅每几千次迭代发生一次。如果有人知道问题可能是什么，我将非常感激。我已经读过不传递性会导致此异常，但我真的无法弄清楚我可能出错的地方。

解决了，感谢biziclop！

我正在根据以下比较器对集合进行排序。

这些值始终为非空值。getOrderSendTime() 对象属于 java.util.Date 类。

我知道这是传递性不一致，我会假设这样的课程不会有这样的问题。我搜索了未解决的问题，但没有找到任何关于该主题的问题。

有任何想法吗？

我一直在寻找一种使用多线程实现 Timsort for C++ （在 Github 上找到的实现）的方法，并且我已经尝试在这个过程中使用。我确定我使用了正确的编译器标志，但是每当我尝试使用 Timsort 时，如下所示：

注意：被排序的数据是一个包含单个单词字符串的向量，我正在使用我自己的比较器。

它似乎在不使用 OpenMP 的情况下运行所需的时间相同。使用 chrono 等的适当包含，我对彼此平均在 0.01 秒内的值进行计时，在我的排序中徘徊在 1.24 秒左右。

线程似乎不适用于我的排序方法是否有原因，还是我实现 OpenMP 的方式有问题？

特意注意：我一直在使用 __gnu_parallel::sort 并获得更好的结果，但我希望自己在实践中比较这些方法。

我目前正在尝试为 100 个项目的 Arraylist 优化排序算法。问题是我的列表具有不变性，即其前半部分项目始终与它们自身相对顺序......

（即{1,1,4,5,6,2,1,11,4,3}，因为前5项是相对有序的）。

为了利用此功能，我正在考虑仅对列表的右半部分进行排序，然后按顺序合并两半。我的理由是，通过仅对列表的一半进行排序然后合并，我可以实现 (m lg(m) + n) 的时间复杂度，其中 m = n / 2。这是否使得 big-Oh 复杂度比 O(nlg (n)) 还是 (m lg(m) + n) 最终会减少到 O(nlg(n)) 反正？

任何有关此问题的大问题或解决此问题的最有效方法的任何见解都将不胜感激。

我读过 Timsort 在最好和最坏的情况下都比 Quicksort 好，尽管它使用了更多的内存。内置 .Sort() 方法使用 Quicksort 是否有特定原因，或者只是它尚未实现？

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

我省略了所有的实现细节，但基本上一个 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)因“一般（对称）违反合同”而失败？

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

摘自 Joshua Bloch 和 Neal Gafter 的 Java Puzzlers

预期的行为是未定义的，文本说它返回 [3, 1, 4, 1, 5, 9]。直到 Java 版本 1.7 都是如此。但是，在 Java v. 1.8 中，输出是排序列表。

我可以看到 Timsort 是 Java 1.8 中的新功能，但我不确定该算法如何与上面给出的不一致比较器一起工作。任何有关如何实现的帮助或见解将不胜感激。

假设我有以下 compareTo：

我想知道我打电话时的确切比较次数Arrays.sort(randomClassArray)，哪里randomClassArray有 100 个对象？