Was ist die ideale Wachstumsrate für einen dynamisch zugewiesenen Array?

https://stackoverflow.com/questions/1100311

11-09-2019
|

Frage

C ++ hat std :: vector und Java hat Arraylist und viele andere Sprachen haben ihre eigene Form der dynamisch zugewiesenen Arrays. Wenn ein dynamisches Array aus dem Raum läuft, wird es in einen größeren Bereich und die alten Werte werden in das neue Array kopiert umverteilt. Eine Frage von zentraler Bedeutung für die Leistung einer solchen Anordnung ist, wie schnell das Array in der Größe wächst. Wenn Sie immer nur groß genug wachsen, um die aktuelle Push-to-fit, werden Sie jedes Mal eine Umschichtung enden. So macht es Sinn, die Array-Größe zu verdoppeln oder multiplizieren sie mit etwa 1,5-fach.

Gibt es einen idealen Wachstumsfaktor? 2x? 1.5x? Durch die ideale meine ich mathematisch gerechtfertigt, beste Ausgleichsleistung und verschwendet Speicher. Ich weiß, dass theoretisch, da Ihre Anwendung eine mögliche Verteilung haben könnte schiebt, dass diese etwas Anwendung abhängt. Aber ich bin neugierig zu wissen, ob es ein Wert ist, die „in der Regel“ am besten ist, oder gilt als am besten innerhalb einer strengen Einschränkung.

Ich habe gehört, es gibt ein Papier zu diesem irgendwo, aber ich habe es nicht gelungen, es zu finden.

Lösung

Es wird ganz auf den Anwendungsfall abhängen. Möchten Sie mehr über die Zeit verschwendet Pflege Kopieren von Daten um (und Neuzuweisung Arrays) oder dem zusätzlichen Speicher? Wie lange wird das Array dauern? Wenn es nicht mehr lange sein würde, einen größeren Puffer gut eine gute Idee sein kann - die Strafe ist von kurzer Dauer. Wenn es geht zu hängen, um (zum Beispiel in Java, ging in ältere und älteren Generationen), das ist offensichtlich eher eine Strafe.

Es gibt nicht so etwas wie einen „idealen Wachstumsfaktor.“ Es ist nicht nur theoretisch abhängig von der Anwendung, es ist auf jeden Fall Anwendung abhängig.

2 ist ein ziemlich häufiger Wachstumsfaktor - ich bin ziemlich sicher, das ist, was ArrayList und List<T> in .NET verwendet. ArrayList<T> in Java verwendet 1.5.

EDIT: Wie Erich weist darauf hin, Dictionary<,> in .NET verwendet „doppelt so groß wie dann auf die nächste Primzahl erhöhen“, so dass Hash-Werte einigermaßen zwischen Eimer verteilt werden können. (Ich bin sicher, ich habe was darauf hindeutet, vor kurzer Dokumentation gesehen, dass Primzahlen ist nicht wirklich so toll für die Verteilung Hash-Eimers, aber das ist ein Argument für eine andere Antwort.)

Andere Tipps

Ich erinnere mich, das Lesen vor vielen Jahren, warum 1.5 über zwei bevorzugt wird, zumindest bis C angewendet ++ (dies wahrscheinlich nicht auf verwaltete Sprachen gilt, wo das Laufzeitsystem Objekte nach Belieben verschieben kann).

Die Begründung ist dies:

Sagen Sie bitte mit einer 16-Byte-Zuordnung starten.
Wenn Sie mehr benötigen, können Sie 32 Byte zuzuweisen, und 16 Bytes frei. Dies läßt ein 16-Byte-Loch im Speicher.
Wenn Sie mehr benötigen, ordnen Sie 64 Bytes, die 32 Bytes frei. Dies läßt ein 48-Byte-Loch (wenn die 16 und 32 wurden benachbarte).
Wenn Sie mehr benötigen, ordnen Sie 128 Bytes, die 64 Bytes frei. Dies läßt ein 112-Byte-Loch (vorausgesetzt, alle vorherigen Zuteilungen benachbart sind).
Und so und und so weiter.

Die Idee ist, dass mit einer 2-fach Erweiterung, gibt es keinen Punkt in der Zeit, dass das resultierende Loch immer groß genug sein wird für die nächste Zuteilung wieder zu verwenden. Mit einer 1,5-fach Zuweisung haben wir diese statt:

