从两个不同的 ArrayLists 中找到唯一交叉点的最有效方法？

Question

我有两个数组列表，A 和 B。

ArrayList A 由类组成，它由一组数据组成，包括一个名为 categoryID 的标识符。 A 中的多个项目可以具有相同的 categoryID。 A 中每个项目的类别 ID 可能如下所示：[1, 1, 2, 2, 3, 4, 7].

ArrayList B 由包含不同数据集的不同类组成，其中包括 categoryID。 categoryID 对于此列表中的每个项目都是唯一的。示例：[1, 2, 3, 4, 5, 6, 7]。

两个列表都按 categoryID 排序，希望这能让这更容易。

我想做的是提出一个新列表 C，其中包含列表 B 中至少与列表 A 有一个交集的项目。所以列表 C 应该包含来自上面给定输入的项目 [1, 2, 3, 4, 7]。

到目前为止，我的策略是遍历两个列表。我不认为这是执行此操作的最有效方法，所以我想问一下我可以考虑的其他替代方法是什么。

我的方法：

ArrayList<classB> results = new ArrayList<classB>();
for (classA itemA : listA){
  int categoryID = item.categoryID;
  for (classB itemB : listB){
    if (itemB.categoryID == categoryID){
      if (!results.contains(itemB)){
        results.add(itemB);
      }
      break;
    }
  }
}

我首先遍历列表 A，获取类别 ID，然后遍历列表 B 以找到匹配的类别 ID。当我找到它时，我检查结果列表是否包含 listB 中的此项。如果没有，那么我将它添加到结果中并跳出内部 for 循环并继续遍历 listA。如果结果列表已经包含 itemB，那么我将简单地跳出内部 for 循环并继续遍历 listA。这种方法是 O(n^2)，这对于大数据集来说不是很好。有什么改进的想法吗？

Answer 1

将 ListA 中的所有类别 ID 添加到 Set，我们称之为 setACategories。然后，循环遍历 ListB，如果 setACategories 包含 ListB 中某个元素的 categoryID，则将 ListB 的该元素添加到 results.

results 也应该是 Set，因为看起来您只希望 listB 中的一个匹配项进入 results 而不是多个匹配项（允许您避免调用至 (!results.contains(itemB)).

Answer 2

将 listA 中的 categoryID 值添加到 Set 中，然后遍历列表，选择 categoryId 在您的集合中的那些元素。

Answer 3

现在最好的方法是使用 java 流：

List<foo> list1 = new ArrayList<>(Arrays.asList(new foo(), new foo()));
List<foo> list2 = new ArrayList<>(Arrays.asList(new foo(), new foo()));
list1.stream().filter(f -> list2.contains(f)).collect(Collectors.toList());

但是，我自己使用 apache commons 库来处理这类东西：

https://commons.apache.org/proper/commons-collections/javadocs/api-3.2.1/org/apache/commons/collections/CollectionUtils.html

Answer 4

尝试使用 Google Guava 中的 Sets.intersection(Set<E> set1,Set<?> set2)。

当然，您可以使用 Sets.newHashSet(Iterable<? extends E> elements)

将数组转换为集合

Answer 5

你试过了吗：

public void test() {
    Collection c1 = new ArrayList();
    Collection c2 = new ArrayList();

    c1.add("Text 1");
    c1.add("Text 2");
    c1.add("Text 3");
    c1.add("Text 4");
    c1.add("Text 5");

    c2.add("Text 3");
    c2.add("Text 4");
    c2.add("Text 5");
    c2.add("Text 6");
    c2.add("Text 7");

    c1.retainAll(c2);

    for (Iterator iterator = c1.iterator(); iterator.hasNext();) {
        Object next = iterator.next();
        System.out.println(next);  //Output: Text 3, Text 4, Text 5
    }
}

Answer 6

见以下代码。我已经实现了一个交集，它使用对它们进行排序的事实来改进最佳答案的方法。

它有点像合并排序中的合并步骤，除了它确保交集。应该还可以再改进吧，我30分钟写完了

根据当前数据，它的运行速度比最佳答案快 17 倍。它还节省了 O(n) 内存，因为它只需要一组

另见：The intersection of two sorted arrays

import java.util.*;

public class test {
    public static void main (String[] args) {
        List<Integer> a1 = new ArrayList<Integer>();
        List<Integer> a2 = new ArrayList<Integer>();
        Random r = new Random();

        for(int i = 0; i < 1000000; i++) {
            a1.add(r.nextInt(1000000));
            a2.add(r.nextInt(1000000));
        }

        Collections.sort(a1);
        Collections.sort(a2);

        System.out.println("Starting");

        long t1 = System.currentTimeMillis();
        Set<Integer> set1 = func1(a1, a2);
        long t2 = System.currentTimeMillis();

        System.out.println("Func1 done in: " + (t2-t1) + " milliseconds.");

        long t3 = System.currentTimeMillis();
        Set<Integer> set2 = func2(a1, a2);
        long t4 = System.currentTimeMillis();

        System.out.println("Func2 done in: " + (t4-t3) + " milliseconds.");

        if(set1.size() != set2.size()) {
            System.out.println("ERROR - sizes not equal");
            System.exit(1);
        }

        for(Integer t : set1) {
            if (!set2.contains(t)) {
                System.out.println("ERROR");
                System.exit(1);
            }
        }
    }

    public static Set<Integer> func1(List<Integer> a1, List<Integer> a2) {
        Set<Integer> intersection = new HashSet<Integer>();

        int index = 0;
        for(Integer a : a1) {

            while( index < a2.size() && a2.get(index) < a) {
                index++;
            } 

            if(index == a2.size()) { 
                break;
            }
            if (a2.get(index).equals(a)) {
                intersection.add(a);
            } else {
                continue;
            }

        }

        return intersection;
    }

    public static Set<Integer> func2(List<Integer> a1, List<Integer> a2) {
        Set<Integer> intersection = new HashSet<Integer>();
        Set<Integer> tempSet = new HashSet<Integer>();
        for(Integer a : a1) {
            tempSet.add(a);
        }

        for(Integer b : a2) {
            if(tempSet.contains(b)) {
                intersection.add(b);
            }
        }

        return intersection;
    }
}

从两个不同的 ArrayLists 中找到唯一交叉点的最有效方法？

Most efficient way to find unique intersections from two different ArrayLists?

java

performance

optimization

arraylist