Liste Besser init mit einer maximalen Kapazität zu initialisieren und nur einen Bruchteil davon oder init ohne Kapazität zu verwenden

7

Ich habe eine List<MyStruct> , die ich initialisiere, um leer zu sein, und ich werde diese Struktur in einer Schleife füllen, während ich die Daten analysiere. Ich weiß, dass es eine maximale Anzahl von Einträgen gibt, die in diese Liste eingefügt werden. Für jetzt sagen wir 1000. Aber nach meiner Analyse der 1000 Einträge kann ich am Ende nur 2 in die Liste setzen. Also sollte ich die Liste mit einer Kapazität von 1000 initialisieren oder keine Kapazität angeben und nur die wenigen Einträge hinzufügen. Es könnte jedoch am Ende alle 1000 hinzufügen. Was ist der beste Weg, Leistung klug?

    
jamone 22.01.2010, 20:25
quelle

6 Antworten

9

Wenn es wirklich so weit variieren kann, dann sollten Sie die Kapazität nicht einstellen. Bei den meisten Sammlungen verdoppelt sich die Kapazität, wenn sie erfüllt wird (mit einer Standardkapazität von 16, glaube ich), so dass sich Ihre Kapazität beim Auffüllen dem Maximum nähert.

    
Nick 22.01.2010, 20:28
quelle
17

Ist nicht wirklich wichtig. Nicht optimieren. Stellen Sie nur die Kapazität ein, wenn Sie eine gute Idee haben, ist es ungefähr die Menge, die Sie brauchen. Unter der Haube verdoppelt sich die Liste jedes Mal, wenn sie wächst, also ist die Anzahl der Growths O(log(n)) . Es sollte ziemlich effizient sein.

    
Mehrdad Afshari 22.01.2010 20:27
quelle
3

Zuerst sollten Sie es einfach auf die natürlichste, wartbarste und lesbarste Weise implementieren. In diesem Fall erstellen Sie einfach ein neues List<T> (akzeptieren die Standardkapazität) und fügen Ihre Objekte hinzu. Dann, was Sie tun, wenn Ihre Anwendung nicht Ihren Leistungsspezifikationen entspricht, profilieren Sie es. Wenn es durch Profiling herauskommt, dass dies ein Engpass in Ihrer Anwendung ist, dann versuchen Sie, es zu optimieren. Wenn Ihre Anwendung Ihren Leistungsspezifikationen entspricht oder dieser Teil kein Engpass ist, ignorieren Sie ihn.

Zweitens sind manchmal Details zur Implementierung wichtig, und hier ist ein Fall, in dem dies der Fall ist. Die Art, wie List<T> implementiert wird, ist ein dynamisch wachsendes Array, das mit einer bestimmten Kapazität beginnt und die Größe jedes Mal verdoppelt, wenn das erneute Wachstum benötigt wird. Das heißt, wenn Sie n object zu einer neu erstellten Liste hinzufügen, wird O(log n) regrowths und Sie werden höchstens O(n) space verschwenden. Wenn der Speicher auf Ihrem System nicht knapp ist (vielleicht betreiben Sie .NET CF auf einem Mobiltelefon), ist das keine große Sache. Und aus Performance-Sicht verbraucht das Parsen Ihrer Einträge wahrscheinlich wesentlich mehr Zeit als das Neuwachstum. Daher ist dies wahrscheinlich auch kein Faktor.

    
jason 22.01.2010 20:35
quelle
0

Wenn Sie bedenken, dass Ihre Liste anfangs klein ist, sollten Sie sie besser nicht initialisieren. Dadurch wird der Code leichter lesbar, ohne dass es zu spürbaren Leistungseinbußen kommt.

    
Dustin E 22.01.2010 20:32
quelle
0

Zuallererst sei gesagt, ich bin nicht an einem solchen Ort, um eine Antwort zu schreiben, ich bin zuerst gekommen, um es zu finden, doch ich schreibe eine, nur um zu empfehlen, und auch Ihre Meinung zu bekommen.

Was macht eine Liste beim Hinzufügen von Daten:

%Vor%

Wenn man das zuerst anschaut, tut es genau das, was einige von euch gesagt haben. Es verdoppelt die Kapazität und im Gegensatz zu anderen, und auch anders als die Art, wie Arrays funktionieren, blockiert es den Benutzer nicht, wenn er die angegebene Kapazität erreicht .

Und wann erhöht sich die Kapazität? In dieser Zeile: Capacity = newCapacity; ; Tatsächlich ist es der Capacity Property Setter, der die Operationen ausführt:

%Vor%

