Ich habe herumalbern mit einer Reihe von verschiedenen Möglichkeiten der Suche nach Sammlungen, Sammlungen von Sammlungen, etc. Doing viele dumme kleine Tests, um mein Verständnis zu verifizieren. Hier ist eine, die mich überschwemmt (Quellcode weiter unten).
Kurz gesagt, erzeuge ich N zufällige Ganzzahlen und füge sie zu einer Liste hinzu. Die Liste ist NICHT sortiert. Ich verwende dann Collections.contains() , um nach einem Wert in der Liste zu suchen. Ich suche absichtlich nach einem Wert, von dem ich weiß, dass er nicht da sein wird, weil ich sicherstellen möchte, dass der gesamte Listenbereich geprüft wird. Ich zeitlich diese Suche.
Ich mache dann eine weitere lineare Suche manuell, indem ich jedes Element der Liste durchlaufe und überprüfe, ob es mit meinem Ziel übereinstimmt. Ich zeitlich auch diese Suche.
Im Durchschnitt dauert die zweite Suche 33% länger als die erste. Nach meiner Logik muss die erste Suche auch linear sein, da die Liste unsortiert ist. Die einzige Möglichkeit, die mir einfiel (die ich sofort verwerfe), ist, dass Java eine sortierte Kopie meiner Liste nur für die Suche erstellt, aber (1) ich habe diese Nutzung von Speicherplatz nicht autorisiert und (2) würde ich das denken würde mit einem so großen N viel mehr Zeit sparen.
Wenn also beide Suchen linear sind, sollten sie beide die gleiche Zeit benötigen. Irgendwie hat der Collections-Kurs diese Suche optimiert, aber ich kann nicht herausfinden, wie. Also ... was fehlt mir?
%Vor% EDIT: Unten ist eine neue Version dieses Codes. Das Interessante daran ist, dass meine manuelle lineare Schleife jetzt 16% schneller als die contains -Methode ausführt (HINWEIS: beide sind so konzipiert, dass sie absichtlich den gesamten Listenraum durchsuchen, also weiß ich, dass sie gleich sind Iterationen). Ich kann diesen 16% igen Gewinn nicht erklären ... mehr Verwirrung.
Ihr Vergleichscode ist fehlerhaft und verzerrt Ihre Ergebnisse.
Dies sucht nach dem target
Aber das geht nicht!
%Vor%Sie durchlaufen gerade die Listenelemente, ohne sie zu testen.
Nachdem dies gesagt wurde, ist die zweite Version aus einem oder mehreren der folgenden Gründe langsamer als die erste Version:
Die erste Version wird das Backing-Array mit einer einfachen for -Schleife und einem Index durchlaufen. Die zweite Version entspricht der folgenden:
Mit anderen Worten beinhaltet jedes Umlaufen der Schleife 2 Methodenaufrufe und eine Typumwandlung 1 .
Die erste Version gibt true zurück, sobald eine Übereinstimmung gefunden wird. Aufgrund des Fehlers in Ihrer Implementierung wird die zweite Version jedes Mal die gesamte Liste durchlaufen. In der Tat ist dieser Effekt angesichts der Wahl von N und high am wahrscheinlichsten der Hauptgrund für den Leistungsunterschied.
1 - Eigentlich ist nicht ganz klar, was der JIT-Compiler mit all dem machen wird. Es könnte in der Theorie die Methodenaufrufe inline, folgern, dass das typcaset unnötig ist, oder sogar die gesamte Schleife weg optimieren. Auf der anderen Seite gibt es Faktoren, die diese Optimierungen verhindern können. Zum Beispiel wird ints als List<Integer> deklariert, was das Inlining verhindern könnte, es sei denn, das JIT kann daraus ableiten, dass der tatsächliche Typ immer derselbe ist.
Ihre Ergebnisse sind möglicherweise auch aus einem anderen Grund verzerrt. Ihr Code berücksichtigt JVM-Warmup nicht. Lesen Sie diese Frage für weitere Details: Wie schreibe ich ein korrekte Mikro-Benchmark in Java?
Hier ist der Unterschied:
Wenn Sie contains verwenden, verwendet es das interne Array des Objekts und führt eine Suche wie folgt aus:
Wenn es versucht, das Element ith zu erhalten, ruft es direkt das i-te Element-Objekt aus dem internen Array ab.
Wenn Sie Ihre eigene schreiben, schreiben Sie wie folgt:
%Vor%entspricht:
%Vor% Dies ist viel mehr Schritte als die contains .
Ich bin mir also nicht ganz sicher, ob Sie irgendetwas testen. Javac (Compiler) ist intelligent genug, um zu erkennen, dass Sie keinen Code innerhalb Ihrer for-Schleife und Ihrer if-Anweisung haben. In diesem Fall wird Java diesen Code aus seiner Kompilierung entfernen. Der Grund, warum Sie Zeit zurück bekommen, ist, weil Sie tatsächlich die Zeit zählen, die es dauert, um eine Zeichenfolge zu drucken. Die Systemausgabezeit kann je nach System stark variieren. Beim Schreiben von Timing-Tests kann jede E / A ungültige Tests erstellen.
Zuerst würde ich die Saitenabdrücke aus Ihrem Timing entfernen.
Zweitens ist ArrayList.contains linear. Es verwendet nicht die spezielle for-Schleife, wie Sie es tun. Ihre Schleife hat einen gewissen Overhead, um den Iterator aus der Sammlung zu holen und dann darüber zu iterieren. So funktioniert die spezielle for-Schleife hinter den Kulissen.
Hoffe, das hilft.
Tags und Links java collections linear-search