Warum wird verdoppelt Vektor-Array?

Question

Warum wird die klassische Implementierung von Vector (Arraylist für Java Personen) verdoppelt seine interne Array-Größe auf jeder Expansion statt Verdreifachung oder Vervierfachung es?

Answer 1

Wenn die durchschnittliche Zeit, die Berechnung in einen Vektor einzufügen, müssen Sie für die nicht-wachsenden Einsätze und die wachsenden Einsätze ermöglichen.

, um die Gesamtzahl der Operationen Aufruf einzufügen n Artikel o _total , und die durchschnittliche o _Durchschnitt .

Wenn Sie einfügen n Artikel und Sie wachsen um einen Faktor von A nach Bedarf, dann gibt es o _total = n + & Sgr; A ⁱ [0 A n] Operationen. Im schlimmsten Fall, dass Sie mit 1 / A der zugewiesenen Speicher.

Intuitiv, A = 2 bedeuten im schlimmsten Fall haben Sie o _total = 2n , so o _Durchschnitt ist O (1), und der schlimmste Fall, dass Sie verwenden 50% der zugewiesenen Speicher.

Für eine größere A , Sie haben eine niedrigere o _total , aber verschwendeten Speicher.

Für eine kleinere A , o _total ist größer, aber Sie nicht so viel Speicherplatz verschwenden. Solange es geometrisch wächst, es ist immer noch O (1) Einsetzen Zeit amortisiert, aber die Konstante höher erhalten.

Für Wachstumsfaktoren 1,25 (rot), 1,5 (Cyan), 2 (schwarz), 3 (blau) und 4 (grün) zeigt dieser Diagramme Punkt und durchschnittliche Größe Effizienz (Verhältnis von Größe / zugewiesenen Platz, mehr ist besser ) auf der linken und der Zeiteffizienz (das Verhältnis von Einfügungen / Operationen, mehr ist besser) auf der rechten Seite für 400.000 Elemente eingefügt wird. 100% Flächeneffizienz ist für alle Wachstumsfaktoren unmittelbar vor dem Ändern der Größe erreicht; der Fall für A = 2 zeigt die Zeiteffizienz zwischen 25% und 50% und Raumeffizienz etwa 50%, was für die meisten Fälle gut ist:

Laufzeiten, wie beispielsweise Java, Arrays werden mit Nullen gefüllt, so dass die Anzahl der Operationen ist zuzuteilen proportional zur Größe des Arrays. Unter Berücksichtigung ergibt dies reduziert die Differenz zwischen der Zeiteffizienz Schätzungen:

Answer 2

Exponentiell die Größe des Arrays zu verdoppeln (oder String) ist ein guter Kompromiss zwischen mit genügend Zellen in dem Array und verschwenden zu viel Speicher.

Sagen wir mit 10 Elementen beginnen:

1 - 10
2-20
3-40
4-80
5-160

Wenn wir die Größe verdreifachen, 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 verdreifachen würden Sie vielleicht tun es 7 oder 8 mal - die Common Language Runtime-Hit einer Neuverteilung dieses paar Mal ist ausreichend klein, um sich Sorgen zu machen, aber sie sind eher vollständig die erforderliche Größe überschreiten

.

Answer 3

