Установите соединение и пересечение, используя потоки Java - PullRequest
Новая
       33

Установите соединение и пересечение, используя потоки Java

0 голосов
/ 13 марта 2019

В настоящее время у меня есть Java-программа, которая использует вложенные циклы for для вычисления объединения и пересечения списка набора целых чисел. Как это сделать, используя java параллельные потоки? Код, который у меня есть в настоящее время, выглядит следующим образом 

for(Set<Integer> x : listA) {
  for (Set<Integer> y : listB) {
       Set u = Sets.union(x,y); // Uses Guava library
       Set i = Sets.intersection(x,y);
  }
}

Я бы хотел сделать это быстро, так как listA и listB велики.

Ответы [ 4 ]

2 голосов
/ 13 марта 2019

Если вы гарантируете, что y (и x) отсортированы / стали, как класс TreeSet, следующее использует специальное объединение (внутренний метод addAllForTreeSet). 

for (Set<Integer> x : listA) {
    for (SortedSet<Integer> y : listB) {
        SortedSet<Integer> u = new TreeSet(x);
        u.addAll(y);
        SortedSet<Integer> i = new TreeSet(x);
        i.retainAll(y);
    }
}

Является ли этона самом деле быстрее, я не уверен.

Лучше было бы, если бы целые числа не были слишком дикими, ограничиваясь, скажем, 10_000.Если значения неотрицательны, можно сразу использовать BitSet вместо Set<Integer>.

Это непобедимо.Используйте конструктор BitSet с вероятной емкостью (например, 10_000). 

for (BitSet x : listA) {
    for (BitSet y : listB) {
        BitSet u = x.clone();
        u.or(y);
        BitSet i = x.clone();
        i.and(y);
    }
}

. Можно использовать параллельный поток для сохранения коэффициента, равного числу процессоров. 

listA.parallelStream().forEach(x -> {});

То естьвторичная оптимизация.

Гуава, которой я не пользовался в последние годы, не было ли наборов примитивного типа int?

2 голосов
/ 13 марта 2019

Вам не нужны потоки для объединения, однако вы можете использовать его для пересечения, например: 

Set<Integer> setA = new HashSet<>(Arrays.asList(1,2,3));
Set<Integer> setB = new HashSet<>(Arrays.asList(2,3,4));
Set<Integer> union = new HashSet<>();
union.addAll(setA);
union.addAll(setB);

Set<Integer> intersection = setA.parallelStream()
        .filter(setB::contains)
        .collect(Collectors.toSet());

System.out.println("Union : " + union);
System.out.println("Intersection : " +intersection);

Обновление

Приведенный выше код находит пересечениеи объединение с использованием собственных библиотек Java и streams.Однако, если у вас есть список наборов, вы можете заключить приведенный выше код в функцию и вызвать его из stream, который повторяет два списка, например: 

private static void unionAndIntersection(Set<Integer> setA, Set<Integer> setB) {
    Set<Integer> union = new HashSet<>();
    union.addAll(setA);
    union.addAll(setB);

    Set<Integer> intersection = setA.parallelStream()
            .filter(setB::contains)
            .collect(Collectors.toSet());

    System.out.println("Union : " + union);
    System.out.println("Intersection : " +intersection);
}

public static void main(String[] args){ 
    List<Set<Integer>> listA = new ArrayList<>();
    List<Set<Integer>> listB = new ArrayList<>();
    listA.stream()
        .forEach(a -> {
            listB.stream()
            .forEach(b -> unionAndIntersection(a, b));
        });
}
1 голос
/ 13 марта 2019

Пересечение: 

List<T> intersect = list1.stream()
                         .filter(list2::contains)
                         .collect(Collectors.toList());

Объединение: 

List<T> union = Stream.concat(list1.stream(), list2.stream())
                                    .distinct()
                                    .collect(Collectors.toList());
1 голос
/ 13 марта 2019

Стоит отметить, что вам не нужно использовать потоки для объединения, а также для пересечения.Существует метод retainAll, который сохраняет только элементы в этой коллекции, которые содержатся в указанной коллекции: 

Set<Integer> setA = new HashSet<>(Arrays.asList(1,2,3));
Set<Integer> setB = new HashSet<>(Arrays.asList(2,3,4));

setA.retainAll(setB);  // now setA has intersection
...