Starten Sie mit 16 Byte.
Wenn Sie mehr benötigen, 24 Byte zuzuweisen, und die 16 freizugeben, ein 16-Byte-Loch verlassen.
Wenn Sie mehr benötigen, 36 Byte zuzuweisen, und die 24 freizugeben, ein 40-Byte-Loch verlassen.
Wenn Sie mehr benötigen, 54 Byte zuzuweisen, und die 36 freizugeben, ein 76-Byte-Loch verlassen.
Wenn Sie mehr benötigen, 81 Bytes zuzuweisen, und die 54 freizugeben, eine 130-Byte-Loch verlassen.
Wenn Sie mehr benötigen, verwenden 122 Bytes (Aufrundung) aus dem 130-Byte-Loch.

Im Idealfall (im Grenzfall als n → ∞), es ist das goldene Verhältnis : φ = 1,618 ...

In der Praxis Sie wollen etwas in der Nähe, wie 1.5.

Der Grund dafür ist, dass Sie in der Lage sein wollen, ältere Speicherblöcke wieder zu verwenden, die Vorteile des Caching zu nehmen und vermeiden ständig das Betriebssystem macht Ihnen mehr Speicherseiten. Die Gleichung würden Sie lösen diese zu , um sicherzustellen, reduziert x ^{n - 1} - 1 = x ^{n + 1} - x ⁿ, deren Lösungsansätze x = φ für große n .

Ein Ansatz, wenn Fragen wie diese zu beantworten ist, einfach „betrügen“ und schauen, was populäre Bibliotheken tun, unter der Annahme, dass eine weit verbreitete Bibliothek ist, zumindest, nicht etwas Schreckliches tun.

So einfach sehr schnell überprüft, Rubin (1.9.1-p129) erscheint 1.5x zu verwenden, wenn auf ein Array anhängt, und Python (2.6.2) verwendet 1.125x plus eine Konstante (in Objects/listobject.c ):

/* This over-allocates proportional to the list size, making room
 * for additional growth.  The over-allocation is mild, but is
 * enough to give linear-time amortized behavior over a long
 * sequence of appends() in the presence of a poorly-performing
 * system realloc().
 * The growth pattern is:  0, 4, 8, 16, 25, 35, 46, 58, 72, 88, ...
 */
new_allocated = (newsize >> 3) + (newsize < 9 ? 3 : 6);

/* check for integer overflow */
if (new_allocated > PY_SIZE_MAX - newsize) {
    PyErr_NoMemory();
    return -1;
} else {
    new_allocated += newsize;
}

newsize oben ist die Anzahl der Elemente in dem Array. Beachten Sie auch, dass newsize hinzugefügt new_allocated, so dass der Ausdruck mit den bitshifts und ternärem Operator ist wirklich nur die Überzuteilung berechnet wird.

Angenommen, Sie haben die Größe des Arrays von x wachsen. So übernehmen Sie mit Größe T starten. Das nächste Mal, wachsen Sie das Array seine Größe T*x wird. Dann wird es T*x^2 und so weiter werden.

Wenn Ihr Ziel in der Lage ist, den Speicher wieder zu verwenden, die vorher erstellt wurde, dann wollen Sie sicherstellen, dass der neue Speicher, den Sie zuzuordnen ist kleiner als die Summe der früheren Speicher Sie ausgeplant. Deshalb haben wir diese Ungleichung:

T*x^n <= T + T*x + T*x^2 + ... + T*x^(n-2)

Wir können T von beiden Seiten entfernen. Also das wir bekommen:

x^n <= 1 + x + x^2 + ... + x^(n-2)

Informell, was wir sagen, ist, dass bei nth Zuteilung wollen wir unsere alle bisher ausgeplant Speicher größer oder gleich den Speicherbedarf bei der n-ten Zuteilung, so dass wir die zuvor ausgeplant Speicher wiederverwenden können.

Zum Beispiel, wenn wir wollen in der Lage sein, dies im dritten Schritt zu tun (das heißt, n=3), dann haben wir

x^3 <= 1 + x

Diese Gleichung gilt für alle x, so dass 0 < x <= 1.3 (grob)

Sehen Sie, was wir x für verschiedene bekommen n ist unter:

n  maximum-x (roughly)

3  1.3

4  1.4

5  1.53

6  1.57

7  1.59

22 1.61

Beachten Sie, dass der wachsende Faktor kleiner sein muss als 2 seit x^n > x^(n-2) + ... + x^2 + x + 1 for all x>=2.

Es hängt wirklich davon. Manche Menschen analysieren gemeinsam genutzte Anwendungsfälle die optimale Anzahl zu finden.

Ich habe 1,5x 2,0x phi x gesehen und Potenz von 2 verwendet, vor.

