In dieser Frage geht es um die Effizienz einer linearen Suche im Vergleich zur Effizienz einer binären Suche nach einem vorsortierten Array im zusammenhängenden Speicher ...
Ich habe eine Anwendung in Fortran geschrieben (77!). Eine häufige Operation für meinen Teil des Codes besteht darin, den Index in einem Array zu finden, so dass gx(i) <= xin < gx(i+1) . Ich habe dies derzeit als binary search implementiert - sorry für die Anweisungsbezeichnungen und goto - Ich habe kommentiert, was die äquivalenten Statements mit fortran 90 ... tun würden ...
Heute las ich jedoch auf Wikipedia über binäre Suche und stieß auf folgendes:
%Vor%Ich verstehe diese Aussage nicht vollständig - mein Eindruck war, dass Cache-Fets in großen (ish) Chunks gleichzeitig gesammelt wurden. Wenn wir also am Anfang des Arrays beginnen, dachte ich, dass der Großteil des Arrays dies tun würde schon im Cache sein (zumindest so viel, wie es für eine lineare Suche wäre), also hätte ich nicht gedacht, dass das wichtig wäre.
Also meine Frage ist, gibt es eine Möglichkeit zu sagen, welcher Algorithmus besser funktioniert (lineare oder binäre Suche?) Gibt es eine Array-Größengrenze? Ich verwende derzeit Arrays mit einer Größe von ungefähr 100 Elementen ...
Bei kleinen Arrays ist das Problem kein Cache. Sie haben Recht: Ein kleines Array wird wahrscheinlich schnell zwischengespeichert.
Das Problem besteht darin, dass die Verzweigungsvorhersage für die binäre Suche wahrscheinlich fehlschlägt, da Verzweigungen auf eine datenabhängige Art und Weise zufällig ausgewählt oder übersprungen werden. Verzweigungsvorhersagefehler blockieren die CPU-Pipeline.
Dieser Effekt kann schwerwiegend sein. Sie können einfach 3 bis 8 Elemente linear in der gleichen Zeit suchen, die für einen einzelnen binären Suchzweig erforderlich ist (und Sie müssen mehrere binäre Suchzweige ausführen). Der genaue Break-even-Punkt muss gemessen werden.
Das Anhalten der CPU-Pipeline ist extrem teuer. Ein Core i7 kann bis zu 4 Befehle pro Taktzyklus absetzen (12 Giga-Befehle pro Sekunde bei 3 GHz!). Aber nur, wenn du nicht vertraust.
Es gibt verzweigungsfreie Algorithmen, die eine binäre Suche durchführen, indem sie CPU-Befehle mit bedingter Bewegung verwenden. Diese Algorithmen lösen im Wesentlichen 32 Suchschritte aus und verwenden in jedem Schritt ein CMOV (32 Schritte sind das theoretische Maximum). Sie sind frei von Verzweigungen, aber nicht stallfrei: Jeder nächste Schritt hängt zu 100% von dem vorherigen ab, so dass die CPU im Befehlsstrom nicht vorausladen kann. Es muss die ganze Zeit warten. Also lösen sie dieses Problem nicht, verbessern es nur geringfügig.
Tags und Links performance fortran binary-search fortran77 linear-search