在标准Java库中,找出两个list是否包含完全相同的元素的最简单方法是什么?

这两个list是否为相同实例并不重要,这两个list的类型参数是否不同也不重要。

e.g.

List list1
List<String> list2; 
// ... construct etc

list1.add("A");
list2.add("A"); 
// the function, given these two lists, should return true

我知道可能有什么东西在盯着我的脸:-)


编辑:为了澄清,我正在寻找完全相同的元素和元素的数量,按顺序。


当前回答

我在评论里发了一堆东西,我认为它有自己的答案。

正如这里所有人所说,使用equals()取决于顺序。如果你不关心顺序,你有三种选择。

选项1

使用containsAll()。在我看来,这个选项并不理想,因为它提供了最坏情况下的性能O(n²)。

选项2

这种说法有两种变体:

2a)如果你不关心保持列表的顺序……在两个列表上使用Collections.sort()。然后使用equals()。这是O(nlogn)因为你做了两次排序,然后是O(n)比较。

2b)如果你需要保持列表的顺序,你可以先复制两个列表。然后,您可以在两个复制的列表上使用解决方案2a。然而,如果复制非常昂贵,这可能没有吸引力。

这导致:

选项3

如果你的要求和2b部分一样,但是复制太贵了。您可以使用TreeSet为您进行排序。将每个列表转储到它自己的TreeSet中。它将在集合中排序,原始列表将保持不变。然后对两个树集执行equals()比较。TreeSetss可以在O(nlogn)时间内构建,equals()是O(n)。

你选吧:-)。

编辑:我差点忘了Laurence Gonsalves指出的同样的警告。TreeSet实现将消除重复项。如果关心重复项,则需要某种排序的多集。

其他回答

这取决于您使用的具体List类。抽象类AbstractCollection有一个名为containsAll(Collection)的方法,它接受另一个集合(List是一个集合),并且:

如果此集合包含指定集合中的所有元素,则返回true。

如果传入一个数组列表你可以调用这个方法来检查它们是否完全相同。

       List foo = new ArrayList();
    List bar = new ArrayList();
    String str = "foobar";

    foo.add(str);
    bar.add(str);

    foo.containsAll(bar);

使用containsAll()的原因是它遍历第一个列表以查找第二个列表中的匹配项。因此,如果它们的顺序不对,equals()将不会拾取它。

编辑: 我只是想在这里对执行所提供的各种选项的平摊运行时间做一个评论。运行时间重要吗?确定。这是你唯一应该考虑的事情吗?不。

从列表中复制每个元素到其他列表的成本需要时间,而且还占用大量内存(有效地使您所使用的内存增加一倍)。

因此,如果JVM中的内存不是问题(通常应该是),那么您仍然需要考虑将每个元素从两个列表复制到两个TreeSets所花费的时间。记住,它在输入每个元素时对它们进行排序。

我最后的建议?你需要考虑你的数据集,你的数据集中有多少元素,以及你的数据集中每个对象有多大,然后你才能做出好的决定。摆弄它们,每种方式创建一个,看看哪个运行得更快。这是一个很好的练习。

我的解决方案适用于不关心列表中的顺序的情况——换句话说:具有相同元素但顺序不同的列表将被认为具有相同的内容。

示例:["word1", "word2"]和["word2", "word1"]被认为内容相同。

我已经谈到了订购,我还需要说一些关于副本的事情。列表需要具有相同数量的元素才能被认为是相等的。

例如:["word1"]和["word1", "word1"]被认为不具有相同的内容。

我的解决方案:

public class ListUtil {

    public static <T> boolean hasSameContents(List<T> firstList, List<T> secondList) {      
        if (firstList == secondList) { // same object
            return true;
        }
        if (firstList != null && secondList != null) {
            if (firstList.isEmpty() && secondList.isEmpty()) {
                return true;
            }
            if (firstList.size() != secondList.size()) {
                return false;
            }
            List<T> tmpSecondList = new ArrayList<>(secondList);
            Object currFirstObject = null;
            for (int i=1 ; i<=firstList.size() ; i++) {
                currFirstObject = firstList.get(i-1);
                boolean removed = tmpSecondList.remove(currFirstObject);
                if (!removed) {
                    return false;
                }
                if (i != firstList.size()) { // Not the last element
                    if (tmpSecondList.isEmpty()) {
                        return false;
                    }
                }
            }
            if (tmpSecondList.isEmpty()) {
                return true;
            }
        }
        return false;
    }
}

我用Strings进行了测试,如下所示:

