Optimierung für Anfänger oder über die Vorteile der Profilerstellung

    Ich habe die Aufgabe, in PHP den optimalen Algorithmus zum Einfügen eines neuen Wertes in ein geordnetes Array zu schreiben. Darüber hinaus wird argumentiert, dass dieser spezielle Algorithmus der beste ist. Zu diesem Zweck wurde vorgeschlagen, drei Optionen zu schreiben und die beste aus ihnen auszuwählen. Natürlich weiß ich, dass die beste Suchmethode binär ist, aber da sie beweisen sollen, dass es die beste ist, schreibe ich noch zwei. Mit dieser Einstellung und dem Vertrauen in das zukünftige Ergebnis begann ich zu programmieren.

    Was dabei herauskam, lade ich Programmieranfänger ein, zu lesen und zu diskutieren.

    Herausforderung


    Es gibt ein ziemlich großes (zehntausend Elemente) geordnetes Array mit Zahlen. Es ist notwendig, einen neuen Wert unter Beibehaltung der Reihenfolge optimal einzufügen.

    Lösungsoptionen


    Am einfachsten ist es, am Ende einzufügen und mit einer eingebauten Funktion neu zu sortieren. Aber anfangs gab es eine Bedingung, dies nicht zu tun.

    Was muss getan werden, um einen neuen Wert einzufügen? Finden Sie zunächst die gewünschte Position. Angesichts der Größe des Arrays wird dies wahrscheinlich der ressourcenintensivste Teil sein. Fügen Sie diesen Wert an der gefundenen Position ein. Sie müssen also 3 Suchoptionen für genau diese Position schreiben. Als experimentelle Kaninchen nehmen wir: Brute Force, binäre Suche, Suche mit Interpolation (ähnlich wie binäre, nur nicht halbieren, aber versuchen, die Position genauer zu erraten).

    Wenn Sie nicht interessiert sind, können Sie den Programmcode für die Suchfunktionen überspringen.

    Suche nach Suche


    function insertBruteForce(&$array, $value)
    {
    function insertBruteForce(&$array, $value)
    {
        foreach($array as $position => $test) {
            if ($test >= $value) {
                    break;
            }
        }
        insertTo($array, $position, $value);
    }
    

    Binäre Suche


    function insertBinary(&$array, $value)
    {
        $begin = 0;
        $end   = count($array) - 1;
        while ($end - $begin > 1) {
            $position = round(($begin + $end) / 2);
            if ($array[$position] > $value) {
                $end = $position;
            } elseif ($array[$position] < $value) {
                $begin = $position;
            } else {
                break;
            }
        }
        if ($array[$position] < $value) {
            ++$position;
        }
        insertTo($array, $position, $value);
    }
    

    Es sieht etwas seltsam aus, weil nicht der exakte Wert gesucht wird, sondern die Position zwischen den Elementen.

    Suche mit Interpolation


    function insertInterpolation(&$array, $value)
    {
        $begin = 0;
        $end   = count($array) - 1;
        while ($end - $begin > 1) {
            $range           = $array[$end] - $array[$begin];
            $percentPosition = ($value - $array[$begin]) / $range;
            $position        = $begin + round(($end - $begin) * $percentPosition);
            $position        = min($position, $end);
            if($array[$position] <= $value && (!isset($array[$position+1]) || $array[$position+1] >= $value)) {
                break;
            } elseif ($array[$position] > $value) {
                $end = $end != $position ? $position : $position - 1;
            } elseif ($array[$position] < $value) {
                $begin = $begin != $position ? $position : $position + 1;
            }
        }
        if ($array[$position] < $value) {
            ++$position;
        }
        insertTo($array, $position, $value);
    }
    


    Wert in gefundene Position einfügen


    Nun, es sollte einfach sein (wie ich damals dachte). In PHP gibt es jedoch keine integrierte Funktion zum Einfügen eines neuen Werts an einer bestimmten Position. Es wird nur der Wert ersetzt. Keine Angst, nutzen Sie das, was ist - schneiden Sie den Wert aus, kleben Sie ihn ein. Dies ist keine Aufzählung des Arrays, es ist nur einmal erforderlich, wir verwenden die eingebauten Funktionen, sie arbeiten auch schnell.

    function insertTo(&$array, $position, $value)
    {
        $array = array_merge(array_slice($array, 0, $position), array($value), array_slice($array, $position));
    }
    

    Wie sich später herausstellte, sollte dies nicht getan werden.

    Testergebnisse


    Schnelles Schreiben von Code zum Generieren einer zufälligen Reihe von Daten, Testen der mehrfachen Ausführung und Sammeln von Statistiken. Und dann passierte etwas Seltsames. Das Ergebnis war ungefähr so:
    insertBruteForce:
    0.0088
    insertBinary: 0.0088 insertInterpolation: 0.0087

    Der fehlende Unterschied zwischen binärer Suche und Interpolation kann noch erklärt werden. Aber warum liefert eine einfache Büste das gleiche Ergebnis? Eine Vergrößerung des Arrays verändert das Kräfteverhältnis nicht.

    Profiling eilt zur Rettung


    Es wurde deutlich, dass die übliche Zeitmessung diese Fragen nicht beantworten kann. Nun, Xdebug ist bereits installiert und konfiguriert. Es bleibt nur übrig, um die Profilerstellung zu aktivieren und zu sehen, was passiert.

    Und dann erwartete mich wieder eine Überraschung. Der Hauptteil der Zeit wurde nicht durch die Suche nach einer Position belegt, sondern durch das Einfügen eines neuen Elements in die gefundene Position. Gleichzeitig wurde die Ausführungszeit der Suche selbst durch das Ergebnis kaum beeinflusst.

    Sie müssen also die Einfügefunktion neu schreiben. Anstatt zu schneiden und zu kleben, versuche ich zu schieben und zu kleben.
    function insertDown(&$array, $value)
    {
        $i = count($array);
        for ($i = $i - 1; $i >= 0 && $array[$i] < $value; --$i) {
            $array[$i+1] = $array[$i];
        }
        $array[$i] = $value;
    }
    

    Schon besser, aber immer noch nicht richtig.

    Diese Option arbeitet 40% schneller und verbraucht weniger Speicher. Und das Ergebnis ist folgendes:
    insertBruteForce: 0.0052
    insertBinary: 0.0053
    insertInterpolation: 0.0053

    Und jetzt schauen wir uns noch einmal die letzte Funktion an. Was macht sie? Sie drückt die Elemente, bis sie die gewünschte Position erreicht. Aber muss sie die Position wirklich im Voraus kennen?

    Suchen und in eine Flasche geben


    function insertDown(&$array, $value)
    {
        $i = count($array);
        for ($i = $i - 1; $i >= 0 && $array[$i] >= $value; --$i) {
            $array[$i+1] = $array[$i];
        }
        $array[$i] = $value;
    }
    

    Ergebnis: Nur eine einfache Funktion (ja, mit Aufzählung) und eine Testzeit von 0,0049 Sekunden, bisher das beste Ergebnis.

    Die Vorteile der kollektiven Intelligenz


    Hinzugefügt am nächsten Tag.
    Als Ergebnis der Diskussion hier haben die Genossen und ich im Code Fehler aufgedeckt, die ich während der Bearbeitung gemacht habe (ich habe die ursprüngliche Version getestet, aber dann angefangen zu experimentieren). Bereits korrigiert und die aktualisierten Ergebnisse in den Text eingefügt.

    PQR schlug vor, die Funktion zum Einfügen von Werten durch folgende zu ersetzen:
    function insertTo(&$array, $position, $value)
    {
        array_splice($array, $position, 0, $value);
    }
    

    Es stellt sich heraus, dass PHP über eine Einfügefunktion verfügt, die jedoch Teil einer universelleren Funktion ist. Testergebnis:
    insertBruteForce:
    0.0035
    insertBinary: 0.0036
    insertInterpolation: 0.0037 insertDown: 0.0047

    Noch besser, aber immer noch komisch.

    SerafimArts schlug vor, die SplFixedArray-Klasse anstelle eines regulären Arrays zu verwenden. Ich versuche es. Die Einfügefunktion musste wirklich wieder "manuell" gemacht werden:
    function insertTo($array, $position, $value)
    {
        $size = $array->count();
        $array->setSize($size + 1);
        for ($i = $size - 1; $i >= $position; --$i) {
            $array[$i+1] = $array[$i];
        }
        $array[$position] = $value;
    }
    

    Ergebnisse:
    insertBruteForce: 0.0033
    insertBinary: 0.0019
    insertInterpolation: 0.0018
    insertDown: 0.0026

    Alle Optionen haben die Vorlaufzeit verkürzt. Und was am interessantesten ist, das Ergebnis ist genau das, was ursprünglich erwartet wurde und genau so, wie wir an der Universität unterrichtet wurden.

    Nachwort


    Kenntnisse und Annahmen sind gut, aber Sie müssen überprüfen, was in der Praxis passiert. Das richtige Werkzeug dafür ist nicht allgemein anerkannt:
            $start = microtime(true);
            <какой-то код>
            $time = microtime(true) - $start;
    

    und Profilerstellung. Obwohl die oben beschriebene Methode nützlich sein kann, liefert die Profilerstellung detailliertere Informationen und sammelt Statistiken nicht nur dort, wo Sie dies ausdrücklich angegeben haben (obwohl dies auch möglich ist).

    Wenn Sie mit Code experimentieren, sollten Sie sehr vorsichtig sein , um automatisierte Tests zu schreiben. In meinem Fall würde dies eine Reihe von Fehlern ausschließen, die während seiner Bearbeitung gemacht wurden.

    Vielen Dank an alle Kommentatoren für die Tipps und Vorschläge.

    Jetzt auch beliebt: