Część wspólna zbiorów z Guavą

Szybkie rozwiązanie problemu opisanego tutaj. Mamy dwa zbiory A i B, chcemy sprawdzić, czy wszystkie elementy ze zbioru A są obecne w zbiorze B. Najprościej jest to zrobić w następujący sposób:

Listing 1. Wykorzystanie API

public class SetsIntersectionExample {

	public static void main(String[] args) {
		// Smoki i gołe baby
		Fairy fairy = Fairy.create();

		Set<String> persons = Stream.generate(() -> fairy.person(PersonProperties.male())).limit(100)
				.map(Person::firstName)
				.collect(Collectors.toSet());
		// Magia, bo chcemy mieć pewność, że mamy istniejące imiona.
		Set<String> names = Sets.newHashSet((String) persons.toArray()[0], (String) persons.toArray()[1]);
		// end: Smoki i gołe baby
		
		System.out.println(persons);
		System.out.println(names);
		System.out.println(persons.containsAll(names));
	}
}

Takie rozwiązanie podał Jakub Dyszkiewicz i prościej się nie da. Cytując dokumentację:

Returns true if this set contains all of the elements of the specified collection. If the specified collection is also a set, this method returns true if it is a subset of this set.

źródło

Przy czym jest, to dość słabo zaimplementowane:

Listing 2. AbstractCollection.containsAll wygląda tak:

public boolean containsAll(Collection<?> c) {
    for (Object e : c)
        if (!contains(e))
            return false;
    return true;
}

Sprawa trochę się komplikuje, gdy chcemy mieć informację o części wspólnej obu zbiorów. Tu jednak z pomocą przychodzi Guava, która ma klasę narzędziową Sets, która znowuż zawiera metodę intersection:

Listing 3. Użycie Sets.intersection

public class SetsIntersectionExample {

	public static void main(String[] args) {
		// Smoki i gołe baby
		Fairy fairy = Fairy.create();

		Set<String> persons = Stream.generate(() -> fairy.person(PersonProperties.male())).limit(100)
				.map(Person::firstName)
				.collect(Collectors.toSet());
		// Magia, bo chcemy mieć pewność, że mamy istniejące imiona.
		Set<String> names = Sets.newHashSet((String) persons.toArray()[0], (String) persons.toArray()[1]);
		// end: Smoki i gołe baby

		System.out.println(persons);
		System.out.println(names);
		System.out.println(persons.containsAll(names));
		System.out.println(Sets.intersection(persons, names).size() == names.size()); // to samo co wyżej
		System.out.println(Sets.intersection(persons, names));
	}
}

Implementacja jest w tym przypadku podobna (taka sama złożoność), ale trochę bardziej skomplikowana, bo wynikiem jest SetView. Jedyny problem, jaki będzie tu nas drażnił, to duże zbiory danych. W takim wypadku wyszukiwanie części wspólnej będzie długotrwałe.

7 myśli na temat “Część wspólna zbiorów z Guavą

  1. używałem intersection z apache commons, implementacja wygląda podobnie i działało nawet szybko
    stackoverflow „mówi”, że można też tak:
    s1.retainAll(s2);

  2. @Piotr, tyle tylko, że Set.retainAll modyfikuje nam kolekcję, a tego bardzo byśmy nie chcieli.

  3. dzięki, tak myślałem, że jest jakiś haczyk ale nie miałem czasu zbadać temat 🙂

  4. A ja cały czas czekam na wpis o tym dlaczego farmy programistów to nie prawda…

  5. czemu uważasz że containsAll jest słabo zaimplementowane?

  6. @oklahoma kid, ponieważ porównywanie zbiorów jest wykonywane liniowo tzn. pętla w pętli. Można to zrobić lepiej na przykład konstruując nowy zbiór na bazie istniejących i korzystając z właściwości Set.add ustalić czy coś się zawiera. Można zacząć się bawić grafami izomorficznymi. Przy czym, wszystkie te rozwiązania są dość skomplikowane i zazwyczaj pamięciożerne.

Napisz odpowiedź

Twój adres email nie zostanie opublikowany. Pola, których wypełnienie jest wymagane, są oznaczone symbolem *

To create code blocks or other preformatted text, indent by four spaces:

    This will be displayed in a monospaced font. The first four 
    spaces will be stripped off, but all other whitespace
    will be preserved.
    
    Markdown is turned off in code blocks:
     [This is not a link](http://example.com)

To create not a block, but an inline code span, use backticks:

Here is some inline `code`.

For more help see http://daringfireball.net/projects/markdown/syntax