9

ArrayLists 似乎使用 TimSort 排序，其中底层列表在排序期间并不总是一致的。在调用比较器时，列表条目可能会消失或出现两次。

在我们的比较器中，我们正在比较键，我们正在使用一个函数来获取一个值来比较这个键。由于此函数在其他上下文中使用，我们测试了键是否实际存在于列表中（排序中不需要的东西）：

        if (keys.contains(itemId)) {
          ...

由于键是我们正在排序的列表，因此由于 TimSort 的内部机制，比较器可能会在列表中找不到键。

问题：这是否在 Javadoc 中的某处（找不到）提到您不应该访问 Comparator 中的底层列表？这是应该对副本进行排序的 TimSort 的糟糕实现吗？还是首先访问比较器中的基础列表是一个愚蠢的想法？

下面的程序由TJ Crowder提供，演示了底层列表的内容在调用 Comparator 期间可能不一致。（这个程序演示了有问题的现象，但它并不代表受问题影响的实际应用程序。）

import java.util.*;

public class Example {
    private static String[] chars = {
        "a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", "n", "o", "p", "q", "r", "s", "t", "u", "v", "w", "x", "y", "z"
    };

    private List<String> list;
    private String[] entries;

    private Example() {
        this.entries = new String[1000];
        for (int n = 0; n < 1000; ++n) {
            this.entries[n] = chars[n % chars.length] + n;
        }
        // Ensure it's an ArrayList, specifically
        this.list = new ArrayList<String>(Arrays.asList(this.entries));
    }

    public static void main(String[] args) {
        (new Example()).run();
    }

    class ListComparator implements Comparator<String> {
        public int compare(String a, String b) {
            for (String s : entries) {
                int i1 = Example.this.list.indexOf(s);
                if (i1 == -1) {
                    System.out.println(s + ": Missing");
                } else {
                    int i2 = Example.this.list.lastIndexOf(s);
                    if (i2 != i1) {
                        System.out.println(s + ": Duplicated, at " + i1 + " and " + i2);
                    }
                }
            }
            return a.compareTo(b);
        }
    }

    private void run() {
        this.list.sort(new ListComparator());
    }
}

以下是运行的前几行输出：

b1：缺失
a52：重复，在 2 和 32
b27：失踪
a52：重复，在 2 和 32
c2：失踪
a52：重复，在 2 和 32
c2：失踪
c28：失踪
a52：重复，在 2 和 32
b53：重复，在 5 和 33
c28：失踪
d29：缺失
a52：重复，在 2 和 32
b53：重复，在 5 和 33
d3：缺失
d29：缺失
a52：重复，在 2 和 32
b53：重复，在 5 和 33
d3：缺失
d29：缺失
e30：失踪
4

1 回答 1

3

这里有一点历史：在 JDK 7 中，TimSort 算法取代了之前的“遗留合并排序”算法。在 JDK 8 中，Collections.sort()委托给新的默认方法List.sort()。此默认方法被 覆盖ArrayList，它进行就地排序。之前的Collections.sort()实现会将列表复制到一个临时数组，对该临时数组执行排序，然后将临时数组中的元素复制回原始列表。

如果排序比较器在被排序的列表中查找，那么它的行为肯定会受到 JDK 8 中引入的 ArrayList 新的就地排序行为的影响。JDK 7 中从“遗留合并排序”到 TimSort 的变化可能没有在这种情况下会产生影响，因为 JDK 7 仍然对临时副本进行排序。

的 copy-sort-copyback 行为List.sort()在“实现要求”部分中进行了描述，该部分指定了默认方法实现的行为，但它不是强加于所有实现的接口合同的一部分。因此，ArrayList（和其他子类）可以自由地改变这种行为。我注意到没有覆盖实现的文档ArrayList.sort()。我想如果添加一些指定就地排序行为的文档，那将是一个小的改进。

如果就地排序ArrayList有问题，您可以在排序之前复制列表：

List<Key> list = ... ;
List<Key> newList = new ArrayList<>(list);
newList.sort(keyComparator); // uses the old list
list = newList;

或者，也许您可​​以提供有关比较器工作方式的更多详细信息，我们也许能够找到一种重写它的方法，这样它就不需要查看正在排序的列表。（我建议为此提出另一个问题。）

于 2019-01-08T01:44:19.133 回答