verkettete Liste

[himitsu]

Ich hab ja nicht gesagt, daß es einfach ist, aber wenn man statt der 1000, um die jedesmal vergrößert wird, ein passenderer Wert nehmen würde, dann wäre halt das andere wieder besser.

[alzaimar]

Zitat:

Zitat von himitsu

..., aber wenn man statt der 1000, um die jedesmal vergrößert wird, ein passenderer Wert nehmen würde, dann wäre halt das andere wieder besser.

Das lass ich nicht gelten. Welcher Wert ist 'passender'? Welche Heuristik zur Ermittlung der Größenänderung ist besser als die Verdopplung? Ohne konkretes Beispiel bleibt die Vergrößerung per Faktor (egal welcher) die bessere Variante, als die Vergrößerung um einen konstanten Wert.

Ich kann ja auch einfach sagen: Der optimale Vergrößerungsfaktor ist der, der sofort (per TGlasskugel) die optimale Größe einstellt. :mrgreen:

[DGL-luke]

Dafür wäre wohl ein

Delphi-Quellcode:

procedure TMyList.BeginUpdate(Capacity: Cardinal);

bzw.

Delphi-Quellcode:

property Capacity: read FCapacity write SetCapacity;

angebracht...

[Elvis]

Zitat:

Zitat von alzaimar

Zitat:

Zitat von himitsu

..., aber wenn man statt der 1000, um die jedesmal vergrößert wird, ein passenderer Wert nehmen würde, dann wäre halt das andere wieder besser.

Das lass ich nicht gelten. Welcher Wert ist 'passender'? Welche Heuristik zur Ermittlung der Größenänderung ist besser als die Verdopplung? Ohne konkretes Beispiel bleibt die Vergrößerung per Faktor (egal welcher) die bessere Variante, als die Vergrößerung um einen konstanten Wert.

Ich habe mich hier auf 172% eingeschossen. Ist IMO ein optimaler SWA (StiNo-Wachstumsfaktor-Arraybasierter-Container :mrgreen: ).
Wenn es wirklich darum geht noch ein Quentchen rauszuquetschen[1] feile ich aber auch an der Größe.
Oft ist es besser einen Container, der theor. größer werden kann, nicht bei 0 oder 10 Elementen zu initialieren. Eine Zahl, die bei möglichst vielen kleinbleibenden Instanzen eine Kopiererei verhindert finde ich da viel netter. So spielen nur die großen Ausreißer Xerox. :mrgreen:


[1]welches dank X-Wiederholungen schon in merkbare Zehntelsekunden ausarten kann, die zusammen mit 5 anderen Methoden zu einem ekligen Lag führen könnten, das ...

Lange Rede, ganz wenig Sinn: Probiere mal 172% statt 200%. ;)

[alzaimar]

Zitat:

Zitat von Elvis

Lange Rede, ganz wenig Sinn: Probiere mal 172% statt 200%. ;)

Unter welchen Bedingungen hast Du das denn rausgefunden?

Ich hab mal eine Reihe von 'optimalen' Faktoren für das Wachsen von Hashtabellen gefunden (das müssen ja Primzahlen sein). Da hat sich doch tatsächlich Einer die Mühe gemacht, die 32 Primzahlen bis 2^31 aufzulisten, die seiner Meinung nach eine optimale Größe ergeben. Leider hat er nicht bedacht, das er nur eine (irgendeine) Testumgebung hat, die sich nicht mit z.B. Meiner deckt. Na ja, das hätten ja durchaus magische Zahlen sein können. Es war aber nur Quark.

Deshalb kann es sein, das die 172 (Andere sprechen von 166) Prozent besser sind, aber in meiner Umgebung bisher nicht. Es macht einfach keinen Unterschied, ob ich nun verdopple, oder ver 1,72fache. Wie gesagt. in meinem Fall.

Übrigens gibt es auch Ansätze, die Fibionacci-Zahlenreihe zu verwenden.

Mir ging es aber ursprünglich sowieso nur darum, zu zeigen, das eine Vergrößerung um irgendeinen Faktor in der Komplexitätsbetrachtung gegenüber einer konstanten Erhöhung vernachlässigbar ist. Ob das 166, 172, 172.163 oder 200 sind, ist dabei unerheblich.

[himitsu]

Na ja, im MM nehm ich ja och 130%/70%, aber bei den String hab ich's infach so gelöst, dat die Größe auf die nächte Volle aufgerundet wird, dat macht vorallem viel aus, wenn sehr viele kleine Änderungen gemacht werden (z.B. per StringReplace und Co.)

TGlasauge ist gut, weiß nur nicht mehr wo ich dat abgespeichert hatte ... aber hier wurde ja eh schon zuoft festgestelt, daß man eigentlich nur "optimal" optimieren kann, wenn man genau weiß, was auf einen zukommt ... ansonsten kann man nur versuchen auf irgendeine Weise das ganze etwas optimaler zu machen (für einen kleinen Bereich der möglichen Änderungen).