2009-10-02 11 views
37

Dlaczego jest list.size()>0 wolniejsza niż list.size()>0 wolniejsza niż list.isEmpty() w Javie? Innymi słowy, dlaczego isEmpty() jest lepsze niż size()>0?Dlaczego metoda list.size()> 0 jest wolniejsza od metody list.isEmpty() w języku Java?

Kiedy patrzę na wdrożenie w ArrayList, to wygląda prędkości powinny być takie same:

ArrayList.size()

/** 
    * Returns the number of elements in this list. 
    * 
    * @return the number of elements in this list 
    */ 
    public int size() { 
     return size; 
    } 

ArrayList.isEmpty()

/** 
    * Returns <tt>true</tt> if this list contains no elements. 
    * 
    * @return <tt>true</tt> if this list contains no elements 
    */ 
    public boolean isEmpty() { 
     return size == 0; 
    } 

Jeśli po prostu napiszemy prosty program, aby uzyskać czas obie metody, w tym przypadku size(), będą we wszystkich przypadkach wymagały więcej isEmpty(), dlaczego tak jest?

Oto mój kod testowy;

import java.util.List; 
import java.util.Vector; 

public class Main { 
    public static void main(String[] args) { 
     List l=new Vector(); 
     int i=0; 
     for(i=0;i<10000;i++){ 
      l.add(new Integer(i).toString()); 
     } 
     System.out.println(i); 
     Long sTime=System.nanoTime(); 
     l.size(); 
     Long eTime=System.nanoTime(); 
     l.isEmpty(); 
     Long eeTime=System.nanoTime(); 
     System.out.println(eTime-sTime); 
     System.out.println(eeTime-eTime); 
    } 
} 

Tutaj eTime-sTime>eeTime-eTime we wszystkich przypadkach. Czemu?

Odpowiedz

46

Twój kod testowy jest wadliwy.

Wystarczy odwrócić kolejność, tj. Zadzwonić najpierw isEmpty i rozmiar> 0 sekund, a otrzymasz z wynikiem. Wynika to z klasy załadunku, buforowanie itp

+1

@JLR: Tak, akceptuję twój punkt, Nie było wadą, jak testował obie metody w 2 osobnych projektach i oba dają bardzo podobny wynik. Thanx za usunięcie mojej wątpliwości –

1

Liczenie pozycji na liście połączonej może być bardzo wolne.

+0

@Spdenme: ale to się nie liczy, po prostu zwraca wartość? –

+0

W twoim przykładzie masz listę * ArrayList * –

+0

List jest interfejsem. Sposób implementacji wpływa na względną wydajność tych dwóch metod. Ponieważ size() jest często nazywaną metodą, większość implementacji decyduje o kosztach utrzymania pola wielkości. –

66

Dla ArrayList s, tak - masz rację, że operacje trwają (mniej więcej) w tym samym czasie.

Dla innych implementacji list - naiwne połączone listy *, na przykład - zliczanie rozmiaru może zająć bardzo dużo czasu, podczas gdy tylko faktycznie dbasz o to, czy jest większe od zera.

Więc jeśli absolutnie wiesz, że lista jest implementacją ArrayList i nigdy się nie zmieni, to nie ma to znaczenia; ale:

  1. to jest zła praktyka programistyczna, mimo wszystko, aby przywiązać się do konkretnej implementacji.
  2. Jeśli coś zmienić kilka lat w dół zgodnie z restrukturyzacji kodu, testowanie pokaże, że „to działa”, ale rzeczy są mniej efektywne niż przed
  3. Nawet w najlepszym przypadku, size() == 0 wciąż nie szybciej niż isEmpty() działa , więc nie ma żadnego ważnego powodu, aby kiedykolwiek użyć tego pierwszego.
  4. isEmpty to bardziej przejrzysta definicja tego, co naprawdę Cię interesuje i które testujesz, dzięki czemu Twój kod staje się bardziej zrozumiały.

(też bym zmienić wykorzystanie NULL w tytule pytanie, samo pytanie, a te operacje, nie mają nic wspólnego z tym, czy jakieś referencje obiektów są nieważne.)

* I Oryginalnie napisał on tutaj LinkedList, nieodwołalnie odwołując się do java.util.LinkedList, choć ta konkretna implementacja zachowuje wprost swoją długość, czyniąc tu wielkość() i operację O (1). Bardziej naiwna operacja na liście połączonej może tego nie robić, aw bardziej ogólnym sensie nie ma gwarancji wydajności implementacji List.

+5

"the" 'LinkedList' (a.k.a' java.util.LinkedList') również przechowuje swój rozmiar, więc wywołanie 'size()' jest równie szybkie jak w przypadku 'ArrayList', ale ogólny punkt jest nadal bardzo ważny. –

+0

@dtszzs: Czas wykonywania nie jest taki sam, to jest to, co przetestowałem i po prostu sprawiasz, że czuję się niekomfortowo. –

+4

@Sam Rudolph: jak to przetestowałeś? Istnieją tysiące sposobów na złapanie takich mikrobieńek. –

2