@Test public void testHasSameContents() throws Exception { // comparing with same list => no duplicate elements Assert.isTrue(ListUtil.hasSameContents(List.of("one", "two", "three"), List.of("one", "two", "three"))); // comparing with same list => duplicate elements Assert.isTrue(ListUtil.hasSameContents(List.of("one", "two", "three", "one"), List.of("one", "two", "three", "one"))); // compare with disordered list => no duplicate elements Assert.isTrue(ListUtil.hasSameContents(List.of("one", "two", "three"), List.of("three", "two", "one"))); // compare with disordered list => duplicate elements Assert.isTrue(ListUtil.hasSameContents(List.of("one", "two", "three", "one"), List.of("three", "two", "one", "one"))); // comparing with different list => same size, no duplicate elements Assert.isFalse(ListUtil.hasSameContents(List.of("one", "two", "three"), List.of("four", "five", "six"))); // comparing with different list => same size, duplicate elements Assert.isFalse(ListUtil.hasSameContents(List.of("one", "two", "two"), List.of("one", "two", "three"))); Assert.isFalse(ListUtil.hasSameContents(List.of("one", "two", "three"), List.of("one", "two", "two"))); // comparing with different list => different size, no duplicate elements Assert.isFalse(ListUtil.hasSameContents(List.of("one", "two", "three", "four"), List.of("one", "two", "three"))); Assert.isFalse(ListUtil.hasSameContents(List.of("one", "two", "three"), List.of("one", "two", "three", "four"))); // comparing with different list => different sizes, duplicate elements Assert.isFalse(ListUtil.hasSameContents(List.of("one", "two", "three", "one"), List.of("one", "two", "three"))); Assert.isFalse(ListUtil.hasSameContents(List.of("one", "two", "three"), List.of("one", "two", "three", "one"))); }

你可以使用Apache的org.apache.commons.collections库: http://commons.apache.org/collections/apidocs/org/apache/commons/collections/ListUtils.html

public static boolean isEqualList(java.util.Collection list1,
                              java.util.Collection list2)

如果你关心顺序,那么只需使用equals方法:

list1.equals(list2)

来自javadoc:

Compares the specified object with this list for equality. Returns true if and only if the specified object is also a list, both lists have the same size, and all corresponding pairs of elements in the two lists are equal. (Two elements e1 and e2 are equal if (e1==null ? e2==null : e1.equals(e2)).) In other words, two lists are defined to be equal if they contain the same elements in the same order. This definition ensures that the equals method works properly across different implementations of the List interface.

如果你想检查与顺序无关,你可以复制所有的元素到set,并在结果集上使用equals:

public static <T> boolean listEqualsIgnoreOrder(List<T> list1, List<T> list2) {
    return new HashSet<>(list1).equals(new HashSet<>(list2));
}

这种方法的一个局限性是它不仅忽略了顺序,而且还忽略了重复元素的频率。例如,如果list1是["A", "B", "A"], list2是["A", "B", "B"],则Set方法将认为它们相等。

如果你需要对顺序不敏感,但对重复的频率敏感,你可以:

在比较它们之前对两个列表(或副本)进行排序,就像在回答另一个问题时所做的那样 或复制所有元素到Multiset

我知道这可能非常晚,但我个人使用这个功能。 如果有人想做一些基准测试,那就太好了。

public static<X> boolean areEqual(List<X> a, List<X> b, BiPredicate<X, X> AEqualsB) {
        boolean aIsNull = a == null;
        boolean bIsNull = b == null;
        if (aIsNull || bIsNull) {
            return aIsNull == bIsNull;
        }
        int size = a.size();
        boolean sameSize = size == b.size();
        if (!sameSize) {return false;} else {
            for (int i = 0; i < size; i++) {
                X aX = a.get(i), bX = b.get(i);
                boolean areEqual = AEqualsB.test(aX, bX);
                if (!areEqual) {
                    return false;
                }
            }
            return true;
        }
    }

顺便说一句,我知道前5行可以用一个异或“^”加上一个else来简化,但信不信由你,我很难得出正确的异或。

我想它的效率取决于谓词的类型,但同时它允许您检查自定义的潜在相等,而忽略对编码器来说可能无关紧要的差异。

下面是一个代码示例。

ListUtils.areEqual(newElements, oldElements, Element::areEqual)

public boolean areEqual(Element e) {
        return optionalAdapterId() == e.optionalAdapterId()
                && value == e.value
                && valueTotal == e.valueTotal
                && stockTotal == e.stockTotal
                && element_title.equals(e.element_title);
    }

至于效率,我认为任何迭代总是昂贵,这就是为什么每当我需要使用这个函数与大名单,我在一个单独的线程执行的操作,和检索响应的需要,即使它很高兴知道此时,它是有益的在一个不同的线程,是什么项目,要求这些线程的数量,这些信息将被添加文档。