Java 流 - 从其他两个列表中获取 "symmetric difference list"

Question

我正在尝试使用 Java 8 个流来合并列表。如何从两个现有列表中获取 "symmetric difference list"（所有对象仅存在于一个列表中）。我知道如何获得相交列表以及如何获得联合列表。

在下面的代码中，我想要来自两个汽车列表（bigCarList、smallCarList）的不相交的汽车。我希望结果是包含 2 辆车的列表（"Toyota Corolla" 和 "Ford Focus"）

示例代码：

public void testDisjointLists() {
    List<Car> bigCarList = get5DefaultCars();
    List<Car> smallCarList = get3DefaultCars();

    //Get cars that exists in both lists
    List<Car> intersect = bigCarList.stream().filter(smallCarList::contains).collect(Collectors.toList());

    //Get all cars in both list as one list
    List<Car> union = Stream.concat(bigCarList.stream(), smallCarList.stream()).distinct().collect(Collectors.toList());

    //Get all cars that only exist in one list
    //List<Car> disjoint = ???

}

public List<Car> get5DefaultCars() {
    List<Car> cars = get3DefaultCars();
    cars.add(new Car("Toyota Corolla", 2008));
    cars.add(new Car("Ford Focus", 2010));
    return cars;
}

public List<Car> get3DefaultCars() {
    List<Car> cars = new ArrayList<>();
    cars.add(new Car("Volvo V70", 1990));
    cars.add(new Car("BMW I3", 1999));
    cars.add(new Car("Audi A3", 2005));
    return cars;
}

class Car {
    private int releaseYear;
    private String name;
    public Car(String name) {
        this.name = name;
    }
    public Car(String name, int releaseYear) {
        this.name = name;
        this.releaseYear = releaseYear;
    }

    //Overridden equals() and hashCode()
}

Answer 1

类似这样的方法可能有效：

Stream.concat(bigCarList.stream(), smallCarList.stream())
      .collect(groupingBy(Function.identity(), counting()))
      .entrySet().stream()
      .filter(e -> e.getValue().equals(1L))
      .map(Map.Entry::getKey)
      .collect(toList());

这里我们首先收集所有的车到Map<Car, Long>，其中value是遇到的这种车的数量。之后，我们 filter 这个 Map 只留下恰好遇到过一次的汽车，丢弃计数并收集到最后的 List.

Answer 2

根据您自己的代码，有一个直接的解决方案：

List<Car> disjoint = Stream.concat(
    bigCarList.stream().filter(c->!smallCarList.contains(c)),
    smallCarList.stream().filter(c->!bigCarList.contains(c))
).collect(Collectors.toList());

只需过滤一个列表中未包含在另一个列表中的所有项目，反之亦然，然后连接两个结果。这对于小型列表非常有效，在考虑优化解决方案（如散列或生成结果）之前 distinct() 你应该问问自己，如果你既不想要重复也不想要特定顺序，为什么要使用列表。

您似乎真的想要 Set，而不是 List。如果使用Sets，则是合适的。但它不适用于 List 的实际语义，即如果源列表包含重复项则不起作用。

但是如果你使用的是Sets，代码可以更简单：

Set<Car> disjoint = Stream.concat(bigCarSet.stream(), smallCarSet.stream())
  .collect(Collectors.toMap(Function.identity(), t->true, (a,b)->null))
  .keySet();

这使用了 toMap 收集器，它创建了一个 Map（值是无关紧要的，我们在这里简单地映射到 true）并使用合并函数来处理重复项。由于对于两个集合，只有当两个集合中都包含一个项目时才会出现重复项，因此这些是我们要删除的项目。

documentation of Collectors.toMap says that the merge function is treated “as supplied to Map.merge(Object, Object, BiFunction)”，我们可以从那里了解到，只需将重复对映射到 null 即可删除该条目。

所以之后，地图的 keySet() 包含不相交集。

Answer 3

一点数学知识

不相交 = 如果 A 和 B 的相交为空，则它们不相交。

不相交不是集合，它是两个集合是否不相交的指标。根据你的描述，我认为你在哪里搜索 symmetric difference.

对称差异

但是无论如何，如果你只想收集到新的列表，那么你只需要一个收集器。

