Podsumowanie Big-O dla implementacji Java Collections Framework? [Zamknięte]

164

Być może wkrótce będę prowadzić „szybki kurs Java”. Chociaż prawdopodobnie można bezpiecznie założyć, że członkowie publiczności będą znali notację Big-O, prawdopodobnie nie jest bezpiecznie zakładać, że będą wiedzieć, jaka jest kolejność różnych operacji na różnych implementacjach kolekcji.

Mógłbym zająć trochę czasu, aby samodzielnie wygenerować macierz podsumowań, ale jeśli jest już gdzieś w domenie publicznej, na pewno chciałbym go ponownie wykorzystać (oczywiście z odpowiednim kredytem).

Czy ktoś ma jakieś wskazówki?

Jared
źródło
Oto link, który okazał się przydatny podczas omawiania niektórych bardzo popularnych obiektów Java i kosztów ich operacji przy użyciu notacji Big-O. objectissues.blogspot.com/2006/11/…
Nick
Chociaż nie są one własnością publiczną, doskonałe generyczne i kolekcje Java autorstwa Maurice'a Naftalina i Philipa Wadlera zawierają przeglądy informacji o środowisku wykonawczym w swoich rozdziałach na temat różnych klas kolekcji.
Fabian Steeg
1
Czy ten wzorzec wydajności byłby przydatny?
ZagroŻenie

Odpowiedzi:

149

Ta strona jest całkiem dobra, ale nie jest specyficzna dla Javy: http://bigocheatsheet.com/ Oto obraz na wypadek, gdyby ten link nie działał

Ben J.
źródło
27
Dlatego nie używamy adresów URL jako odpowiedzi. O ile wiem, ten dokument / serwer nie jest już dostępny!
Jason Mock
1
@Ben J Linki już nie działają
Vikas V
Linki do archiwów internetowych są teraz również uszkodzone.
MikeFHay
Wydaje się, że dodano nowe działające adresy URL. Dzięki za wysiłek, jest to bardzo pomocne.
Tejas C
1
@AndreaZilio LinkedList.remove (Object) to stały czas, zakładając, że znasz już sąsiada. Jeśli nie znasz sąsiada, czas na znalezienie go najpierw jest liniowy.
Paul Evans
217

W książce Java Generics and Collections znajdują się te informacje (strony: 188, 211, 222, 240).

Lista implementacji:

                      get  add  contains next remove(0) iterator.remove
ArrayList             O(1) O(1) O(n)     O(1) O(n)      O(n)
LinkedList            O(n) O(1) O(n)     O(1) O(1)      O(1)
CopyOnWrite-ArrayList O(1) O(n) O(n)     O(1) O(n)      O(n)

Zestaw realizacji:

                      add      contains next     notes
HashSet               O(1)     O(1)     O(h/n)   h is the table capacity
LinkedHashSet         O(1)     O(1)     O(1) 
CopyOnWriteArraySet   O(n)     O(n)     O(1) 
EnumSet               O(1)     O(1)     O(1) 
TreeSet               O(log n) O(log n) O(log n)
ConcurrentSkipListSet O(log n) O(log n) O(1)

Implementacje map:

                      get      containsKey next     Notes
HashMap               O(1)     O(1)        O(h/n)   h is the table capacity
LinkedHashMap         O(1)     O(1)        O(1) 
IdentityHashMap       O(1)     O(1)        O(h/n)   h is the table capacity 
EnumMap               O(1)     O(1)        O(1) 
TreeMap               O(log n) O(log n)    O(log n) 
ConcurrentHashMap     O(1)     O(1)        O(h/n)   h is the table capacity 
ConcurrentSkipListMap O(log n) O(log n)    O(1)

Implementacje kolejki:

                      offer    peek poll     size
PriorityQueue         O(log n) O(1) O(log n) O(1)
ConcurrentLinkedQueue O(1)     O(1) O(1)     O(n)
ArrayBlockingQueue    O(1)     O(1) O(1)     O(1)
LinkedBlockingQueue   O(1)     O(1) O(1)     O(1)
PriorityBlockingQueue O(log n) O(1) O(log n) O(1)
DelayQueue            O(log n) O(1) O(log n) O(1)
LinkedList            O(1)     O(1) O(1)     O(1)
ArrayDeque            O(1)     O(1) O(1)     O(1)
LinkedBlockingDeque   O(1)     O(1) O(1)     O(1)