Wenn Sie eine Verteilung über Array Längen haben, und Sie haben eine Nutzenfunktion, die besagt, wie viel Sie Raum wie verschwenden vs. Zeit zu verschwenden, können Sie auf jeden Fall eine optimale Größenanpassung wählen (und erste Sizing) Strategie.

Der Grund für die einfache Konstante mehr verwendet wird, ist offensichtlich so, dass jeder konstante Zeit amortisierte hängen hat. Aber das bedeutet nicht, dass Sie nicht ein anderes (größeres) Verhältnis für kleine Größen verwenden können.

In Scala können Sie loadFactor für die Standardbibliothek Hash-Tabellen mit einer Funktion überschreiben, die an der aktuellen Größe sieht. Merkwürdig ist, verdoppeln die Größe veränderbare Arrays nur, was die meisten Menschen in der Praxis zu tun.

Ich weiß nicht, jede Verdoppelung (oder 1,5 * ing) Arrays, die tatsächlich aus Speicherfehler fangen und wachsen weniger in diesem Fall. Es scheint, dass, wenn Sie einen großen einzelnen Array haben, würden Sie das tun wollen.

Ich würde weiter hinzufügen, dass, wenn Sie die Größe veränderbare Arrays zu halten sind schon lange genug, und du Raum im Laufe der Zeit bevorzugen, könnte es sinnvoll, dramatisch overallocate (für die meisten Fälle) zunächst und dann genau die richtige Größe neu zuteilen, wenn Sie sind fertig.

ich mit Jon Skeet zustimmen, selbst besteht darauf, meine theorycrafter Freund, dass dies erwiesen werden kann O (1), wenn der Faktor Einstellung auf 2x.

Das Verhältnis zwischen CPU-Zeit und Speicher unterscheidet sich auf jeder Maschine, und so wird der Faktor nur so viel variieren. Wenn Sie eine Maschine mit Gigabyte RAM und eine langsame CPU, in ein neues Array die Elemente Kopieren ist viel teurer als auf einer schnellen Maschine, die wiederum haben könnten weniger Speicher. Es ist eine Frage, die in der Theorie beantwortet werden kann, für einen einheitlichen Computer, die in realen Szenarien überhaupt helfen Ihnen tun.

Ich weiß, es ist eine alte Frage, aber es gibt einige Dinge, die jeder zu fehlen scheint.

Erstens ist dies die Multiplikation mit 2: Größe << 1. Dies ist die Multiplikation mit alles zwischen 1 und 2: int (float (Größe) * x), wobei x die Anzahl der * ist Gleitkomma math, und der Prozessor hat zusätzliche Anweisungen zum Gießen zwischen Schwimmer und int auszuführen. Mit anderen Worten, auf der Maschinenebene, Verdoppelung nimmt eine einzelne, sehr schnelle Anweisung die neue Größe zu finden. Multipliziert man durch etwas zwischen 1 und 2 erfordert mindestens eine Befehlsgröße auf einen Schwimmer zu werfen, multiplizieren Sie einen Befehl (der Schwimmer Multiplikation, so dass es wahrscheinlich mindestens doppelt so viele Zyklen dauert, wenn nicht 4 oder sogar 8-mal so viele), und eine Anweisung zu werfen, in int zurück und geht davon aus, dass Ihre Plattform Schwimmer Mathematik auf den Universalregister durchführen können, anstatt den Einsatz von speziellen Register erforderlich ist. Kurz gesagt, sollten Sie die Mathematik für jede Zuordnung erwarten, dass mindestens 10-mal so lang wie eine einfache Linksverschiebung zu nehmen. Wenn Sie jedoch eine Menge von Daten während der Neuzuweisung kopieren, könnte dies nicht viel Unterschied machen.

Zweitens, und wahrscheinlich die großen Kicker: Jeder scheint anzunehmen, dass der Speicher, die freigegeben wird, sowohl mit sich selbst angrenzt, sowie angrenzend an die neu zugewiesenen Speicher. Es sei denn, Sie sind alle aus dem Speicher Vorbelegen selbst und dann als Pool verwendet, ist dies mit ziemlicher Sicherheit nicht der Fall. Das O könnte gelegentlich am Ende dieses up zu tun, aber die meiste Zeit, es wird genügend freie Speicherplatz Fragmentierung sein, dass jedes halbwegs ordentlichen Speicherverwaltungssystem in der Lage sein wird, ein kleines Loch, wo Ihr Gedächtnis wird finden nur fit. Sobald Sie wirklich Brocken bekommen gebissen, sind Sie eher mit zusammenhängenden Stücke am Ende, aber dann sind Ihre Zuweisungen groß genug, dass man sie nicht oft genug tun, denn es mehr Materie. Kurz gesagt, ist es Spaß, dass mit einiger idealen Zahl vorstellbar wird der effizienteste Nutzung von freier Speicherplatz, aber in Wirklichkeit ermöglichen, ist es nicht passieren, es sei denn Ihr Programm auf blankes Metall ausgeführt wird (wie in, gibt es keine OS darunter alle der Entscheidungen).