Biorąc pod uwagę te dwie implementacje, prędkość powinna być taka sama, tyle jest prawdą.

Ale to zdecydowanie nie jedyne możliwe implementacje tych metod. Pierwotnie połączona lista (ta, która nie przechowuje rozmiaru osobno) może na przykład odpowiadać isEmpty() znacznie szybciej niż wywołanie size().

Co więcej: isEmpty() dokładnie opisuje twoje intencje, podczas gdy size()==0 jest niepotrzebnie skomplikowane (nie jest to oczywiście bardzo skomplikowane, ale należy unikać niepotrzebnej złożoności).

+0

but6 jeśli widzisz implementację, wygląda to bardzo prosto? –

+0

Te, na które patrzysz, tak. Ale jak @dtsazza wyjaśnił całkiem dobrze: implementacja nie jest jedyną ważną rzeczą, intencja i czytelność są również ważne. I mogą istnieć inne implementacje Collectons, w których 'size()' może nie zostać tak łatwo zaimplementowane ('WeakHashMap' lub inne kolekcje dynamiczne). –

5

Mówiłeś:

Tutaj eTime-sTime>eeTime-eTime we wszystkich przypadkach, dlaczego?

Po pierwsze, prawdopodobnie wynika to z kodu testowego. Nie można przetestować prędkości wywoływania funkcji l.size() i l.isEmpty() w tym samym czasie, ponieważ oba wywołują tę samą wartość. Najprawdopodobniej wywołanie l.size() spowodowało załadowanie rozmiaru twojej listy do pamięci podręcznej cpu i wywołanie l.isEmpty() jest o wiele szybsze.

Można spróbować nazywając l.size() kilka milion razy i l.isEmpty() kilka razy w milion dwa oddzielne programy ale w teorii kompilator może po prostu optymalizacji precz wszystkie te połączenia skoro” właściwie nic nie robię z wynikami.

W każdym przypadku różnica w wydajności między nimi będzie niewielka, szczególnie po wykonaniu porównania, które należy wykonać, aby sprawdzić, czy lista jest pusta (l.size() == 0). Najprawdopodobniej wygenerowany kod będzie wyglądał prawie całkowicie podobnie. Jak zauważyły ​​inne plakaty, w tym przypadku chcesz zoptymalizować pod kątem czytelności, a nie prędkości.

edytuj: Testowałem to sam. To trochę podrzucanie. size() i isEmpty() użyte na Vector dały różne wyniki na długich trasach, ani nie pokonały innych konsekwentnie. Po uruchomieniu na ArrayListsize() wydawało się szybciej, ale nie za dużo. Jest to najprawdopodobniej spowodowane faktem, że dostęp do Vector jest zsynchronizowany, więc to, co naprawdę widzisz podczas testowania dostępu do tych metod, to obciążenie synchronizacyjne, które może być bardzo wrażliwe.

Rzeczą, którą należy tutaj zabrać, jest to, że gdy próbujesz zoptymalizować wywołanie metody z kilkoma nanosekundami różnicy w czasie wykonywania, to jesteś robi to źle. Zdobądź podstawy od razu, na przykład za pomocą Long s, gdzie powinieneś używać long.

+0

no tak po prostu nie uruchomiłem dwóch przypadków w osobnych programach tylko po to, aby usunąć wątpliwości i wynik jest tej samej wielkości() zajmuje 10 razy więcej czasu pracy niż isEmpty() –

0

Nie można ogólnie powiedzieć, która jest szybsza, ponieważ zależy to od tego, jakiej wersji interfejsu używa użytkownik.

Załóżmy, że mówimy o ArrayList. Wyszukaj kod źródłowy ArrayList, możesz go znaleźć w pliku src.zip w katalogu instalacyjnym JDK. Kod źródłowy metod isEmpty i size wygląda następująco (Sun JDK 1.6 aktualizacji 16 dla Windows):

public boolean isEmpty() { 
    return size == 0; 
} 

public int size() { 
    return size; 
} 

Można łatwo zauważyć, że oba wyrażenia isEmpty() i size() == 0 zejdą do dokładnie tych samych stwierdzeń, więc jeden z pewnością nie jest szybszy od drugiego.

Jeśli chcesz dowiedzieć się, jak to działa w przypadku innych implementacji interfejsu List, sprawdź sam kod źródłowy i dowiedz się.

1

Zgodnie z PMD (analizator kodu źródłowego Java oparty na regułach statycznych) preferowane jest isEmpty(). Zestaw reguł PMD można znaleźć tutaj. Wyszukaj regułę "UseCollectionIsEmpty".

http://pmd.sourceforge.net/rules/design.html

Według mnie to również pomaga w utrzymaniu cały kod źródłowy spójne raczej niż połowa ludzi korzystających isEmpty(), a resztę przy użyciu formatu() == 0.

2

.size() musi patrzeć na całą listę, a .isEmpty() może zatrzymać się na pierwszej.

Oczywiście zależne od wdrożenia, ale jak już powiedziano wcześniej, jeśli nie musisz znać faktycznego rozmiaru, po co licząc wszystkie elementy?

Powiązane problemy