Es ist offensichtlich, dass es keine einfache Flag-Änderung ist, um mehr Elemente hineinzulassen, als die verknüpfte Liste (um ehrlich zu sein, ich betrachte Listen immer als LinkedList.) Jetzt kann ich mit der Liste sagen, dass ich die Leistung besser lesen kann , und weniger Schreibleistung (aber ich bin mir nicht sicher, was ich sage, jemand bestätigt, wenn wir LinkedList verwenden sollten, wenn wir Schreib- und einmalige Leseoperationen durchführen ...)). Wie wir sehen können, erstellt es ein neues Array und kopiert Elemente nacheinander in die neue Liste ...

Also hier ist mein Vorschlag:

  1. Wie @jason sagte, brauchen wir nicht daran zu denken, einen Wert zu übergeben, wenn wir unsere Schreiboperation nur einmal in die Liste
  2. ausführen dürfen
  3. Wenn das Gewicht der Liste klein ist, wird zum Beispiel nur ein paar Wiederholungen der Listengröße nicht viel bewirken, zum Beispiel wie alle sagten, wenn es 2 wird 4 und 8 ... zuerst ist es nur die dreifache Zeit dass wir die Größe erhöhen, und zweitens kopieren wir nur ein paar Daten. wieder können wir es ignorieren, egal wo der Code platziert wird, oder ich hoffe es.
  4. Aber wenn Sie einige tausend Daten von db kopieren, und es von Anfang an beginnt, 2- & gt; 4- & gt; 8- & gt; 16- & gt; 32- & gt; 64- & gt; 128- & gt; 256- & gt; 512- & gt; 1024 & gt; 2048 & gt; ... Bis wir wissen, dass wir die Array-Größe zehn Mal erhöht haben, und wenn wir glauben, dass eine Kopie nur eine einzige Operation ist, die Referenz kopiert, haben wir von den anderen wenigen Dingen, die in Maschinencodes erledigt werden müssen, 4094 Zeit Array zu einem anderen, und verbrauchen auch die Hälfte des Platzes, die auf GC gewartet werden müssen (in der grafischen Anwendung RAM kann Materie werden, aber es ist zu viel für mich, um Beispiel zu schreiben) ... Wenn Sie also die Anzahl der Operationen multiplizieren, die denselben Code zur gleichen Zeit aufrufen, kann sich die Leistung drastisch verringern. Also kann ich Folgendes tun: Wenn ich eine Zahl kenne, zum Beispiel weiß ich, dass ich x Element habe, und dieses Element kann sich auf 0 ~ 2 beziehen, kann ich das x oder x * 2 übergeben, und es wird nur einmal wachsen wenn benötigt. (Bitte sagen Sie mir Ihre Meinung).

  5. In Ergänzung zu Idee Nr. 3 Die Verdopplung scheint für jede einzelne Liste vernünftig zu sein, und egal, was Sie tun, Sie können nur die Hälfte der Zeit aufstocken und die gesamte Operation wird nur dauern ~ zwei dieser Hälften, so dass Sie es ignorieren können, wenn Sie nicht mehrere Threads / Aufgaben zur gleichen Zeit oder viele Listen nacheinander starten.

Ich finde auch nur heraus: private const int _defaultCapacity = 4;

Hinweis: Wenn Sie die maximale Kapazität verwenden, wird für 2G-Elemente Speicherplatz in Höhe der Menge benötigt (wie gesagt: // Allow the list to grow to maximum possible capacity (~2G elements) before encountering overflow. ), und das ist nicht der Betrag, den Sie haben Willst du deine Liste initialisieren, selbst wenn dein Code einmal ausgeführt wird, sieht es zu sehr aus geraden (linearen / Side-by-Side) Daten innerhalb des RAM aus (wie die Datenstruktur uns dachte, wenn C # nichts Neues getan hat) unsere Bücher sagten) und die Zuordnung kann auch irgendwann erfordern (mir ist dieser Prozess nicht bekannt). also ich empfehle es nie, wenn Sie nicht wissen, wie das wirklich so viel erforderlich ist, und ich denke, in solchen Zeiten sollten wir auch eine verkettete Liste betrachten, wenn die Daten wirklich linear sind, und es kann viel Platz in RAM genommen werden zufällige Orte (wenn das der Fall ist: das erfordert viele Überprüfungen, bevor die Maschine einen Platz finden kann, um diesen Raum zuzuweisen).

    
deadManN 17.12.2017 08:46
quelle
-1

Wahrscheinlich ist der beste Kompromiss ein Kompromiss. Initialisiere die Liste auf etwa 256.

    
ChaosPandion 22.01.2010 20:27
quelle

Tags und Links