Meine Antwort auf die Frage? Nein, es gibt keine ideale Zahl. Es ist so anwendungsspezifische, dass niemand wirklich einmal versucht. Wenn Ihr Ziel ist ideal Speichernutzung ist, sind Sie ziemlich viel Glück. Für Leistung, weniger häufig Zuweisungen besser, aber wenn wir gingen nur mit, dass, könnten wir von 4 oder sogar 8 multiplizieren! Natürlich, wenn Firefox verwenden, 1GB zu 8GB in einem Schuss springt, beschweren wollen Menschen, so dass nicht einmal Sinn machen. Hier sind einige Faustregeln ich gehen würde durch obwohl:

Wenn Sie nicht die Speichernutzung optimieren, zumindest nicht Prozessorzyklen verschwenden. Multipliziert mit 2 mindestens eine Größenordnung schneller als Gleitkomma-Mathematik zu tun. Es ist vielleicht nicht einen großen Unterschied machen, aber es wird einigen Unterschied zumindest (besonders früh auf, während der häufigeren und kleinere Zuordnungen) machen.

Sie es nicht überdenken. Wenn Sie nur 4 Stunden damit verbracht, herauszufinden, wie etwas zu tun, das bereits geschehen ist, können Sie Ihre Zeit nur verschwendet. Völlig ehrlich, wenn es eine bessere Option ist als * 2, wäre es vor in der C ++ Vektor-Klasse (und viele anderen Orten) Jahrzehnte getan hat.

Schließlich, wenn Sie wirklich wollen, optimieren Sie die kleinen Dinge nicht schwitzen. Jetzt Tage, kümmert sich niemand um 4 KB Speicher verschwendet, es sei denn, sie auf Embedded-Systemen arbeiten. Wenn Sie zu 1 GB Objekte erhalten, die jeweils zwischen 1 MB und 10 MB sind, ist Verdoppelung wahrscheinlich viel zu viel (ich meine, dass zwischen 100 und 1.000 Objekte). Wenn Sie Expansionsrate erwartete Schätzung können, können Sie es Ebene an einem bestimmten Punkt zu einer linearen Wachstumsrate aus. Wenn Sie etwa 10 Objekte pro Minute erwarten, wächst dann bei 5 bis 10 Objektgrößen pro Schritt (einmal alle 30 Sekunden bis eine Minute) ist probably in Ordnung.

Was es ankommt, ist, glaube es nicht über, optimieren, was Sie können, und passen Sie auf Ihre Bewerbung (und Plattform), wenn Sie müssen.

Weitere zwei Cent

Die meisten Computer haben den virtuellen Speicher! Im physischen Speicher können Sie zufällige Seiten überall haben, die als einzigen zusammenhängenden Raum angezeigt werden, in Ihrem Programm der virtuellen Speicher. Die Lösung des indirection wird von der Hardware durchgeführt. Virtueller Speicher erschöpft war ein Problem, auf 32-Bit-Systemen, aber es ist wirklich kein Problem mehr. So füllen Sie die Loch ist kein Problem mehr (ausgenommen spezielle Umgebungen). Da Windows 7 auch Microsoft unterstützt 64-Bit ohne zusätzlichen Aufwand. @ 2011
O (1) mit jedem erreicht r > 1 Faktor. Gleicher mathematischer Beweis funktioniert nicht nur für 2 als Parameter.
r = 1.5 kann mit old*3/2 berechnet werden, so gibt es keine Notwendigkeit für Gleitkomma-Operationen ist. (Ich sage /2 weil Compiler es mit Bitverschiebung in dem erzeugten Assembler-Code ersetzen, wenn sie es für richtig sehen.)
MSVC ging für r = 1,5, so gibt es zumindest einen großen Compiler, der nicht 2 als Verhältnis nicht verwendet.

Wie bereits erwähnt von jemandem 2 fühlt sich besser als 8. Und auch 2 fühlt sich besser als 1,1.

Mein Gefühl ist, dass 1.5 ein guter Standardwert ist. Anders als das es hängt von dem konkreten Fall.

Lizenziert unter: CC-BY-SA mit Zuschreibung

Nicht verbunden mit StackOverflow