Nieoczekiwana złożoność typowych metod (rozmiaru) w Java Collections Framework?

Question

Niedawno byłem zaskoczony faktem, że niektóre kolekcje Java nie mają stałej operacji czasowej metody size().

Gdy dowiedziałem się, że równoczesne implementacje kolekcji wykonane pewne kompromisy jako kompromis dla przyrostu współbieżności (rozmiar jest O (n) w ConcurrentLinkedQueue, ConcurrentSkipListSet, LinkedTransferQueue, etc.) Dobrą wiadomością jest to, że są właściwie udokumentowane w dokumentacji API .

Co mnie niepokoi, to wydajność rozmiaru metody na widokach zwróconych przez niektóre metody zbiorów. Na przykład TreeSet.tailSet zwraca widok części zestawu kopii, którego elementy są większe lub równe odElement. Bardzo mnie zaskoczyło to, że rozmiar wywołania przy zwrocie SortedSet jest liniowy w czasie, czyli O (n). Przynajmniej to, co udało mi się wygrzebać z kodu źródłowego OpenJDK: W TreeSet jest zaimplementowany jako owinięcia nad TreeMap, aw ciągu TreeMap istnieje klasa EntrySetView którego metoda wielkość jest w następujący sposób:

abstract class EntrySetView extends AbstractSet<Map.Entry<K,V>> { 
    private transient int size = -1, sizeModCount; 

    public int size() { 
     if (fromStart && toEnd) 
      return m.size(); 
     if (size == -1 || sizeModCount != m.modCount) { 
      sizeModCount = m.modCount; 
      size = 0; 
      Iterator i = iterator(); 
      while (i.hasNext()) { 
       size++; 
       i.next(); 
      } 
     } 
     return size; 
    } 

    .... 
} 

Oznacza to, że pierwszy rozmiar jest wywoływany to O (n), a następnie jest buforowany, o ile mapa podkładu nie jest modyfikowana. Nie mogłem znaleźć tego faktu w dokumentacji API. Bardziej wydajną implementacją byłby O (log n) z kompromisem pamięci w buforowaniu wielkości poddrzewa. Ponieważ takie kompromisy są podejmowane w celu uniknięcia powielania kodu (TreeSet jako wrapper na TreeMap), nie widzę powodu, dla którego nie powinny one być tworzone ze względu na wydajność.

Pomijając moje bycie dobrym lub złym z moją (bardzo krótką) analizą wdrożenia TreeSet w OpenJDK, chciałbym wiedzieć, czy istnieje szczegółowa i kompletna dokumentacja dotycząca wykonywania wielu takich operacji, w szczególności tych, które są całkowicie nieoczekiwane?

Answer 1

Na przykład TreeSet.tailSet zwraca widok części zestawu kopii, którego elementy są większe lub równe fromElement. Bardzo mnie zaskoczyło to, że wywołanie size po zwrocie SortedSet jest liniowe w czasie, czyli O(n).

Dla mnie to nie jest zaskakujące. Rozważmy to zdanie z javadoc: „Zwracany zestaw jest wspierany przez ten zestaw, więc zmiany w zwróconym zestawie znajdują odzwierciedlenie w tym zestawie, i vice versa”

Ponieważ zestaw tylny jest dynamicznym widokiem zestawu podkładowego, wynika z tego, że jego wielkość musi być obliczana dynamicznie w praktyce. Alternatywa wymagałaby, aby po wprowadzeniu zmiany w zestawie podkładowym konieczne było dostosowanie rozmiarów wszystkich istniejących widoków tailset (i zestawu słuchawkowego). To spowodowałoby, że aktualizacje zestawu kopii zapasowych byłyby droższe, i pojawiłby się problem zarządzania pamięcią masową. (Aby zaktualizować rozmiary widoku, zestaw podkładów będzie wymagał odniesień do wszystkich istniejących zestawów widoków ... i jest to potencjalny ukryty wyciek pamięci.)

Teraz masz punkt dotyczący dokumentacji. W rzeczywistości javadocs nie mówią nic o złożoności kolekcji widoków. I rzeczywiście, to nawet nie dokumentuje, że TreeSet.size() jest ! W rzeczywistości dokumentuje to jedynie złożoność operacji add, remove i i .

---

Chciałbym wiedzieć czy istnieje szczegółowa i kompletna dokumentacja na wykonanie wielu takich operacji, zwłaszcza te, które są całkowicie nieoczekiwany?

AFAIK, nr Oczywiście, nie od Sun/Oracle ...