Ich denke, auf Habré gibt es Fans der Silicon Valley-Serie . Diese Woche zeigten sie zum ersten Mal in allen sechs Spielzeiten einen großen Code - natürlich möchte ich hier sofort darauf eingehen.
Um den Hauptcharakter Richard Hendrix zu demütigen, zeigt sein ehemaliger Chef bei einem Treffen ein Fragment seines alten Codes. Dort wird eine lineare Suche auf die bereits sortierten Daten angewendet - damit wird die Aufgabe erledigt, aber sie sieht sehr ineffizient aus.
Richard selbst argumentiert nicht, dass der Code schlecht ist. Unter den Zuschauern der Serie fand seine Entscheidung jedoch plötzlich Verteidiger, und jetzt frage ich mich, was Habr von ihrer Position hält.
Richards bekanntes Code-Snippet sieht folgendermaßen aus:
int index = 0; while (!element.equals(sortedList.get(index)) && sortedList.size() > ++index); return index < sortedList.size() ? index : -1;
Hier dreht sich eine lineare Suche der Reihe nach um jedes Element einer sortierten Liste, bis es zu dem richtigen Element kommt. In der Regel bevorzugen sie die binäre Suche nach sortierten Daten, bei der die Menge jedes Mal in zwei Hälften geteilt und die ungeeignete Hälfte als Ganzes verworfen wird (da die Anzahl der Iterationen in der linearen Suche mit zunehmender Datenmenge viel schneller zunimmt als in der binären). Aber im subreddit / r / SiliconValleyHBO erschien der folgende Kommentar :
"Ich möchte ein wenig studieren und darauf hinweisen, dass sich Richards" Fehler "bei der Verwendung der linearen Suche anstelle der binären Suche nach sortierten Daten in vielen Fällen als produktiver herausstellt. Bei riesigen Datensätzen (ich glaube, die Schwelle liegt bei Millionen von Elementen) ist die binäre Suche schneller. Wenn Ihr Datensatz jedoch nicht riesig ist, wird eine lineare Suche vom Prozessor besser zwischengespeichert, eignet sich besser für die Verzweigungsvorhersage, und Ihr Algorithmus kann auch vektorisiert werden. Lineare Suchen erfordern mehr Iterationen, aber jede ist wahnsinnig schneller als eine binäre Suchiteration. Dies ist nicht intuitiv und widerspricht allem, was Sie an der Universität gelehrt haben, ist es aber.
Dieser Bericht ist sehr interessant und zeigt einige erstaunliche Ergebnisse realer Leistungsmessungen. “
Und andere Mitglieder des Threads unterstützten den Kommentator: Ja, theoretisch sind alle Iterationen gleich, aber auf echter Hardware mit echten Optimierungen ist alles völlig anders. So wie der Schöpfer der Serie, Mike Judge, in den 80er Jahren im Valley arbeitete, als all diese L1-Caches und die Verzweigungsvorhersage nicht besonders ausgeprägt waren, lag das CPU-Verhalten viel näher am idealen Modell - dies ist ein Beispiel in der Serie.
Für mich, wie der Kommentar sagt, klingt alles widersinnig, aber es wurde interessant herauszufinden, ob Richard Recht haben könnte. Natürlich stört es die Tatsache, dass nicht der gesamte Kontext in der Reihe angegeben ist. Beispielsweise wissen wir nicht, wie viele Daten durchlaufen wurden. Einerseits arbeitete Richard dann für den Internetgiganten Hooli, wo er wahrscheinlich mit Millionen von Aufzeichnungen zu tun hatte, andererseits war es sein erster Arbeitstag, und er konnte nicht sofort in Millionen gestürzt werden. Wir stellen die Frage so: Auch wenn die binäre Suche für die meisten Aufgaben in Hooli eindeutig besser ist, ist es wahrscheinlich, dass Richard die richtige Entscheidung für seine Bedingungen getroffen hat und andere Charaktere ihn vergeblich auslachen, ohne den Kontext zu kennen?
Um das zu verstehen, habe ich einen von Reddit zitierten Bericht geöffnet. Wie versprochen erwies es sich als interessant (nicht überraschend, da dies ein Bericht von Andrei Alexandrescu ist ), aber nachdem ich mir einen Teil angesehen und durch den Rest geklickt hatte, sah ich dort keine Vergleichsmessungen der binären und linearen Suche.
Aber ich erinnerte mich, dass derselbe Alexandrescu auf unserer DotNext-Konferenz auch über Leistung sprach. Ich öffnete die Textversion seines Berichts, den wir für Habr erstellt hatten, und suchte nach dem Wort "linear". Es stellte sich unter anderem heraus, dass es nur ein Beispiel für ein merkwürdiges Szenario gab, in dem diese Suche viel effektiver wäre als eine binäre (Suche nach übereinstimmenden Elementen von zwei Mengen in dem Fall, in dem diese Mengen identisch sind) - dies ist jedoch ein sehr spezifischer Fall, für den es keine allgemeine Schlussfolgerung gibt. " lineare Suche wird unterschätzt. "
Googelte, was das moderne Internet dazu sagt - fand aber im Grunde genommen Antworten auf Stack Overflow, wo sie einfach "benutze binäre, weniger Iterationen" schrieben. Es gab auch Fälle, in denen sie versuchten, ein Benchmarking durchzuführen, aber für mich auch nicht sehr überzeugend wirkten.
Hier bittet die Option natürlich darum, "sich selbst zu vergleichen, um alles selbst auf echter Hardware zu sehen".
Wenn ich jedoch bei all meinen Besuchen bei DotNext etwas von zwei leistungsbewussten Andreevs (Alexandrescu und Akinshina ) gelernt habe , ist es eine Erkenntnis, wie oft Menschen falsch benchmarken und wie viel sie nicht berücksichtigen. Daher habe ich ein geringes Vertrauen in zufällige Internet-Posts mit Benchmarks, aber für mich selbst noch weniger.
Glücklicherweise gibt es Leute auf Habr, die weit mehr verstehen als ich (zum Beispiel derselbe Andrey DreamWalker Akinshin, der ein ganzes Buch über Benchmarking geschrieben hat). Wenn Sie das Thema verstehen, teilen Sie uns daher in den Kommentaren mit, wie alles wirklich ist. Zu welcher Datengröße kann ein linearer Ansatz immer noch eine gute Wahl sein? Wie wahrscheinlich ist es, dass Richard alles richtig gemacht hat, auch wenn er selbst nicht bereit ist, es zu verteidigen?
Und wenn es keine sachkundigen Kommentatoren gibt, muss ich Akinshin beim nächsten DotNext an die Batterie anschließen und den Benchmark erstellen.