Rezumat Big-O pentru implementările Java Collections Framework? [închis] (Programare, Java, Colecții, Mare O)

Jared a intrebat.
a intrebat.

S-ar putea să predau în curând un „curs accelerat Java”. Deși este probabil sigur să presupunem că membrii audienței vor cunoaște notația Big-O, probabil că nu este sigur să presupunem că vor ști care este ordinea diferitelor operații pe diferite implementări de colecții.

Aș putea să-mi fac timp să generez eu însumi o matrice rezumativă, dar dacă aceasta există deja undeva în domeniul public, aș dori cu siguranță să o reutilizez (cu creditul corespunzător, bineînțeles).

Are cineva indicii?

Comentarii

  • Iată un link pe care l-am găsit util atunci când am discutat câteva obiecte Java foarte comune și cât costă operațiile lor folosind notația Big-O. objectissues.blogspot.com/2006/11/11/… –  > Por Nick.
  • Deși nu se află în domeniul public, excelenta lucrare Java Generics and Collections de Maurice Naftalin și Philip Wadler enumeră informații de ansamblu la execuție în capitolele sale despre diferitele clase de colecții. –  > Por Fabian Steeg.
  • Ar putea acest lucru benchmark de performanță ar fi de folos? –  > Por ThreaT.
4 răspunsuri
Ben J

Acest site este destul de bun, dar nu este specific pentru Java: http://bigocheatsheet.com/

Comentarii

    29

  • Și acesta este motivul pentru care nu folosim URL-uri ca răspunsuri. Acel document/server, din câte știu eu, nu mai este disponibil! –  > Por Jason Mock.
  • @Ben J Linkurile nu mai funcționează –  > Por Vikas V.
  • Legăturile către arhiva web sunt acum și ele defecte. –  > Por MikeFHay.
  • Se pare că au fost adăugate noi URL-uri de lucru. Vă mulțumim pentru că ați făcut acest efort, este foarte util. –  > Por Tejas C.
  • @AndreaZilio LinkedList.remove(Object) este în timp constant, presupunând că știți deja vecinul. Dacă nu cunoașteți vecinul, este timp liniar pentru a-l găsi mai întâi. –  > Por Paul Evans.
toolkit

Cartea Java Generics și colecții conține aceste informații (paginile: 188, 211, 222, 240).

Lista implementărilor:

                      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)

Implementări de seturi:

                      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)

Implementări de hărți:

                      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)

Implementări de coadă:

                      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)

În partea de jos a javadocului pentru java.util conține câteva linkuri bune:

Comentarii

  • Trebuie să specificați pentru ce scenariu de caz sunt aceste cifre, de exemplu, ștergerea din Arraylist ar putea dura O(n), dacă ștergeți elementul din mijlocul sau de la sfârșitul array-ului. –  > Por Popeye.
  • @popeye nu este O de obicei cel mai rău caz? –  > Por Yassin Hajaj.
  • Așa cum a menționat @Popeye, ar trebui să existe o descriere clară despre ce caz este vorba în răspuns. Cazul poate fi fie media/cel mai rău pentru complexitatea timpului. Se pare că răspunsul se referă la un caz „mediu” pentru toate DS. –  > Por Yashwin Munsadwala.
matt b

Javadocs de la Sun pentru fiecare clasă de colecție vă va spune, în general, exact ceea ce doriți. HashMap, , de exemplu:

Această implementare oferă performanță în timp constant pentru operațiile de bază (get și put), presupunând că funcția hash dispersează corect elementele între găleți. Iterarea peste vizualizările colecțiilor necesită un timp proporțional cu „capacitatea” instanței HashMap. (numărul de găleți) plus dimensiunea acesteia (numărul de corespondențe cheie-valoare).

TreeMap:

Această implementare oferă un cost garantat în timp log(n) pentru operațiile containsKey, get, put și remove.

TreeSet:

Această implementare oferă un cost garantat în timp log(n) pentru operațiunile de bază (add, remove și contains).

(sublinierea îmi aparține)

Comentarii

  • Nu sunt de acord cu partea referitoare la HashMap. Cunosc poziția lui Sun, dar… get, de exemplu, trebuie să apeleze obj.equals(key), ceea ce ar putea fi liniar în ceea ce privește dimensiunea obiectelor conținute. Luați în considerare faptul că, de obicei, trebuie să citiți câmpurile pentru această comparație. Excepțiile ar fi întregi sau șiruri de caractere (internalizate)???? –  > Por Supraexploatat.
  • În primul rând, dacă ar fi greșit, nu ar trebui să vă fie prea greu să creați un caz de testare care să infirme performanța în timp constant? În al doilea rând, dacă vă uitați la codul sursă pentru HashMap, acesta nu apelează equals() pentru fiecare cheie din hartă, ci doar atunci când codurile hash sunt egale. –  > Por matt b.
  • Dacă citiți citatul de mai sus, se spune că este în timp constant „presupunând că funcția hash dispersează corect elementele între găleți”. Din teoria CS, tabelele hash au operații în timp constant atunci când funcția hash este „bună” (ceea ce se întâmplă în medie), dar poate dura timp liniar în cel mai rău caz. –  > Por newacct.
  • @Overflown – din punct de vedere tehnic, nu contează cât timp durează obj.equals() din punct de vedere al complexității, deoarece aceasta este doar o parte a „constantei” în raport cu numărul de elemente din colecție. –  > Por mikera.
newacct

Tipul de mai sus a dat o comparație pentru HashMap / HashSet vs. TreeMap / TreeSet.

Eu voi vorbi despre ArrayList vs. LinkedList:

ArrayList:

  • O(1) get()
  • amortizat O(1) add()
  • dacă introduceți sau ștergeți un element în mijloc folosind ListIterator.add() sau Iterator.remove(), , va fi O(n) pentru a schimba toate elementele următoare

LinkedList:

  • O(n) get()
  • O(1) add()
  • dacă introduceți sau ștergeți un element în mijloc folosind ListIterator.add() sau Iterator.remove(), , va fi O(1)

Comentarii

  • if you insert or delete an element in the middle using ListIterator.add() or Iterator.remove(), it will be O(1) De ce? Mai întâi trebuie să găsim elementul din mijloc, deci de ce nu este O(n)? –  > Por MyTitle.
  • @MyTitle: citiți din nou. „folosind ListIterator.add() sau Iterator.remove()” Avem un iterator. –  > Por newacct.