我创建了一个创建收集器的方法。此收集器仅“收集”值，其中谓词被评估为真。因此，如果您正在搜索对称差异，那么您只需要一个谓词。

  public void testDisjointLists() {
    List<Car> bigCarList = get5DefaultCars();
    List<Car> smallCarList = get3DefaultCars();

    Collector<Car, ArrayList<Car>, ArrayList<Car>> inter
        = produceCollector(car -> {
          return bigCarList.contains(car) && smallCarList.contains(car);
        });

    Collector<Car, ArrayList<Car>, ArrayList<Car>> symDiff
        = produceCollector(car -> {
          return bigCarList.contains(car) ^ smallCarList.contains(car);
        });

    //Get all cars in both list as one list
    List<Car> union
        = Stream.concat(bigCarList.stream(), smallCarList.stream()).distinct().collect(Collectors.toList());

    List<Car> intersect = union.stream().collect(inter);

    //Get all cars that only exist not exists in both Lists
    List<Car> symmetricDifference = union.stream().collect(symDiff);

    System.out.println("Union Cars:");
    union.stream().forEach(car -> System.out.println("Car: " + car));
    System.out.println("");

    System.out.println("Intersect Cars: ");
    intersect.stream().forEach(car -> System.out.println("Car: " + car));
    System.out.println("");

    System.out.println("Symmetric Difference: ");
    symmetricDifference.stream().forEach(car -> System.out.println("Car: " + car));
    System.out.println("");
  }

  public Collector<Car, ArrayList<Car>, ArrayList<Car>> produceCollector(Predicate<Car> predicate) {
    Collector<Car, ArrayList<Car>, ArrayList<Car>> collector = Collector.of(
        ArrayList::new,
        (al, car) -> {
          if (predicate.test(car)) {
            al.add(car);
          }
        },
        (al1, al2) -> {
          al1.addAll(al2);
          return al1;
        }
    );
    return collector;
  }

对于性能怪胎

经过一些研究，收集器似乎比第一个过滤器解决方案快 14 倍。

long before2 = System.nanoTime();
List<Car> intersect2 = union.stream().filter(car -> {
  return bigCarList.contains(car) && smallCarList.contains(car);
}).collect(Collectors.toList());
long after2 = System.nanoTime();
System.out.println("Time for first filter solution: " + (after2 - before2));


long before = System.nanoTime();
List<Car> intersect = union.stream().collect(inter);
long after = System.nanoTime();
System.out.println("Time for collector solution: " + (after - before));

第一个过滤器解决方案时间：540906

收集器解决时间：37543

Answer 4

另一种方法，虽然不如单行流那么优雅：

    HashMap<Integer, Boolean> y = new HashMap<>();
    bigCarSet ().forEach(i -> y.put(i, !y.containsKey(i)));
    bigCarList().forEach(i -> y.put(i, !y.containsKey(i)));
    y.entrySet().stream().filter(Map.Entry::getValue).map(Map.Entry::getKey)
     .collect(Collectors.toList());

至少可以简化为：

    HashMap<Integer, Boolean> y = new HashMap<>();
    Stream.concat(list1.stream(), list2.stream()).forEach(i -> y.put(i, !y.containsKey(i)));
    y.entrySet().stream().filter(Map.Entry::getValue)
                 .map(Map.Entry::getKey).collect(Collectors.toList());

Answer 5

OP 要求对称差异。而对称差可以表示为：

或并集与交集的区别：

A△B=(A∪B)-(B∩A)
或差并集：

A△B=(A-B)∪(B-A)

的第一部分通过#2实现，而第二部分通过#1实现。在这里，我将展示方法 #1 的变体：

List<Car> result = new ArrayList<>(bigCarList);
result.addAll(smallCarList); // (A ∪ B)

result.removeIf(c -> bigCarList.contains(c) && smallCarList.contains(c)); // (B ∩ A)

如果将列表转换为集合，这可以优化，因此使用 contains 是 O(1):

List<Car> bigCarList = get5DefaultCars();
List<Car> smallCarList = get3DefaultCars();

Set<Car> bigCarSet = new HashSet<>(bigCarList);
Set<Car> smallCarSet = new HashSet<>(smallCarList);

Set<Car> result = new LinkedHashSet<>(bigCarList);
result.addAll(smallCarList); // (A ∪ B)

result.removeIf(c -> bigCarSet.contains(c) && smallCarSet.contains(c)); // (B ∩ A)

Answer 6

lambda 解决方案 groupingBy:
带有 true 键的地图值在两个列表中
false键的地图值是不相交的

Map<Boolean,List<Car>> map = Stream.concat(bigCarList.stream(),
    smallCarList.stream()).collect(
        groupingBy( b -> bigCarList.stream().anyMatch( s -> b.equals( s ) )
            && smallCarList.stream().anyMatch( s -> b.equals( s ) ) ) );
List<Car> disjoint = map.get( false );  // [Toyota Corolla, Ford Focus]

相同的原理但更短 w/o 内联流：

Map<Boolean,List<Car>> map = Stream.concat(bigCarList.stream(),
    smallCarList.stream()).collect(
        groupingBy( b -> bigCarList.contains( b )
            && smallCarList.contains( b ) ) );
List<Car> disjoint = map.get( false );  // [Toyota Corolla, Ford Focus]

两者都在处理重复项
表示：一个列表中的重复项不包含在另一个列表中
如果数据量没有大到运行进入磁盘 space 问题，一个简单的 groupingBy - 没有过滤或额外的查询来减少结果集 - 应该是最清晰和最快的解决方案。

Java 流 - 从其他两个列表中获取 "symmetric difference list"

Java Streams - Get a "symmetric difference list" from two other lists

java

list

java-8

java-stream

一点数学知识

对称差异

对于性能怪胎