Kann es einen Algorithmus geben, der schneller ist als die lineare Suche?

Es ist durchaus möglich, dass Ihre search() -Methoden nichts zurückgeben und in den Schleifen keine Aktion stattfindet. JIT-Compiler in Ihrer JVM optimiert den Code - mit anderen Worten, ändert den Byte-Code, bevor er in JVM geladen wird, so dass sowohl Ihre search() Methoden machen wahrscheinlich (fast) nichts . Was am wichtigsten ist, entfernt wahrscheinlich auch die Schleifen vollständig. Die JIT-Optimierung ist ziemlich schlau, sie kann viele Situationen identifizieren, in denen kein Code in JVM geladen werden muss (der Code ist jedoch in der bytecode .class -Datei).

Dann messen Sie nur Zufallszahlen - nicht die Komplexität Ihrer Methoden in Echtzeit.

Lesen Sie z.B. um sicherzustellen, dass keine JVM- und Compiler-Optimierung auftritt , wenden Sie sie an und führen Sie den Benchmark erneut aus.

Ändern Sie auch Ihre search() -Methoden, so dass sie den Index zurückgeben - wodurch das Leben für den Optimierer schwieriger wird. Manchmal ist es jedoch überraschend schwierig, einen Code zu erstellen, der nicht optimiert werden kann. Das Abschalten der Optimierung (wie oben im Link) ist zuverlässiger.

Im Allgemeinen macht es keinen Sinn, nicht optimierten Code zu benchmarken. In diesem Fall möchte das OP jedoch einen theoretischen Algorithmus messen. Er möchte die tatsächliche Anzahl der Durchgänge messen. Er muss sicherstellen, dass die Schleifen tatsächlich ausgeführt werden. Deshalb sollte er die Optimierung ausschalten.

Der OP dachte, dass er die Geschwindigkeit des Algorithmus gemessen habe, während der Algorithmus überhaupt keine Chance hatte, überhaupt zu laufen. Wenn Sie die JIT-Optimierung in diesem speziellen Fall deaktivieren, wird der Benchmark korrigiert.

Darum geht es uns nicht darum, im wahrsten Sinne des Wortes zu bestimmen, wie lange die Dinge dauern und wie die Dinge wachsen, wenn die Komplexität der Eingaben zunimmt. Sehen Sie sich die asymptotische Laufzeitanalyse an:

Ссылка

Was ist die Statistik von value ? Höchstwahrscheinlich sind es sogar Werte in Ihrem Fall. Es ist ziemlich klar, dass für beide Fälle die Komplexität des Algorithmus O(n) und O(n/2) + O(n/2) ziemlich gleich ist - lineare Zeit

Es ist nur zufällig, dass es "schneller" ist. Was Sie wahrscheinlich bemerken, ist, dass Ihre Werte häufiger auf einem geraden Index als auf einem ungeraden Index erscheinen.

Theoretisch ist die zeitliche Komplexität beider Algorithmen gleich O(n) . Eine Spekulation, warum skipSearch beim Ausführen schneller war, ist, dass das Element, nach dem Sie gesucht haben, zufällig in einem geraden Index liegt. Daher wird es von der ersten Schleife gefunden und würde im schlimmsten Fall die Hälfte der Iterationen ausführen von linearSearch. In Benchmarks wie diesen müssen Sie nicht nur die Größe der Daten berücksichtigen, sondern auch wie die Daten aussehen. Versuchen Sie, nach einem Element zu suchen, das nicht existiert, einem Element, das an einem geraden Index existiert, einem Element, das an einem ungeraden Index existiert.

Auch wenn skipSearch bessere Ergebnisse mit geeigneten Benchmarks erzielt, werden nur einige Nanosekunden abgespeckt, so dass es keinen signifikanten Anstieg gibt und es sich in der Praxis nicht lohnt.

Eines der von jemandem erwähnten Probleme bestand darin, dass Sie für jeden Algorithmus verschiedene Indizes verwenden. Um das zu beheben, habe ich ein wenig Code überarbeitet. Hier ist der Code, den ich habe:

Sie werden also bemerken, dass ich ein ArrayList<Integer> gemacht habe, um Indizes zu halten, und ich gebe drei verschiedene Möglichkeiten, diese Array-Liste zu füllen - eine mit geraden Zahlen, nur eine mit ungeraden Zahlen und Ihre ursprüngliche Zufallsmethode.

Nur mit geraden Zahlen wird dieser Ausgang erzeugt:

  

Durchschnittliche Zeit: 175.609ns

     

Durchschnittliche Zeitüberspringzeit: 100.64691ns

Das Ausführen mit ungeraden Zahlen erzeugt nur diese Ausgabe:

  

Durchschnittliche Zeit: 178.05182ns

     

Durchschnittliche Suchzeit: 263.82928ns

Wenn Sie mit Ihrem ursprünglichen Zufallswert arbeiten, wird diese Ausgabe erzeugt:

  

Durchschnittliche Zeit: 175.95944ns

     

Durchschnittliche Suchzeit: 181.20367ns

Jedes dieser Ergebnisse ist sinnvoll.

Wenn Sie nur gerade Indizes auswählen, ist Ihr skipSearch-Algorithmus O (n / 2), also verarbeiten wir nicht mehr als die Hälfte der Indizes. Normalerweise sind uns konstante Faktoren in Bezug auf die zeitliche Komplexität egal, aber wenn wir uns die Laufzeit anschauen, dann ist es wichtig. Wir schneiden das Problem buchstäblich in zwei Hälften, was sich auf die Ausführungszeit auswirkt. Und wir sehen, dass die tatsächliche Ausführungszeit entsprechend halbiert ist.

Wenn wir nur ungerade Indizes auswählen, sehen wir einen viel größeren Einfluss auf die Ausführungszeit. Dies ist zu erwarten, weil wir nicht weniger als halbe Indizes verarbeiten.

Wenn die ursprüngliche Zufallsauswahl verwendet wird, sehen wir skipSearch schlechter (wie erwartet). Dies liegt daran, dass wir im Durchschnitt eine gerade Anzahl von geraden und ungeraden Indizes haben werden. Die geraden Zahlen werden schnell gefunden, aber die ungeraden Zahlen werden sehr langsam gefunden. Die lineare Suche wird den Index 3 früh finden, während die skipSearch ungefähr O (n / 2) Elemente verarbeitet, bevor sie den Index 3 findet.

Warum Ihr ursprünglicher Code seltsame Ergebnisse liefert, liegt für mich in der Luft. Es könnte sein, dass der Pseudozufallszahlengenerator die geraden Zahlen leicht begünstigt, könnte es aufgrund von Optimierungen sein, könnte es aufgrund von Verzweigungsprädiktorverrücktheit sein. Aber es wurde sicherlich nicht Äpfel mit Äpfeln verglichen, indem zufällige Indizes für beide Algorithmen ausgewählt wurden. Einige dieser Dinge könnten immer noch Auswirkungen auf meine Ergebnisse haben, aber zumindest versuchen die beiden Algorithmen jetzt, die gleichen Zahlen zu finden.