Warum verdoppelt die klassische Implementierung von Vector (ArrayList for Java people) die interne Array-Größe bei jeder Erweiterung, anstatt sie zu verdreifachen oder zu vervierfachen?Warum ist Vektor-Array verdoppelt?
Bei der Berechnung der durchschnittlichen Zeit für das Einfügen in einen Vektor müssen Sie die nicht wachsenden Inserts und die wachsenden Inserts berücksichtigen.
Rufen Sie die Gesamtzahl der Operationen n Artikel o Gesamt und die durchschnittlichen o durchschnittlichen einzufügen.
Wenn Sie n Elemente einfügen, und Sie um einen Faktor von A wachsen je nach Bedarf, dann gibt es o Gesamt = n + Σ A i [0 < i < 1 + ln A n] Operationen. Im schlimmsten Fall verwenden Sie 1/A des zugeordneten Speichers.
Intuitiv A = 2 bedeutet schlimmsten Sie o Gesamt = 2n, so o durchschnittliche ist O (1), und der ungünstigste Fall verwenden Sie 50% der zugewiesenen Speicher .
Für eine größere A, haben Sie eine niedrigere o Gesamt, aber mehr verschwendet Speicher.
Für eine kleinere A, o Gesamt größer ist, aber Sie haben nicht so viel Speicherplatz verschwenden. Solange es geometrisch wächst, ist es immer noch O (1) amortisiert Insertionszeit, aber die Konstante wird höher.
Für die Wachstumsfaktoren 1,25 (rot), 1,5 (cyan), 2 (schwarz), 3 (blau) und 4 (grün) zeigen diese Diagramme die Punkt- und Durchschnittsgrößeneffizienz (Verhältnis von Größe/zugewiesenem Platz; mehr ist besser) auf der linken Seite und Zeiteffizienz (Verhältnis von Einfügungen/Operationen; mehr ist besser) auf der rechten Seite für das Einfügen von 400.000 Artikeln. 100% Raumeffizienz wird für alle Wachstumsfaktoren kurz vor der Größenänderung erreicht; der Fall für A = 2 zeigt Zeitwirkungsgrad zwischen 25% und 50%, und die Raumeffizienz etwa 50%, was für die meisten Fälle gut ist:
Für Laufzeiten, wie beispielsweise Java, Arrays Null sind gefüllt, so dass die Anzahl der zuzuteilenden Operationen proportional zur Größe des Arrays ist. Unter Berücksichtigung dieser die Differenz zwischen den Zeiteffizienz Schätzungen ergibt reduziert:
Ich habe Ihre Antwort hochgestuft, würde Ihnen aber vorschlagen, zu prüfen, wie oft sich jedes Objekt in einer Sammlung verschoben hat, wenn es knapp unter das für eine Erweiterung erforderliche Niveau gestopft ist. Mit einem Wachstumsfaktor von k hat sich nur 1/k der Objekte nur einmal bewegt, 1/k^2 hat sich mindestens zweimal bewegt, 1/k^3 hat sich dreimal bewegt usw., also die durchschnittliche Anzahl von Zeiten, in denen sich jedes Datenelement in 'n'-Erweiterungen bewegt, wird 1/k + 1/k^2 + 1/k^3 + ... 1/k^n sein, was eine begrenzte geometrische Reihe ist. – supercat
Sieht so aus, als wären die Bilder, die für diese Antwort aufgenommen wurden, jetzt Anzeigen für imageshack. Hast du sie noch irgendwo? – CCovey
Die exponentielle Verdopplung der Größe des Arrays (oder der Zeichenfolge) ist ein guter Kompromiss zwischen genügend Zellen im Array und zu viel Speicher zu verschwenden.
sagen wir mit 10 Elementen beginnen:
1 - 10
2-20
3-40
4-80
5 - 160
Wenn wir die dreifache Größe, wir wachsen zu schnell
1 - 10
2 - 30
3-90
4-270
5 - 810
In der Praxis würden Sie vielleicht 10 oder 12 mal wachsen. Wenn Sie sich verdreifachen, würden Sie es vielleicht 7 oder 8 Mal tun - der Runtime-Hit für die Neuzuordnung ist diese wenigen Male ausreichend klein, um sich Sorgen zu machen, aber Sie werden wahrscheinlich die erforderliche Größe vollständig überschreiten.
Ok, aber dann könnte man argumentieren, dass der Vektor sich zu einem weiteren Element erweitern oder um die Hälfte der Elemente erweitern könnte. Gibt es einen besonderen Grund, es zu verdoppeln? – TheOne
Wenn Ihre aktuelle Größe 1.000.000 Zellen beträgt, scheint das Kopieren und Kopieren sehr teuer zu sein. – TheOne
Wenn Sie sich verdoppeln, verlieren Sie garantiert ** am meisten ** die Menge an Speicher, die Sie verwenden möchten. Der Punkt, an dem Sie exponentiell wachsen, ist, dass Sie gar nicht wachsen müssen, wenn Sie in der Nähe der Zielgröße sind. –
Wenn Sie nach der Java-spezifischen Implementierung von Vector und ArrayList fragen, wird diese nicht unbedingt bei jeder Erweiterung verdoppelt.
Von der Javadoc für Vector:
Jeder Vektor versucht das Speichermanagement zu optimieren, indem eine
capacityundcapacityIncrementaufrechterhalten wird. Die Kapazität ist immer mindestens so groß wie die Vektorgröße; Es ist normalerweise größer, da, wenn Komponenten zum Vektor hinzugefügt werden, der Speicher des Vektors in Blöcken der GrößecapacityIncrementanwächst. Eine Anwendung kann die Kapazität eines Vektors vor dem Einfügen einer großen Anzahl von Komponenten erhöhen. Dies reduziert die Menge der inkrementellen Neuzuweisung.
Mit einem der Konstruktoren für Vector können Sie die anfängliche Größe und das Kapazitätsinkrement für den Vector festlegen. Die Vector-Klasse bietet auch die ensureCapacity(int minCapacity) und setSize(int newSize), für manuelle Anpassungen der Mindestgröße des Vector und die Größe des Vektors selbst ändern.
Die Arraylist-Klasse ist sehr ähnlich:
Jede
ArrayListInstanz eine Kapazität hat. Die Kapazität entspricht der Größe des Arrays, das zum Speichern der Elemente in der Liste verwendet wird. Es ist immer mindestens so groß wie die Listengröße. Wenn Elemente zu einer ArrayList hinzugefügt werden, wird ihre Kapazität automatisch erhöht. Die Details der Wachstumspolitik sind nicht über die Tatsache hinaus spezifiziert, dass das Hinzufügen eines Elements konstante amortisierte Zeitkosten hat.Eine Anwendung kann die Kapazität einer
ArrayListInstanz erhöhen, bevor eine große Anzahl von Elementen mit der Operation 'sureCapacity' hinzugefügt wird. Dies kann den Umfang der inkrementellen Neuzuweisung verringern.
Wenn Sie nach der allgemeinen Implementierung eines Vektors fragen, dann ist die Wahl der Größenzunahme und wie viel ein Kompromiss ist. Im Allgemeinen werden Vektoren durch Arrays unterstützt. Arrays haben eine feste Größe. Um die Größe eines Vektors zu ändern, weil er voll ist, müssen Sie alle Elemente eines Arrays in ein neues, größeres Array kopieren. Wenn Sie Ihr neues Array zu groß machen, haben Sie Speicher zugewiesen, den Sie nie verwenden werden. Wenn es zu klein ist, kann es zu lange dauern, die Elemente aus dem alten Array in das neue, größere Array zu kopieren - eine Operation, die Sie nicht sehr oft durchführen möchten.
Es gibt keinen Leistungsgrund für die Verdoppelung gegenüber der Verdreifachung oder Vervierfachung, da alle die gleichen großen O-Leistungsprofile haben. In absoluten Zahlen wird die Verdoppelung jedoch im normalen Szenario eher platzsparend sein.
Wenn Sie einen Speicherblock mit einer ungewöhnlichen Größe zuweisen würden, dann würde dieser Block, wenn er freigegeben wird (entweder weil Sie die Größe ändern oder er GC'd), ein ungewöhnlich großes Loch im Speicher haben Kopfschmerzen für den Speichermanager verursachen. Daher wird es normalerweise bevorzugt, Speicher in Potenzen von zwei zu reservieren. In einigen Fällen gibt der zugrunde liegende Speichermanager nur Blöcke bestimmter Größe, und wenn Sie eine seltsame Größe anfordern, wird es auf die nächste größere Größe aufgerundet. Anstatt also nach 470 Einheiten zu fragen, 512 sowieso zurückzubekommen und dann die Größe wieder zu ändern, nachdem Sie alle 470 verwendet haben, nach denen Sie gefragt haben, können Sie auch einfach nach 512 fragen.
Ich stimme dieser Antwort nicht zu. Ich bin nicht sicher, dass es "warum nicht durch 3 oder 4 oder 5 Wachstumsrate" antwortet.Es beantwortet eine etwas andere Frage (warum Speicher auf Zweiergrenzen zuweisen?). –
Es ist sicherlich nicht die, die ich ausgewählt hätte. Ich dachte darüber nach als ergänzende Antwort. Zusätzlich zu den anderen gut erklärten Gründen für die Wachstumsrate verschwenden Sie Ressourcen, wenn das neue Array keine Zweierpotenz ist. In Anbetracht der anderen Argumente, warum ein größerer Multiplikator nicht gut wäre, ist die einzige Potenz von Zwei, die gut passt, 2. Es setzt natürlich voraus, dass die ursprüngliche Größe natürlich auch eine Zweierpotenz ist, aber ich denke am meisten Vektor Klassen versuchen das zu arrangieren. – kwatford
Rechts. "stimme nicht zu" war wahrscheinlich ein bisschen stark :) Außerdem könntest du definitiv einen Algorithmus entwickeln, um dir ungefähr 1,5 Wachstum zu verschaffen, das immer noch dafür sorgt, dass du wortgerecht bist. Wenn ein Byte-Array 64 Byte lang ist, können Sie ihm 32 Byte hinzufügen und die Wortausrichtung beibehalten. –
Persönlich halte ich es für eine Schiedsgerichtsbarkeit. Wir könnten Base e anstelle von Base 2 verwenden (anstatt nur multiple Größe durch (1 + e) zu verdoppeln).
Wenn Sie dem Vektor große Mengen an Variablen hinzufügen möchten, wäre es vorteilhaft, a zu haben high base (um den Kopieraufwand zu reduzieren). Auf der anderen Seite, wenn Sie nur ein paar Mitglieder auf avg speichern müssen, dann ist eine niedrige Basis ausreichend und reduziert den Overhead und beschleunigt somit die Dinge .
Basis 2 ist ein Kompromiss.
Jedes Mehrfaches ist ein Kompromiss. Mach es zu groß und du verschwendest zu viel Speicher. Machen Sie es zu klein und Sie verschwenden viel Zeit für Neuzuweisungen und Kopieren. Ich denke, dass Verdoppeln da ist, weil es funktioniert und sehr einfach zu implementieren ist. Ich sah auch eine proprietäre STL-ähnliche Bibliothek, die 1.5 als Multiplikator für die gleiche verwendet - ich denke, dass ihre Entwickler in Betracht gezogen haben, doppelt zu viel Speicher zu verschwenden.
Sie könnten auch fragen sich, warum vermehren sie nicht von 1.5? Oder 1.8 usw.? (Sie könnten mit 1,5 multiplizieren und dann auf die nächstgrößere ganze Zahl runden.) – Peter
+1 Große Frage. –