Jaki jest skuteczny i elegancki sposób dodawania pojedynczego elementu do niezmiennego zestawu?

Question

Mam niezmienny zestaw (odlany jako Set<Integer>), który potencjalnie zawiera wiele elementów. Potrzebuję kolekcji zawierającej elementy z tego zestawu plus jeden dodatkowy element. Mam kludgy kod, aby skopiować zestaw, a następnie dołączyć element, ale szukam właściwego sposobu, który utrzymuje rzeczy tak wydajne, jak to możliwe.

Mam dostępną Guawę, ale nie wymagam jej użycia.

Answer 1

Nie wiesz, o wydajności, ale można użyć Guava na ImmutableSet.Builder:

import com.google.common.collect.ImmutableSet 

// ... 
Set<Integer> newSet = new ImmutableSet.Builder<Integer>() 
           .addAll(oldSet) 
           .add(3) 
           .build(); 

Oczywiście można również pisać własne metody pomocnika na to:

public static <T> Set<T> setWith(Set<T> old, T item) { 
    return new ImmutableSet.Builder<T>().addAll(old).add(item).build(); 
} 

// ... 
Set<Integer> newSet = setWith(oldSet, 3); 

Answer 2

Jeśli zestaw jest niezmienny, nie widzę innego sposobu niż kopiowanie zestawu, a następnie dodanie nowego elementu. Pamiętaj, że kopiowanie zestawu jest tak proste, jak przekazanie zestawu podstawowego do funkcji konstruktora podczas tworzenia nowego zestawu.

Answer 3

Doświadczyłem dysonansu poznawczego, gdy przeczytałem "niezmienny" i "dodaj do" w tym samym zdaniu. Możesz dodać nowy element na końcu zmiennej wartości niezmiennych, ale nie możesz modyfikować niezmiennego zestawu. Nie znam niczego eleganckiego.

Answer 4

masz trzy opcje.

• Użyj zestawu zmiennego.
• Sprawdź, czy element nie jest już obecny, jeśli nie, utwórz kopię zestawu i dodaj element.
• Utwórz zestaw otoki, który zawiera poprzedni zestaw i element.

Czasami BitSet jest lepszym wyborem niż Set<Integer> w zależności od rozkładu wartości.

Answer 5

Możesz wziąć pod uwagę Sets.union(). Budowa byłaby szybsza, ale wolniej.

public static <T> Set<T> setWith(Set<T> old, T item) { 
    return Sets.union(old, Collections.singleton(item); 
} 

(com.google.common.collect.Sets & java.util.Collections)

Answer 6

Gdy chcesz lepszą wydajność niż pełną kopię, a masz zamawianie nad elementami, można użyć skutecznie niezmienne opakowanie wokół B+ tree, aby uzyskać dobrą wydajność zestawu przyrostowego.

Dodanie elementu do drzewa B + wymaga czasu O (log (n)) i alokacji przyrostowej, a nie O (n), jak w przypadku ImmutableSet.builder().addAll(...).add(...).build(). Oznacza to, że budowanie zestawu z n przyrostowych rozszerzeń to O (n * log (n)), a nie O (sqr (n)).

Ten answer ma wskaźnik do biblioteki jdbm, więc warto przyjrzeć się jdbm:jdbm.