Która jest bardziej efektywne: using removeAll() lub stosując następującą technikę HashMap tylko zachować zmienione zapisy w ArrayList

Question

Mam 2 ArrayList s A i B tego samego datastructure C (hashCode() i equals() przesłonięta). C oznacza zapis studenta. Obie listy mają ten sam rozmiar i reprezentują odpowiednio nowe rekordy uczniów i stare (uczniowie są tacy sami na obu listach, kolejność może być inna). Chcę zachować tylko te zapisy w A, które zostały zmienione. Jako takie, robię:

A.removeAll(B) 

Jak na Javadocs, byłoby wziąć każdy zapis i porównać z każdego rekordu z B, a jeżeli stwierdzi, oba równe, to będzie usunąć rekord z A. Jeśli nie stwierdzono, że rekord A jest równy dowolnemu rekordowi w B, a ponieważ wszyscy uczniowie w A są również w B, oznacza to, że ten rekord A zmienił się. Problem polega na tym, że łatwo można złożyć n kwadratową złożoność.

Innym rozwiązaniem może być:

Map<C> map = new HashMap<C>(); 
for (C record : B){ 
    map.add(record.getStudentId(),record); 
} 
List<C> changedRecords = new ArrayList<C>(); 
for (C record : A){ 
    if (record.equals(map.get(record.getStudentId())){ 
     changedRecords.add(record); 
    } 
} 

myślę, że to może być o mniejszej złożoności niż powyższe rozwiązania. Czy to jest poprawne ?

Answer 1

Tak drugi algorytm jest lepszy niż O(n^2), ponieważ masz dwie pętle, jedna począwszy nad B a drugi nad A a ty (amortyzacji) stałą pracę w każdej pętli, nowe rozwiązanie działa w O(|A| + |B|).

Podejrzewam, że nie masz żadnych duplikatów. Jeśli jest to przypadek, można również przejść przez HashSet (zmiana do LinkedHashSet jeśli chcesz zachować porządek w A):

HashSet<C> tmp = new HashSet<C>(A); 
tmp.removeAll(B);      // Linear operation 
A = new ArrayList<C>(tmp); 

(Lub jeśli kolejność nie ma znaczenia dla Ciebie, można użyć HashSet s przez całą drogę).

---

Jak podkreślił @Daud w komentarzach poniżej, HashSet.removeAll(Collection c) faktycznie nazywa c.contains wielokrotnie jeśli rozmiar zestawu hash jest mniejszy niż gromadzenie co wpływa na złożoność (przynajmniej w OpenJDK). Dzieje się tak, ponieważ implementacja zawsze wybiera iterację w mniejszej kolekcji.

Answer 2

To, co możesz zaoszczędzić na złożoności, które możesz tracić w alokacji pamięci, więc niekoniecznie jest bardziej wydajne. Arrraylist używa czegoś podobnego do algorytmu partycjonowania w miejscu, aby sprowadzić tablicę backing i przetestować porównanie.

Podczas porównywania po prostu szuka indeksu pierwszego wystąpienia dopasowania w stosunku do tablicy pomocniczej Object[]. Algorytm utrzymuje dwa indeksy, jeden do iteracji przez tablicę backing i jeden jako symbol zastępczy dla dopasowań. W przypadku dopasowania po prostu przesuwa indeks w tablicy podkładu i przenosi do następnego przychodzącego elementu; to jest stosunkowo tanie.

Jeśli chodzi o punkt, w którym stwierdza, że ​​kolekcja przychodząca nie zawiera wartości w bieżącym indeksie w tablicy, po prostu zastępuje element, w którym ostatnie dopasowanie wystąpiło z elementem w bieżącym indeksie bez ponoszenia nowa alokacja pamięci. Ten wzorzec powtarza się, dopóki wszystkie elementy z tablicy ArrayList nie zostaną porównane z przychodzącą kolekcją, a więc złożoność, o którą się martwisz.

Na przykład: Rozważmy listę tablic A z 1,2,4,5 i kolekcję "C" z 4,1, które porównujemy; chce usunąć 4 i 1. W tym przypadku jest po każdej iteracji pętli, które przejść 0 -> 4

iteracji: R jest pętli indeks ArrayList do for (; r < size; r++)

r = 0 (sposób C zawiera 1 ? Tak, przejdź do następnego) A: 1,2,4,5 w = 0

r = 1 (Czy C zawiera 2? Nie, skopiuj wartość r w miejscu wskazywanym przez w ++) A: 2,2,4,5 W = 1

R = 2 (sposób C zawiera cztery ?, Tak pominąć) A: 2,2,4,5 W = 1

r = 3 (Czy C zawiera 5? Nie, skopiuj wartość przy R w miejscu wskazywanym przez w ++)

A: 2,5,4,5 w = 2

r = 4, przystanek

Porównaj wag do wielkości tablica podkładowa, która wynosi 4. Ponieważ nie są one równe Null out wartości od w na koniec tablicy i zresetować rozmiar.

A: 2,5 Wielkość 2

wbudowanego removeAll uważa również, że ArrayLists może zawierać wartość null. Możesz rzucić NPE na record.getStudentId() w powyższym rozwiązaniu. Wreszcie, removeAll chroni przed wyjątkami w porównaniu na Collection.contains. jeśli tak się stanie, w końcu używa natywnej memcopy, która chroni matrycę przed korupcją w wysoce efektywny sposób.

Answer 3

Zdecydowanie drugi "algorytm" jest lepszy od pierwszego przy analizie amortyzowanej. czy to najlepszy sposób? czy tego potrzebujesz? czy spowoduje to widoczny wpływ na użytkownika pod względem wydajności? czy liczba pozycji na liście rośnie tak ogromnie, że staje się to wąskim gardłem w systemie?

Pierwsze podejście jest bardziej czytelne, przekazuje zamiar osobom, które utrzymują kod. Zaleca się również używanie "przetestowanego" API zamiast ponownego wynajdowania koła (chyba, że ​​jest to absolutnie konieczne). Komputery stały się tak szybkie, że nie powinniśmy dokonywać żadnych przedwczesnych optymalizacji.

jeśli widać istotne mogę iść z roztworu stosując zestaw podobny do użytkownika @ Aioob

Answer 4

ja spotkałem się wąskim gardłem wydajności w państwach removeAll w niektórych przypadkach (EMF modelu manipulacji pokrewne). Dla ArrayList jak wspomniano powyżej, po prostu użyj standardowego removeAll, ale jeśli A jest na przykład EList, n^2 można napotkać.

W związku z tym unikaj polegania na ukrytych dobrych właściwościach określonych implementacji List < T>; Set.contains() O (1) to gwarancja, użyj go do związanej złożoności algorytmicznej.

Używam następującego kodu, który unika niepotrzebnych kopii; intencją jest to, że skanujesz strukturę danych znajdując nieistotne elementy, których nie chcesz i dodając je do "todel".

Z jakiegoś powodu, takiego jak unikanie jednoczesnych modyfikacji, nawigowanie po drzewie itp. ... nie można usuwać elementów podczas wykonywania tego przejścia. Więc kumulujemy je w "todel" HashSet.

W funkcji musimy zmodyfikować "kontener", ponieważ jest to zazwyczaj atrybut osoby dzwoniącej, ale użycie polecenia remove (indeks int) w "kontenerze" może wywołać kopię z powodu przesunięcia elementów w lewo. Używamy kopii "zawartości", aby to osiągnąć.

Argument szablonu jest taki, że podczas procesu selekcji często dostaję podtypy C, ale nie krępuj się używać wszędzie: < T>.

/** 
* Efficient O (n) operation to removeAll from an aggregation. 
* @param container a container for a set of elements (no duplicates), some of which we want to get rid of 
* @param todel some elements to remove, typically stored in a HashSet. 
*/ 
public static <T> void removeAll (List<T> container, Set<? extends T> todel) { 
    if (todel.isEmpty()) 
     return; 
    List<T> contents = new ArrayList<T>(container); 
    container.clear(); 
    // since container contains no duplicates ensure |B| max contains() operations 
    int torem = todel.size(); 
    for (T elt : contents) { 
     if (torem==0 || ! todel.contains(elt)) { 
      container.add(elt); 
     } else { 
      torem--; 
     } 
    } 
} 

Więc w twoim przypadku będzie wywołać z: removeAll (A, nowy Hashset < C> (b)); płacąc jedną kopię B, jeśli naprawdę nie można zgromadzić w zestawie < C> podczas fazy wyboru.

Umieść go w klasie narzędziowej i importuj statycznie, aby ułatwić obsługę.