W dolnej części javadoc pakietu java.util znajduje się kilka dobrych linków:

zestaw narzędzi
źródło
3
Musisz określić, dla którego scenariusza są te liczby, na przykład delete from Arraylist może zająć O (n), jeśli usuniesz element w środku lub na końcu tablicy.
Popeye,
@popeye nie jest zwykle najgorszym przypadkiem?
Yassin Hajaj
Jak wspomniał @Popeye, powinien być jasny opis tego, jakiego przypadku dotyczy odpowiedź. Przypadek może być średni / najgorszy pod względem złożoności czasowej. Wygląda na to, że odpowiedź odnosi się do „przeciętnego” przypadku dla wszystkich DS.
Yashwin Munsadwala
12

Dokumenty Javadocs firmy Sun dla każdej klasy kolekcji na ogół mówią dokładnie, czego chcesz. HashMap , na przykład:

Ta implementacja zapewnia stałą wydajność dla podstawowych operacji (pobierz i umieść), przy założeniu, że funkcja skrótu prawidłowo rozprasza elementy między zasobnikami. Iteracja po widokach kolekcji wymaga czasu proporcjonalnego do „pojemności” instancji HashMap (liczba segmentów) plus jej rozmiar (liczba mapowań klucz-wartość).

Mapa drzewa :

Ta implementacja zapewnia gwarantowany koszt czasu w dzienniku (n) dla operacji zawieraKey, pobieranie, wysyłanie i usuwanie.

TreeSet :

Ta implementacja zapewnia gwarantowany koszt log (n) czasu dla podstawowych operacji (dodawanie, usuwanie i zawiera).

(podkreślenie moje)

matowe b
źródło
Nie zgadzam się z częścią HashMap. Znam pozycję Słońca, ale ... na przykład get musi wywołać obj.equals (klucz), który może być liniowy względem rozmiaru zawartych obiektów. Weź pod uwagę, że zwykle musisz przeczytać pola do tego porównania. Wyjątkami byłyby liczby całkowite lub ciągi znaków (internowane) ???
Przeleciał
Po pierwsze, jeśli się mylili, to nie powinno być dla Ciebie zbyt trudne stworzenie przypadku testowego, który zaprzecza wydajności w czasie stałym? Po drugie, jeśli spojrzysz na kod źródłowy HashMap, nie wywoła on equals () dla każdego klucza w mapie - tylko wtedy, gdy hashcodes są równe.
mat b
5
Jeśli przeczytasz powyższy cytat, mówi on, że jest to stały czas „zakładając, że funkcja skrótu prawidłowo rozprasza elementy między zasobnikami”. Z teorii CS, tablice skrótów mają operacje na stałym czasie, gdy funkcja skrótu jest „dobra” (co zdarza się średnio), ale w najgorszym przypadku może zająć liniowy czas.
newacct
4
@Overflown - z technicznego punktu widzenia nie ma znaczenia, ile czasu zajmie obj.equals () z perspektywy złożoności, ponieważ jest to tylko część „stałej” w odniesieniu do liczby elementów w kolekcji.
mikera
6

Facet powyżej przedstawił porównanie HashMap / HashSet vs. TreeMap / TreeSet.

Porozmawiam o ArrayList vs. LinkedList:

ArrayList:

  • O (1) get()
  • amortyzowane O (1) add()
  • jeśli wstawisz lub usuniesz element w środku za pomocą ListIterator.add()lub Iterator.remove(), przesunięcie wszystkich kolejnych elementów będzie O (n)

Połączona lista:

  • Na) get()
  • O (1) add()
  • jeśli wstawisz lub usuniesz element w środku za pomocą ListIterator.add()lub Iterator.remove(), będzie to O (1)
newacct
źródło
1
if you insert or delete an element in the middle using ListIterator.add() or Iterator.remove(), it will be O(1) czemu? najpierw musimy znaleźć element pośrodku, więc dlaczego nie O (n)?
MyTitle
@MyTitle: przeczytaj ponownie. „using ListIterator.add()or Iterator.remove()” Mamy iterator.
newacct