Java Streams - 从其他两个列表中获取“对称差异列表”

问题描述 投票：0回答：7

我正在尝试使用 Java 8 流来组合列表。 如何从两个现有列表中获取“对称差异列表”（仅存在于一个列表中的所有对象）。 我知道如何获取相交列表以及如何获取并集列表。

在下面的代码中，我想要两个汽车列表（bigCarList，smallCarList）中不相交的汽车。 我希望结果是包含 2 辆汽车（“丰田花冠”和“福特福克斯”）的列表

示例代码：

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()
}
java list java-8 java-stream
7个回答
12
投票

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

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
，
Tagir Valeev 的解决方案
是合适的。但它不适用于 Sets 的实际语义，即如果源列表包含重复项则不起作用。

但是如果您使用
List

，代码可以更简单：
Set

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

收集器创建一个 

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

true

的

文档说合并函数被视为“提供给
Collectors.toMap
”，我们可以从中了解到，只需将重复对映射到
Map.merge(Object, Object, BiFunction)就会删除该条目。
所以之后，地图的

null

包含不相交集合。

6
投票

keySet()

这里我们首先将所有汽车收集到
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());

，其中value是遇到的此类汽车的数量。之后，我们

Map<Car, Long>
这个
filter
只留下恰好遇到过一次的汽车，丢弃计数并收集到最后的
Map
。

0
投票

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

不相交不是一个集合，它是一个指示符，显示两个集合是否不相交。根据您的描述，我认为您正在寻找

对称差异

。 对称差

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

我做了一个创建收集器的方法。此收集器仅“收集”谓词评估为 true 的值。因此，如果您正在寻找对称差异，那么您只需要一个谓词。

List

对于性能狂来说

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

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; } 

首次过滤解决方案时间：540906

收集器解决时间：37543

0
投票

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)); 

至少可以简化为：

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()); 




    

    
    
    

    

        

            

                

                    
0
投票

                    
                

            

        

        




    无论是并集还是交集的区别：
  1. 

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

    

    2. 或者差异的并集：
  2. 

    A △ B = (A – B) ∪ (B – A)
    

    

    

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

    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());


如果将列表转换为集合，可以对此进行优化，这样使用 
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)

    



    

    
    
    

    

        

            

                

                    
0
投票

                    
                

            

        

        
 
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)
的 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]


两者都在处理重复项

表示：一个列表中不包含在另一列表中的重复项

如果数据量不是很大，以至于您遇到磁盘空间问题，那么简单的 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]
 - 无需过滤或其他查询来减少结果集 - 应该是最清晰、最快的解决方案。

    


groupingBy

    

    
    
    

    

        

            

                

                    
0
投票

                    
                

            

        

        

	



    

    


  

  

    
最新问题


  





  

    © www.soinside.com 2019 - 2024. All rights reserved.