Wenn Sie einen ungewöhnlichen großer Speicherblock zuzuordnen sind, dann, wenn dieser Block freigegeben wird (entweder weil Sie es sind Ändern der Größe oder es wird GC'd) gäbe es ein ungewöhnliches großes Loch in Erinnerung sein, das dazu führen könnte, Kopfschmerzen für die Speicher-Manager. So ist es in der Regel bevorzugt Speicher in Zweierpotenzen zuzuteilen. In einigen Fällen werden die zugrunde liegenden Speicher-Manager geben Ihnen nur Blöcke bestimmter Größen, und wenn Sie eine seltsame Größe fordern wird es auf die nächst größere Größe aufrunden. Also anstatt für 470 Einheiten zu fragen, immer wieder 512 sowieso, und dann wieder Ändern der Größe, wenn Sie all 470 verwendet haben, die Sie gefragt haben, könnte genauso gut nur für 512 fragen zu beginnen.

Answer 4

Jede mehrere ist ein Kompromiss. Machen Sie es zu groß und Sie zu viel Speicher verschwenden. Machen Sie es zu klein und Sie viel Zeit für Umschichtungen und Kopieren verschwenden. Ich denke, dass Verdoppelung gibt es, weil es funktioniert und ist sehr einfach zu implementieren. Ich sah auch eine proprietäre STL-ähnliche Bibliothek, die 1,5 als Multiplikator für das gleiche verwendet. - Ich denke, seine Entwickler betrachtet verdoppeln zu viel Speicher verschwenden

Answer 5

Wenn Sie über die Java-spezifische Implementierung fragen Arraylist , dann ist es nicht unbedingt auf jeder Expansion verdoppelt.

Von der Javadoc für Vector:

  

Jeder Vektor versucht das Speichermanagement zu optimieren, indem eine capacity und capacityIncrement aufrechterhalten wird. Die Kapazität ist immer mindestens so groß ist wie die Vektorgröße; es ist in der Regel größer, weil als Komponenten zu dem Vektor hinzugefügt werden, die Größe der capacityIncrement der Lagerung erhöht sich der Vektor in Stücke schneiden. Eine Anwendung kann die Fähigkeit eines Vektors erhöhen, bevor eine große Anzahl von Bauteilen einzufügen; Dies reduziert die Menge der inkrementellen Neuzuweisung.

Einer der Konstrukteure für Vector ermöglicht es Ihnen, die ursprüngliche Größe und Kapazität Anstieges für den Vektor angeben. Die Vector-Klasse bietet auch die ensureCapacity(int minCapacity) und setSize(int newSize), manuelle Anpassungen der Mindestgröße des Vektor und den Vektor auf eigener Faust zu ändern.

Die Arraylist-Klasse ist sehr ähnlich:

  

Jede ArrayList Instanz hat eine Kapazität. Die Kapazität ist die Größe der Anordnung verwendet, um die Elemente in der Liste zu speichern. Es ist immer mindestens so groß wie die Listengröße. Als Elemente zu einem Arraylist hinzugefügt werden, wächst ihre Fähigkeit, automatisch. Die Einzelheiten der Wachstumspolitik nicht über die Tatsache festgelegt, dass ein Element hinzugefügt wird konstant fortgeführten Anschaffungszeitkosten hat.

     

Eine Anwendung kann die Kapazität einer ArrayList Instanz erhöhen, bevor eine große Anzahl von Elementen mit dem ensureCapacity Betrieb hinzuzufügen. Dies kann die Menge der inkrementellen Neuzuteilung reduzieren.

Wenn Sie sich über die allgemeine Durchführung eines Vektors fragen, als die Wahl der Zunahme der Größe und wie viel ist ein Kompromiss. Im allgemeinen werden Vektoren, die durch Arrays gesichert. Arrays sind eine feste Größe. Um einen Vektor zu verkleinern, weil es voll Mittel ist, die Sie kopieren müssen alle Elemente eines Arrays in ein neues, größeres Array. Wenn Sie Ihr neues Array zu groß machen, dann haben Sie Speicher zugewiesen, die Sie nie verwenden. Wenn es zu klein ist, könnte es zu lange dauern, die Elemente aus dem alten Array in die neue, größere Array zu kopieren -. Eine Operation, die Sie nicht wollen, sehr oft durchführen

Answer 6

Ich persönlich denke, seine eine arbitriary Wahl. Wir konnten zwei Basen e statt Base verwenden (statt nur mehrere Größe verdoppelt durch (1 + e)).

Wenn Sie vorhaben, große Mengen von Variablen auf den Vektor werden, indem dann wäre es vorteilhaft, eine hohe Basis zu haben (die amnt von reduzieren Kopieren Sie tun werden.) Auf der anderen Seite, wenn Sie speichern werden müssen, nur wenige Mitglieder auf avg, dann eine niedrige Basis in Ordnung sein wird und die Menge an Overhead reduzieren, damit die Dinge zu beschleunigen.

Base 2 ist ein Kompromiss.

Answer 7

Es gibt keine Leistung Grund für die Verdoppelung vs Verdreifachung oder Vervierfachung wie die alle die gleichen großen O-Performance-Profile haben. Doch in absoluten Zahlen Verdoppelung wird dazu neigen, mehr Platz effizient im normalen Szenario zu sein.