如何比较两个ArrayList？

Question

我有两个 ArrayList，每个大小为100000。我想比较它们并计算匹配的元素数量。

以下是我的代码:

for (int i = 0; i < mArryLst2.size(); i++) {
   if (ArryLst1.contains(mArryLst2.get(i))) {
       matchedPixels++;         
   }
}

这里的比较过程花费了很多时间。

如何解决和优化这个问题。

- SuReSh PaTi

---

为了方便比较对象，你应该使用Set/HashSet而不是List/ArrayList。 - Maurício Linhares

数组列表元素的类型是什么？ - fge

此外，元素是否唯一？看起来是的。如果是，你应该使用 HashSet 而不是 ArrayList。 - fge

如果一个元素 E 在 array1 中出现一次，在 array2 中出现两次，这算作一次还是两次匹配？如果在两个数组中都出现了两次呢？ - Andreas Mayer

Answer 1

你应该使用 CollectionUtils.retainAll：返回一个包含collection1中所有同时也在collection2中的元素的集合。

ArrayList commonList = CollectionUtils.retainAll(list1,list2);

- dku.rajkumar

---

他们是否需要访问共同元素或只是它们的计数？ - helios

请提供JAR文件的链接。 - chopss

你可以在commons-collections.jar中找到它，有很多网站可以下载。 - dku.rajkumar

从这里下载commons-collections.jar => http://www.java2s.com/Code/Jar/o/Downloadorgapachecommonscollectionsjar.htm - NIKHIL CHAURASIA

Answer 2

你应该将第一个列表转换为一个HashSet。HashSet的查找时间复杂度是O(1)，而List的查找时间复杂度是O(n)。这使得整个算法的时间复杂度变为O(n)，而不再是O(n^2)。

Set<Foo> set1 = new HashSet<Foo>(list1);
for (Foo foo : list2) {
    if (set1.contains(foo)) {
        matchedPixels++;
    }
}

- JB Nizet

---

那又怎样？楼主想要检查列表是否包含某个元素。如果它包含，则集合也将包含它。如果它不包含，则集合也不包含它。 - JB Nizet

ops方法的结果可能与使用HashSets的结果不同，这就是重点。 - fyr

不，它不能不同。请重新阅读我的评论。OP没有计算列表中元素出现的次数。它只检查它是否在列表中。它怎么可能在列表中而不在包含与列表相同元素（仅一次而不是多次）的集合中呢？ - JB Nizet

很多人建议这个解决方案，但是因为给出了为什么它会更快的解释，所以加一分。 - Caner

@JB Nizet：该操作遍历ArrayList mArryLst2。mArryLst2可能包含重复项..！如果mArryLst2包含元素“1”，“1”和mArryLst2“1”，则结果将为2。使用HashSet不会得到此结果。 - fyr

这就是为什么我的答案告诉OP将第一个列表转换为HashSet，而不是第二个。 - JB Nizet

Answer 3

你应该查看这个链接 如何在Java中比较两个ArrayList的值？。复制其中一个列表，然后对另一个列表调用removeAll方法。

List result = new ArrayList(mArryLst2);
result.removeAll(ArryLst1); 

- Kamran Ali

Answer 4

有几种方法可以加快这个过程（特别是对于大型数组），并简化代码；

    // Quick Check to see if the two arrayLists have the same number of elements
    if (array1.size() != array2.size())
        return false;

    // Optionally Sort the arrays - avoid returning false if the elements are the same but 
    // have been stored out of sequence
    Collections.sort(array1);
    Collections.sort(array2);

    if (array1.hashCode() == array2.hashCode()) {
        return true;
    } else {
        return false;
    }

- Bob

---

如果你想暗示两个ArrayLists array1和array2如果具有相同的哈希码则包含相同元素，那么你是错误的！ - Andreas Mayer

排序只有在元素之间存在一个全序关系（该帖子没有提到）时才有用，这种情况下，您可以使用二分搜索在另一个 ArrayList 中查找其中一个的元素。为此，您只需对其中一个进行排序即可。 - Andreas Mayer

Answer 5

您可以使用

ArrayList Listname = ListUtils.retainAll(list1,list2);

- chopss

---

请注意，ListUtils 不是 Android 原生类，它来自于 Apache Commons Collections。 - Sharp Edge

Answer 6

最好的选择是将第一个ArrayList的所有元素放入Set中（它只允许唯一的元素）。 现在，从你的第二个ArrayList中，将每个元素添加到你的Set中，如果元素已经存在于你的Set中，则会返回false。

如果你有两个ArrayList，ArrayList1和ArrayList2，并且你想将所有匹配项放入另一个ArrayList Diff中。

HashSet hs = new HashSet();

for(int i : ArrayList1) hs.add(i);

for(int i : ArrayList2)  
 {

if(!hs.add(i))
  Diff.add(i);

 }

- Rajesh Pantula

Answer 7

我认为这样会更快

    Set set = new HashSet();
    set.addAll(ArryLst1);

    for (int i = 0; i <mArryLst2.size(); i++)
    {
       if (set .contains(mArryLst2.get(i))) 
       {
             matchedPixels++;        
       }
    }

- narek.gevorgyan

Answer 8

最好的方法是覆盖equals方法并检查您的数组列表中的每个对象是否相等。

    public class CustomClass {
        String x;
        String a;
        String b;
        String c;
        long l;
        @Override
        public boolean equals(Object obj) {
            return (this.blindlyEquals(obj) && ((CustomClass) obj).blindlyEquals(this));
        }
        protected boolean blindlyEquals(Object o) {
            if (!(o instanceof CustomClass))
                return false;
            CustomClass p = (CustomClass)o;
            return (p.x == this.x && p.a == this.a && p.b == this.b && p.c == this.c && p.l == this.l);
        }

    }


    public class MainClass {

        ArrayList<CustomClass> member = new ArrayList<CustomClass>();
        ArrayList<CustomClass> server;
        /**
         * @param args
         */

        public static void main(String[] args) {
            // TODO Auto-generated method stub
            MainClass mainClass = new MainClass();
            mainClass.server = mainClass.getServerList();
            mainClass.member = mainClass.getLocalList();


            if(mainClass.member.equals(mainClass.server)){
                System.out.println("true");
//do the needfull, run a for loop to check which object is  not equal
            }else{
                System.out.println("false");
//do the needfull, run a for loop to check which object is  not equal
            }

        }
        public ArrayList<CustomClass> getServerList(){
            ArrayList<CustomClass> server = new ArrayList<CustomClass>();
            CustomClass obj = new CustomClass();
            CustomClass obj2 = new CustomClass();
            obj.a = "ali";
            obj.b = "ball";
            obj.c = "cat";
            obj.x = "xerox";
            obj.l = 10;

            obj2.a = "ali";
            obj2.b = "ball";
            obj2.c = "cat";
            obj2.x = "xerox";
            obj2.l = 10;

            server.add(obj);
            server.add(obj2);
            return server;
        }

        public ArrayList<CustomClass> getLocalList(){
            ArrayList<CustomClass> memberOne = new ArrayList<CustomClass>();
            CustomClass obj = new CustomClass();
            CustomClass obj2 = new CustomClass();
            obj.a = "ali";
            obj.b = "ball";
            obj.c = "cat";
            obj.x = "xerox";
            obj.l = 10;

            obj2.a = "ali";
            obj2.b = "ball";
            obj2.c = "cat";
            obj2.x = "xerox";
            obj2.l = 10;

            memberOne.add(obj);
            memberOne.add(obj2);
            return memberOne;
        }
    }

- Ali Ashraf