Wenn das "O" viel ausfällt

Ursprünglicher Autor: Jack Mott
  • Übersetzung


Big O ist ein großartiges Werkzeug. Sie können damit schnell die entsprechende Datenstruktur oder den entsprechenden Algorithmus auswählen. Aber manchmal kann uns eine einfache Analyse des „O“ eines Großen täuschen, wenn Sie nicht sorgfältig über den Einfluss konstanter Faktoren nachdenken. Ein Beispiel, das häufig beim Programmieren auf modernen Prozessoren auftritt, hängt mit der Wahl der Datenstruktur zusammen: Array, Liste oder Baum.


Speicher, langsam-langsamer Speicher


In den frühen 1980er Jahren waren der Zeitaufwand für das Abrufen von Daten aus dem RAM und der Zeitaufwand für die Durchführung von Berechnungen mit diesen Daten ungefähr gleich. Es war möglich, einen Algorithmus zu verwenden, der sich versehentlich durch den dynamischen Speicher bewegte und Daten sammelte und verarbeitete. Seitdem haben Prozessoren damit begonnen, Berechnungen um ein Vielfaches schneller durchzuführen, von 100 bis 1000 Mal, als um Daten aus dem RAM zu empfangen. Dies bedeutet, dass der Prozessor, während er auf Daten aus dem Speicher wartet, Hunderte von Zyklen im Leerlauf ist und nichts unternimmt. Das wäre natürlich völlig dumm, daher enthalten moderne Prozessoren mehrere Ebenen des integrierten Cache. Jedes Mal, wenn Sie ein Datenelement aus dem Speicher anfordern, werden zusätzliche benachbarte Speicherelemente in den Prozessor-Cache geschrieben. Infolgedessen können Sie mit einem sequentiellen Durchgang durch den Speicher fast genauso schnell darauf zugreifen Wie viel der Prozessor Informationen verarbeiten kann, weil ständig Speicherstücke in den L1-Cache geschrieben werden. Wenn Sie zu zufälligen Speicheradressen wechseln, können Sie den Cache häufig nicht verwenden, und die Leistung kann erheblich beeinträchtigt werden. Wenn Sie mehr wissen wollen, dann einen BerichtDer Acton Mike bei CppCon ist ein großartiger Ausgangspunkt (und eine großartige Zeit).


Infolgedessen sind Arrays zu einer besseren Datenstruktur geworden, wenn die Leistung wichtig ist, auch wenn laut der O-Analyse ein großes Array langsamer arbeiten sollte. Wenn Sie einen Baum verwenden möchten, funktioniert ein sortiertes binäres Sucharray möglicherweise besser. Wenn Sie eine Warteschlange verwenden möchten, funktioniert ein wachsendes Array möglicherweise besser und so weiter.


Verknüpfte Liste und dynamisches Array


Wenn Sie wissen, wie wichtig es ist, auf den seriellen Speicher zuzugreifen, ist es für Sie keine Überraschung, dass das Array schneller als eine verknüpfte Liste ist, wenn Sie eine Sammlung schnell durchsuchen müssen. Intelligente Speicherverwaltungs- und Garbage Collector-Umgebungen speichern verknüpfte Listenknoten möglicherweise konsistenter, können dies jedoch nicht garantieren. Die Verwendung eines Raw-Arrays erfordert normalerweise komplexeren Code, insbesondere wenn Sie neue Elemente einfügen oder hinzufügen müssen, da Sie das Wachstum des Arrays, das Verschieben der Elemente usw. bewältigen müssen. Die meisten Sprachen haben native Bibliotheken, die eine bestimmte Implementierung dynamischer Arrays enthalten. In C ++ gibt es einen Vektor , in C # gibt es eine Liste (in F # wird sie unter dem Namen ResizeArray verwendet) und in Java gibt es eine ArrayList. In der Regel bieten diese Strukturen dieselbe oder eine ähnliche Schnittstelle wie eine verknüpfte Liste. In diesem Artikel werde ich solche Strukturen als dynamische Arrays (Array-Liste) bezeichnen. Beachten Sie jedoch, dass in den Beispielen in C # die List-Klasse und nicht die ältere ArrayList verwendet wird.


