Findet Fibonacci schneller als die binäre Suche?
Ich lese einige Materialien, die behaupten, Fibonacci Suche ist schneller als binäre Suche im Durchschnitt, und die Hauptursache ist "es beinhaltet nur Addition und Subtraktion, nicht Division durch 2".
Ich habe einige Fragen:
1.Ist Fibonacci schneller als binäre Suche ohne Rücksicht auf die Betriebsgeschwindigkeit? Als die Schritte, die binäre Suche nehmen, sind weniger.
2.Die Division durch 2 kann durch Bit-Shift-Operation erfolgen, ist es wirklich langsamer als Addition?
3.Was ist der Vorteil der Fibonacci-Suche im Vergleich zur binären Suche?
2 Antworten
Ist Fibonacci schneller als die binäre Suche ohne Rücksicht auf die Betriebsgeschwindigkeit? Wie die Schritte binäre Suche nehmen, sind weniger.
Es hängt vom zugrunde liegenden Speichersystem für die Liste ab. Zum Beispiel - denken Sie an eine Festplatte. Es ist viel "billiger", nach einer Stelle im selben Zylinder des vorher gelesenen zu suchen - da sich der Lesearm nicht bewegen muss. Also, wenn Ihre Lesevorgänge viel näher beieinander liegen - Sie müssen den Lesearm wahrscheinlich weniger bewegen - so ist die erwartete Zeit für jede Suche auf der Festplatte kürzer. Außerdem ist es ähnlich schneller, den Lesearm über weniger Zylinder zu bewegen, als ihn über mehrere Zylinder zu bewegen.
Im Beispiel:
Es ist viel billiger, den Lesearm von (1) nach (2) zu bewegen als von (1) nach (3). Und da (2) "näher" ist (in Bezug auf Adressen), dann sind (3) kürzere Sprünge wahrscheinlicher in dieser Kategorie. [Von (1) bis (2) bewegt sich der Lesearm überhaupt nicht, er lässt die Platte nur drehen, bis sie ihn erreicht hat]
Die Division durch 2 kann per Bit - Shift - Operation erfolgen, ist das wirklich so? langsamer als die Addition?
Dies ist hauptsächlich ein Hardware- (und Compiler-Optimierung) Problem. Ich kann mir keinen Grund vorstellen, warum ein Hersteller diese Optimierung nicht vornehmen wird, und Bit-Shift in den meisten Implementierungen, die mir bekannt sind, ist so schnell wie Additionen.
Was ist der Vorteil der Fibonacci-Suche im Vergleich zur binären Suche?
Wie in (1) erwähnt, führt ein kürzerer Abstand zwischen aufeinander folgenden Suchvorgängen zu kürzeren (erwarteten) Suchzeiten.
Additionen, Subtraktionen und Divisionen von 2 nehmen alle einen einzigen Takt. Die betreffende Arithmetik favorisiert Fibonacci nicht, im Gegenteil.
Und du brauchst etwa 44% mehr Nachschlagevorgänge mit Fibonacci ( Log(2)/Log(Phi) - 1 ). Schwierig, durch schnellere Speicherzugriffe zu kompensieren!
Wenn Sie nach Alternativen zur binären Suche suchen, versuchen Sie Ihr Glück mit der Interpolationssuche. Ссылка
Tags und Links algorithm search binary-search fibonacci