2009-10-02 18 views
37

Warum ist list.size()>0 langsamer als list.isEmpty() in Java? Mit anderen Worten, warum isEmpty() gegenüber size()>0 vorzuziehen ist? Warum ist list.size()> 0 langsamer als list.isEmpty() in Java?

Als ich bei der Umsetzung aussehen in ArrayList, dann sieht es aus wie die Geschwindigkeit sollte das gleiche:

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; 
    } 

Wenn wir nur ein einfaches Programm schreiben, um die Zeit zu nehmen b y beide Methoden, dieser Fall size() wird in allen Fällen mehr isEmpty() dauern, warum das so?

Hier ist mein TestCode;

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); 
    } 
} 

Hier eTime-sTime>eeTime-eTime in allen Fällen. Warum?

Antwort

46

Ihr Testcode ist fehlerhaft.

Umkehren Sie einfach die Reihenfolge, d. H. Aufruf isEmpty zuerst und Größe> 0 Sekunde und Sie erhalten das gegenüber Ergebnis. Dies liegt an Klassenladen, Caching usw.

+1

@JLR: Ja, ich akzeptiere Ihren Punkt, gab es Fehler, als testeten beide Methoden in 2 separaten Projekten und beide geben sehr ähnliche Ergebnisse. Danke für die Beseitigung meiner Zweifel –

1

Das Zählen von Elementen in einer verknüpften Liste kann sehr langsam sein.

+0

@spdenme: aber es zählt nicht, es gibt nur einen Wert zurück? –

+0

In Ihrem Beispiel haben Sie eine * ArrayList * –

+0

Liste ist eine Schnittstelle. Wie es implementiert wird, wirkt sich auf die relative Leistung dieser beiden Methoden aus. Da size() eine häufig verwendete Methode ist, entscheiden die meisten Implementierungen, dass sich die Kosten für die Pflege eines Größenfelds lohnen. –

66

Für ArrayList s, ja - Sie haben Recht, dass die Operationen (ungefähr) die gleiche Zeit dauern.

Für andere Implementierungen von List-naive Linked Lists * zum Beispiel - das Zählen der Größe könnte sehr lange dauern, während es Ihnen eigentlich nur egal ist, ob es größer als Null ist.

Also, wenn Sie absolut wissen, dass die Liste eine Implementierung von ArrayList ist und sich nie ändern wird, dann ist es nicht wirklich wichtig; aber:

  1. das ist schlechte Programmierpraxis sowieso, um sich zu einer bestimmten Implementierung zu binden.
  2. Wenn es ein paar Jahre nach der Zeile mit Code Umstrukturierung ändern, werden Tests zeigen, dass „es funktioniert“, aber die Dinge laufen weniger effizient als vor
  3. Selbst im besten Fall size() == 0 ist noch nicht schneller als isEmpty() Es gibt also keinen zwingenden Grund, den ersteren zu benutzen.
  4. isEmpty ist eine klarere Definition dessen, was Sie eigentlich interessieren und testen, und macht so Ihren Code ein bisschen leichter verständlich.

(Auch würde ich die Verwendung von NULL in Frage Titel revidieren, die Frage selbst, und diese Vorgänge, nichts mit dem zu tun haben, ob Objektreferenzen sind null.)

* I ursprünglich geschrieben LinkedList hier, implizit auf java.util.LinkedList verweisen, obwohl diese bestimmte Implementierung speichert seine Länge explizit, so dass Größe() eine O (1) Operation hier. Eine eher naive Linked-List-Operation könnte dies nicht tun, und im allgemeineren Sinne gibt es keine Effizienzgarantie für Implementierungen von List.

+5

"Die" LinkedList "(a.k.a' java.util.LinkedList') speichert auch ihre Größe, so dass der 'size()' Aufruf genauso schnell ist wie für 'ArrayList', aber der allgemeine Punkt ist immer noch sehr gültig. –

+0

@dtszzs: Die Laufzeit ist nicht gleich, das ist was ich getestet habe und mich nur unangenehm machen .. –

+4

@Sam Rudolph: Wie hast du es getestet? Es gibt Tausende von Möglichkeiten, solche Microbenchmarks falsch zu machen. –

2

Angesichts dieser beiden Implementierungen sollte die Geschwindigkeit die gleiche sein, das stimmt.

Aber das sind bei weitem nicht die einzigen möglichen Implementierungen für diese Methoden. Eine primitive verkettete Liste (eine, die die Größe nicht separat speichert) könnte beispielsweise isEmpty() viel schneller antworten als ein size() Aufruf.

Noch wichtiger: isEmpty() beschreibt Ihre Absicht genau, während size()==0 ist unnötig komplex (nicht sehr komplex natürlich, aber jede unnötige Komplexität sollte vermieden werden).

+0

but6 wenn du dort die Implementierung siehst, sieht das sehr sehr einfach aus? –

+0