Was ist, wenn Sie eine Datenstruktur benötigen, in die Sie Elemente schnell einfügen und schnell durchgehen können? Stellen wir uns für dieses Beispiel vor, dass wir einen solchen Fall haben: Wir werden zu Beginn der Sammlung etwa fünfmal häufiger einfügen, als wenn wir ihn durchgehen. Stellen wir uns auch vor, dass sowohl die verknüpfte Liste als auch das dynamische Array in unserer Umgebung gleichermaßen schöne Schnittstellen haben, mit denen Sie arbeiten können. Es bleibt nur zu entscheiden, was eine effektivere Lösung sein wird. Wir können uns mehr der O-Analyse zuwenden, um unsere wertvolle Zeit zu optimieren. Wenden wir uns einem nützlichen Hinweis auf das „O“ zu . Die entsprechenden Schwierigkeiten für diese Datenstrukturen sind:


PassageEinfügen
Dynamisches ArrayO (n)O (n)
Verknüpfte ListeO (n)O (1)

Das Problem mit dynamischen Arrays ist das Einfügen. Zumindest müssen Sie jedes Element eine Einheit nach der Einfügemarke kopieren und verschieben, um Platz für das neue Element zu schaffen. Daher O (n). Manchmal müssen Sie ein neues Array erstellen, das größer ist, damit ein Platz zum Einfügen vorhanden ist. In unserem Fall erfolgt die Einfügung fünfmal häufiger als die Passage, sodass die Schlussfolgerung offensichtlich zu sein scheint. Während n groß genug ist, sollte eine verknüpfte Liste im Allgemeinen effizienter sein.


Ein Experiment


Aber um sicherzugehen, ist es besser zu zählen. Experimentieren wir mit C # mithilfe von BenchMarkDotNet . C # verfügt über eine LinkedList-Auflistung, bei der es sich um eine klassische verknüpfte Liste handelt, und List, bei der es sich um ein dynamisches Array handelt. Die Schnittstellen sind für beide ähnlich und beide können in unserem Fall problemlos angewendet werden. Betrachten Sie den schlimmsten Fall für ein dynamisches Array - die Einfügung erfolgt immer am Anfang, sodass Sie das gesamte Array mit jeder Einfügung kopieren müssen. Die Konfiguration der Testumgebung ist wie folgt:


Host Process Environment Information:
BenchmarkDotNet.Core=v0.9.9.0
OS=Microsoft Windows NT 6.2.9200.0
Processor=Intel(R) Core(TM) i7-4712HQ CPU 2.30GHz, ProcessorCount=8
Frequency=2240910 ticks, Resolution=446.2473 ns, Timer=TSC
CLR=MS.NET 4.0.30319.42000, Arch=64-bit RELEASE [RyuJIT]
GC=Concurrent Workstation
JitModules=clrjit-v4.6.1590.0
Type=Bench  Mode=Throughput  

Testfälle:


    [Benchmark(Baseline=true)]
    public int ArrayTest()
    {        
        //In C#, List is an array backed list.
        List local = arrayList;
        int localInserts = inserts;
        int sum = 0;
        for (int i = 0; i < localInserts; i++)
        {
            local.Insert(0, 1); //Insert the number 1 at the front
        }
        // For loops iterate over List much faster than foreach
        for (int i = 0; i < local.Count; i++)
        {
            sum += local[i];  //do some work here so the JIT doesn't elide the loop entirely
        }
        return sum;
    }
    [Benchmark]
    public int ListTest()
    {
        LinkedList local = linkedList;
        int localInserts = inserts;
        int sum = 0;
        for (int i = 0; i < localInserts; i++)
        {
            local.AddFirst(1); //Insert the number 1 at the front
        }
        // Again, iterating the fastest possible way over this collection
        var node = local.First;
        for (int i = 0; i < local.Count; i++)
        {
            sum += node.Value;
            node = node.Next;
        }
        return sum;
    }

Ergebnisse:


MethodeGrößeBeilagenMedian
Arraytest100538.9983 uns
Listtest100551.7538 uns

Das dynamische Array gewinnt mit einem guten Vorsprung. Dies ist jedoch eine kleine Liste. "O" groß beschreibt die Leistung, nur zu großen Größen zu wachsen. Daher nsollten die Testergebnisse beim Erhöhen eventuell umgekehrt werden n. Versuchen wir mal:


MethodeGrößeBeilagenMedian
Arraytest100538.9983 uns
Listtest100551.7538 uns
Arraytest1000542.1585 uns
Listtest1000549.5561 uns
Arraytest100.0005208.9662 uns
Listtest100.0005312.2153 uns
Arraytest1.000.00052,179.2469 us
Listtest1.000.00054,913.3430 us
Arraytest10.000.000536.103.8456 uns
Listtest10.000.000549.395,0839 uns


