D slicing und runtime

[Namal]

Hallo,

ich versuche grade das Slicing zu verstehen und wie man das effizient nutzt.

Hier steht

Make sure that the array capacity is big enough at the beginning to allow for efficient non-reallocating array appends and concatenations later if performance is a concern. You can't modify the .capacity property. You are only allowed to either modify the length, or use the reserve function.

und

int[] a = [1,2,3,45];
a.reserve(10);  // if a's capacity is more than 10, nothing is done
// else a is reallocated so that it has a capacity of at least 10

Was bedeutet denn "at the beginning". Was ist wenn zu Anfang mein Array die Größe 0 hat, kann ich es dem auch die Kapazität 10 zuweisen? Und wie wähle ich die Kapazität aus, damit es effizient wird? Sagen wir bei einem Stack, wo ich immer nut ein Element anhänge und entferne?

[hustbaer]

"at the beginning" heisst bevor du anfängst Daten reinzutun.

Was ist wenn zu Anfang mein Array die Größe 0 hat, kann ich es dem auch die Kapazität 10 zuweisen?

Ja, mit .reserve(10)

Und wie wähle ich die Kapazität aus, damit es effizient wird? Sagen wir bei einem Stack, wo ich immer nut ein Element anhänge und entferne?

Na du machst die capacity min. gleich gross wie die grösste zu erwartende Länge.
Wenn du keine sinnvolle Obergrenze kennst, dann lass es einfach.

Reallocation kostet zwar durchaus Zeit, aber mach dich damit mal nicht verrückt. Ist viel weniger Schlimm als man meinen mag.

Zumindest wenn D schlau genug ist die Arrays geometrisch wachsen zu lassen. (Macht quasi jede "dynamic array" Implementierung so, von daher gehe ich davon aus dass D da nicht die Ausnahme sein wird.)

[Namal]

http://deadaztec.wordpress.com/2013/03/01/arrays-and-slices/

Ok, hier hab ich gefunden, dass wenn man 2^x große Stücke nehmen soll und das liefert dann eine konstante Laufzeit.