Die, die du dir ansiehst, ja. Aber wie @dtsazza es gut erklärt: Implementierung ist nicht das einzige Wichtige, Absicht und Lesbarkeit sind ebenfalls wichtig. Und es könnte andere Collectons-Implementierungen geben, bei denen 'size()' möglicherweise nicht so einfach implementiert wird ('WeakHashMap' oder andere dynamische Sammlungen). –

5

Sie sagte:

Hier eTime-sTime>eeTime-eTime in allen Fällen Warum?

Zunächst ist es wahrscheinlich wegen Ihres Testcodes. Sie können die Geschwindigkeit des Aufrufs von l.size() und l.isEmpty() nicht gleichzeitig testen, da beide den gleichen Wert abfragen. Wahrscheinlich hat das Aufrufen von l.size() die Größe Ihrer Liste in Ihren CPU-Cache geladen, und der Aufruf von l.isEmpty() ist viel schneller.

Sie versuchen l.size nennen könnte() ein paar Millionen Mal und l.isEmpty() ein paar Millionen Mal in zwei getrennte Programme aber der Compiler in der Theorie nur, da Sie alle diese Anrufe optimieren könnten weg‘ re nicht wirklich etwas mit den Ergebnissen.

In jedem Fall ist der Leistungsunterschied zwischen den beiden vernachlässigbar, besonders wenn Sie den Vergleich durchführen, um zu sehen, ob die Liste leer ist (l.size() == 0). Wahrscheinlich wird der generierte Code fast vollständig ähnlich aussehen. Wie einige andere Poster angemerkt haben, möchten Sie in diesem Fall die Lesbarkeit optimieren, nicht die Geschwindigkeit.

edit: Ich habe es selbst getestet. Es ist so ziemlich ein Toss-Up. size() und isEmpty() verwendet auf Vector gab unterschiedliche Ergebnisse auf lange Läufe, weder schlagen die anderen konsequent. Bei laufendem ArrayListsize() schien schneller, aber nicht viel. Dies liegt wahrscheinlich an der Tatsache, dass der Zugriff auf Vector synchronisiert ist. Was Sie wirklich sehen, wenn Sie versuchen, den Zugriff auf diese Methoden zu vergleichen, ist der Synchronisationsoverhead, der sehr empfindlich sein kann.

Die Sache hier wegzunehmen ist, dass, wenn Sie versuchen, einen Methodenaufruf mit ein paar Nanosekunden Unterschied in der Ausführungszeit zu optimieren, dann sind Sie es falsch machen. Holen Sie zuerst die Grundlagen richtig, wie zum Beispiel Long s, wo Sie long verwenden sollten.

+0

nein eigentlich nur nicht ich lief die beiden Fälle in separaten Programmen, nur um die Zweifel zu löschen und das Ergebnis ist die gleiche Größe() dauert 10 Mal mehr Laufzeit als isEmpty() –

15

Es tut mir leid, aber Ihre Benchmark ist fehlerhaft. Sehen Sie sich Java theory and practice: Anatomy of a flawed microbenchmark für eine allgemeine Beschreibung an, wie Sie Benchmarks angehen können.


aktualisieren: für eine angemessene Benchmark sollten Sie in Japex aussehen.

+0

Java.net scheint im Moment zu sein. –

0

Es ist unmöglich zu sagen, was im Allgemeinen schneller ist, weil es davon abhängt, welche Implementierung der Schnittstelle List Sie verwenden.

Angenommen, wir sprechen über ArrayList. Suchen Sie den Quellcode von ArrayList, Sie finden es in der Datei src.zip in Ihrem JDK-Installationsverzeichnis. Der Quellcode der Methoden isEmpty und size sieht wie folgt aus (Sun JDK 1.6 Update 16 für Windows):

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

public int size() { 
    return size; 
} 

können Sie leicht erkennen, dass beide Ausdrücke isEmpty() und size() == 0 werden die gleichen Aussagen genau kommen, so ein ist sicherlich nicht schneller als die andere.

Wenn Sie daran interessiert sind, wie es für andere Implementierungen der Schnittstelle List funktioniert, suchen Sie den Quellcode selbst und finden Sie es heraus.

1

Gemäß PMD (statischer Regelsatz basiert Java Source Code Analyzer) ist isEmpty() bevorzugt. Sie finden den PMD-Regelsatz hier. Suchen Sie nach der Regel "UseCollectionIsEmpty".

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

Nach mir, es hilft auch, den gesamten Quellcode konsistent eher als die Hälfte der Leute zu halten isEmpty() verwenden und den Rest Größe mit() == 0.

2

.size() muss sich die gesamte Liste ansehen, während .isEmpty() bei der ersten anhalten kann.

Offensichtlich Implementierung abhängig, aber wie bereits gesagt wurde, wenn Sie nicht die tatsächliche Größe wissen müssen, warum die Mühe, alle Elemente zu zählen?

Verwandte Themen