Unerwartete Ergebnisse für viele. Egal wie groß n, ein dynamisches Array ist immer noch besser. Um die Leistung zu verschlechtern, muss sich das Verhältnis von Einsätzen zu Gängen ändern, nicht nur die Größe der Sammlung. Beachten Sie, dass dies kein Fehler der "O" -Analyse des großen ist, sondern nur ein menschlicher Fehler - wir wenden die Methode nicht richtig an. Wenn Sie sich mit Mathematik beschäftigen, zeigt „O“ deutlich, dass beide Datenstrukturen mit derselben Geschwindigkeit wachsen, bis sich das Verhältnis von Einfügungen zu Durchläufen nicht mehr ändert.


Wo sich der Wendepunkt befindet, hängt von vielen Faktoren ab. Google Chandler Carrut schlug jedoch eine gute ungefähre Regel vor : Ein dynamisches Array ist effizienter als eine verknüpfte Liste, bis eine Größenordnung mehr Einfügungen als Durchgänge vorhanden sind. In unserem Fall funktioniert die Regel gut, da Sie bei einem Verhältnis von 10: 1 eine Verschiebung in Richtung einer verknüpften Liste sehen können:


MethodeGrößeBeilagenMedian
Arraytest100.00010328,147.7954 ns
Listtest100.00010324,349.0560 ns

Teufel im Detail


Ein dynamisches Array gewinnt, weil sich die durchlaufenden Zahlen nacheinander im Speicher befinden. Jedes Mal, wenn eine Nummer aus dem Speicher angefordert wird, wird dem L1-Cache ein ganzer Satz von Nummern hinzugefügt, sodass die nächsten 64 Datenbytes zur Verarbeitung bereit sind. Bei der Arbeit mit einer verknüpften Liste jeder Anrufnode.NextLeitet den Zeiger auf den nächsten Knoten um, und es gibt keine Garantie dafür, dass sich dieser Knoten unmittelbar nach dem vorherigen im Speicher befindet. Daher kommen wir manchmal über den Cache hinaus. Wir müssen jedoch nicht immer mit Typen arbeiten, die Werte direkt speichern, insbesondere in objektorientierten Sprachen, wo dies häufig durch Referenztypen geschieht. In diesem Fall befinden sich die Zeiger selbst im Speicher nacheinander im dynamischen Array, die Objekte, auf die sie zeigen, jedoch nicht. Die Situation ist immer noch besser als bei einer verknüpften Liste, bei der Zeiger für jedes Element zweimal dereferenziert werden müssen. Wie wirkt sich dies jedoch auf die Gesamtleistung aus?


Die Leistung wird abhängig von der Größe der Objekte und den Merkmalen von Eisen und Software erheblich beeinträchtigt. Wenn wir die Zahlen im obigen Beispiel durch kleine Objekte (12 Byte) ersetzen, sinkt der Bruchpunkt in einem Durchgang auf 4 Einfügungen:


MethodeGrößeBeilagenMedian
ArrayTestObject100.0000674.1864 uns
ListTestObject100.00001.140.9044 uns
ArrayTestObject100.0002959.0482 uns
ListTestObject100.00021.121,5423 uns
ArrayTestObject100.00041.230.6550 us
ListTestObject100.00041.142.6658 uns

Verwalteter C # -Code leidet in diesem Fall stark, da das Durchlaufen eines dynamischen Arrays unnötige Überprüfungen der Grenzen des Arrays verursacht. Ein Vektor in C ++ arbeitet mit größerer Wahrscheinlichkeit effizienter. Wenn Sie dieses Problem völlig aggressiv lösen, können Sie eine schnellere Klasse für ein dynamisches Array mit unsicherem C # -Code schreiben, um zu vermeiden, dass die Grenzen des Arrays überprüft werden. Der relative Unterschied hängt auch stark davon ab, wie der Speicherzuweiser und der Garbage Collector den dynamischen Speicher verwalten, wie groß Objekte sind und andere Faktoren. Größere Objekte verbessern normalerweise die Leistung dynamischer Arrays in meiner Umgebung. Wenn es um ganze Anwendungen geht, kann sich die relative Leistung dynamischer Arrays mit zunehmender Fragmentierung des dynamischen Speichers ebenfalls verbessern, um dies sicherzustellen


Ein weiterer Punkt. Wenn die Objekte klein genug sind (in verschiedenen Situationen 16 bis 32 Byte oder weniger), sollten Sie die Option in Betracht ziehen, sie nach Wert ( structin .NET) und nicht im Objekt zu speichern . Dies verbessert nicht nur die Leistung aufgrund der sequentiellen Verteilung im Speicher erheblich, sondern reduziert theoretisch auch die zusätzliche Last aufgrund der Speicherbereinigung, abhängig vom Verwendungsszenario dieser Daten:


