Bestimmte Anomalien in der binären Suche Laufzeit

Question

Ich habe eine modifizierte Version der binären Suche, die ein Array in sortierter Reihenfolge und einen Wert übernimmt, und gibt den kleinstmöglichen Index eines Elements, das gleich oder größer als der angegebene Wert (oder -1 wenn der Wert größer als der max ist)

Nach dem Ausführen des obigen Algorithmus funktioniert alles einwandfrei und die Methode funktioniert wie erwartet. Ich habe es jedoch über verschiedene Eingabegrößen ausgeführt, um die Laufzeit zu messen.

for(int i=1;i<=20;i++){ 
    int size=10*(i*i*i*i); 
int[] array=createRandomSortedArray(size); 
long startTime=System.nanoTime(); 
int index=findSmallestIndex(array, needle); 
long et=System.nanoTime()-startTime; 
System.out.println("To find "+needle+" in "+size+" inputs "+" execution time is "+et+" nanoseconds"); 
} 

und im Anschluss wurden die observtions: -

To find 50 in 10 inputs execution time is 5775 nanoseconds 
To find 50 in 160 inputs execution time is 1925 nanoseconds 
To find 50 in 810 inputs execution time is 4330 nanoseconds 
To find 50 in 2560 inputs execution time is 5293 nanoseconds 
To find 50 in 6250 inputs execution time is 3849 nanoseconds 
To find 50 in 12960 inputs execution time is 3368 nanoseconds 
To find 50 in 24010 inputs execution time is 3849 nanoseconds 
To find 50 in 40960 inputs execution time is 11548 nanoseconds 
To find 50 in 65610 inputs execution time is 9143 nanoseconds 
To find 50 in 100000 inputs execution time is 4812 nanoseconds 
To find 50 in 146410 inputs execution time is 4812 nanoseconds 
To find 50 in 207360 inputs execution time is 11549 nanoseconds 
To find 50 in 285610 inputs execution time is 8661 nanoseconds 
To find 50 in 384160 inputs execution time is 8661 nanoseconds 
To find 50 in 506250 inputs execution time is 11549 nanoseconds 
To find 50 in 655360 inputs execution time is 11067 nanoseconds 
To find 50 in 835210 inputs execution time is 11549 nanoseconds 
To find 50 in 1049760 inputs execution time is 11549 nanoseconds 
To find 50 ininputs execution time is 11067 nanoseconds 
To find 50 in 1600000 inputs execution time is 12030 nanoseconds 

sehe ich, dass die Ausführungszeit für die 10 Eingänge als ihre nachfolgende 160 Eingangsgröße deutlich höher ist. Um zu überprüfen, Dinge, lief ich die Ausführung für 10 Eingänge von sich außerhalb der Schleife und im Anschluss an das Ergebnis

To find 50 in 10 inputs execution time is 962 nanoseconds 

Warum das so ist? Warum existiert diese Anomalie? Es gibt noch einige andere Schritte, bei denen die Laufzeit langsamer ist als die vorhergehende niedrigere Eingabegröße.

Answer 1

Haben Sie die VM vor dem Start Ihres Microbenchmarks "aufwärmen" lassen? Versuchen Sie, diesen Code ein paar tausend Mal auszuführen, bevor Sie tatsächlich Ergebnisse aufzeichnen, und sehen Sie, ob dies einen Unterschied macht. Sie können die folgende Befehlszeile Argument hinzufügen, um zu sehen, was mit dem JIT-kompiliert wird:

-XX:+PrintCompilation 

Sie auch Ihr Programm mit

-Xint 

auszuschalten alle Hotspot-Optimierungen ausführen können und versuchen, ein Äpfel zu bekommen für Äpfel Vergleich.

Wenn dies nicht das Problem ist - ich vermute, es gibt einige konstante Kosten, um einfach Ihre Methode aufzurufen. Versuchen Sie, die Eingabegröße linear zu vergrößern, und sehen Sie, ob Sie auf diese Weise Korrelationen zeichnen können. Es ist schwer zu sagen, wenn Sie von 10 auf 160 springen.

Schließlich möchten Sie vielleicht ein Flag enthalten, das bei Aktivierung wird das Verhalten (z. B. Anzahl der Vergleiche usw.) protokolliert der Code ausgeführt, um zu sehen, ob Sie irgendwelche tun unnötige Arbeit.

Answer 2

Könnte Hotspot seine Magie machen. Kehren Sie die Reihenfolge der Läufe um (large first), um dies zu überprüfen.

Answer 3

Um dies zu analysieren, würde ich das tatsächliche Array ausgeben, das der Algorithmus durchsucht. Da es so aussah, als wären die Arrays für jeden Lauf nicht die gleichen, ist es schwer zu vergleichen, da die Anzahl der besuchten Indizes vollständig vom Inhalt des Arrays und des Suchelements abhängig ist.