MethodeGrößeBeilagenMedian
ArrayTestObject100.000102,094.8273 us
ListTestObject100.000101.154.3014 uns
ArrayTestStruct100.00010792.0004 uns
ListTestStruct100.000101.206.0713 uns

Java kann hier bessere Ergebnisse zeigen, da es automatisch intelligente Änderungen an kleinen Objekten vornimmt, oder Sie können einfach separate Arrays primitiver Typen verwenden. Und obwohl das Schreiben sehr mühsam ist, kann es schneller sein als eine Reihe von Strukturen. Es hängt alles von den Funktionen des Zugriffs auf Daten in Ihrem Code ab. Denken Sie daran, wenn die Leistung besonders wichtig ist.


Stellen Sie sicher, dass die Abstraktion gerechtfertigt ist


Oft sind die Leute mit solchen Schlussfolgerungen nicht einverstanden, und ihre Argumente sind Code-Sauberkeit, Korrektheit und Wartbarkeit. Natürlich hat jeder Bereich seine eigenen Prioritäten, aber ich glaube, wenn die Abstraktion die Sauberkeit nur geringfügig verbessert, wenn die Leistung stark leidet, sollten Sie es sich zur Regel machen, die Leistung zu wählen. Wenn Sie keine Zeit für das Studium der Umgebung haben, können Sie sich über Fälle informieren, in denen es eine schnellere und nicht weniger saubere Lösung gibt, wie dies häufig bei dynamischen Arrays anstelle von Listen der Fall ist.


Reflexionsinformationen: Hier sind sieben verschiedene Möglichkeiten, um die Summe einer Liste von Zahlen in C # mit Laufzeit und Speichernutzung zu ermitteln. Überlaufprüfungsarithmetik wird überall verwendet, so dass ein Vergleich mit Linq, wo die Summenmethode genau diese Arithmetik verwendet, korrekt ist. Beachten Sie, dass die beste Methode schneller ist als die anderen. Beachten Sie, wie teuer der beliebteste Weg ist. Beachten Sie, dass die Abstraktion foreachgut mit Arrays funktioniert, jedoch nicht mit dynamischen Arrays oder verknüpften Listen. Unabhängig von Ihrer Sprache und Umgebung ist es wichtig, diese Details zu verstehen, um standardmäßig die richtigen Entscheidungen zu treffen.


MethodeLängeMedianZugewiesene Bytes / Op
LinkedListLinq100.000990.7718 uns23, 192,49
RawArrayLinq100.000643.8204 uns11.856,39
LinkedListForEach100.000489.7294 uns11.909,99
LinkedListFor100.000299.9746 uns6,033,70
ArrayListForEach100.000270.3873 uns6,035,88
ArrayListFor100.00097.0850 uns1,574,32
RawArrayForEach100.00053.0535 uns1,574,84
RawArrayFor100.00053.1745 uns1,577,77

    [Benchmark(Baseline = true)]
    public int LinkedListLinq()
    {
        var local = linkedList;
        return local.Sum();
    }
    [Benchmark]
    public int LinkedListForEach()
    {
        var local = linkedList;
        int sum = 0;
        checked
        {
            foreach (var node in local)
            {
                sum += node;
            }
        }
        return sum;
    }
    [Benchmark]
    public int LinkedListFor()
    {
        var local = linkedList;
        int sum = 0;
        var node = local.First;
        for (int i = 0; i < local.Count; i++)
        {
            checked
            {
                sum += node.Value;
                node = node.Next;
            }
        }
        return sum;
    }
    [Benchmark]
    public int ArrayListFor()
    {
        //In C#, List is an array backed list
        List local = arrayList;
        int sum = 0;
        for (int i = 0; i < local.Count; i++)
        {
            checked
            {
                sum += local[i];
            }
        }
        return sum;
    }
    [Benchmark]
    public int ArrayListForEach()
    {        
        //In C#, List is an array backed list
        List local = arrayList;
        int sum = 0;
        checked
        {
            foreach (var x in local)
            {
                sum += x;
            }
        }
        return sum;
    }
    [Benchmark]
    public int RawArrayLinq()
    {
        int[] local = rawArray;
        return local.Sum();
    }
    [Benchmark]
    public int RawArrayForEach()
    {
        int[] local = rawArray;
        int sum = 0;
        checked
        {
            foreach (var x in local)
            {
                sum += x;
            }
        }
        return sum;
    }
    [Benchmark]
    public int RawArrayFor()
    {
        int[] local = rawArray;
        int sum = 0;
        for (int i = 0; i < local.Length; i++)
        {
            checked
            {
                sum += local[i];
            }
        }
        return sum;
    }

Jetzt auch beliebt: