Forum: Sonstige Fragen zu Delphi
Delphi
by alzaimar,
19. Mai 2006
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)...
Forum: Sonstige Fragen zu Delphi
Delphi
by alzaimar,
19. Mai 2006
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...
Forum: Sonstige Fragen zu Delphi
Delphi
by alzaimar,
19. Mai 2006
Nein, stimmt nicht. Also, der erste Satz stimmt nicht. Der Zweite schon, aber woher willst Du denn wissen, wieviel vermutlich dazukommt? Wenn Du das wüsstest, könntest Du die Liste gleich groß genug machen.
Eine Liste, die ihre Größe jeweils verdoppelt, tut dies (bei einer angenommenen Anfangsgroße von 1000 Elementen) nur 21x in ihrem Leben. Und das auch nur, wenn man sie mit 2Mrd. Elementen...
Forum: Sonstige Fragen zu Delphi
Delphi
by alzaimar,
19. Mai 2006
Wie immer, muß man zwischen Theorie (Komplexitätsbetrachtung) und Realität unterscheiden.
Wie ich schon sagte, bei einem dynamischen Array muß man die Größe jeweils verdoppeln (oder jedenfalls um einen Faktor vergrößern), und nicht um einen konstanten Wert. Ein konstanter Wert wird die Komplexität von O(1) auf O(n) verschlechtern, eine Vergrößerung um einen Faktor ('2') eben nur marginal....
Forum: Sonstige Fragen zu Delphi
Delphi
by alzaimar,
19. Mai 2006
Dann ist aber auch eine Komplexitätsbetrachtung für'n A****, oder? Egal., Ich hätte es dazu schreiben sollen und Dein Einwand ist berechtigt.
Forum: Sonstige Fragen zu Delphi
Delphi
by alzaimar,
19. Mai 2006
Ich schrieb, das man die Größe des dynamischen Arrays verdoppelt, wenn das neue Elemnt nicht mehr hineinpasst. Windows vergrößert von sich aus gar nichts, oder?
Aber wenn ich das mache, und zwar immer verdoppeln, kann man das vernachlässigen, auch rechnerisch, ergo O(1).
(*) Nee, hab ich gar nicht geschrieben, sondern nur gedacht, das ich das geschrieben habe :wall: . Aber wer nach vor...
Forum: Sonstige Fragen zu Delphi
Delphi
by alzaimar,
18. Mai 2006
Nein. Es kommt hier auf das Verfahren an. Quicksort ist zwar von der Komplexität her genauso wie Shellsort (und auch Mergesort), in der Praxis hat sich aber quicksort bewährt, weil es einfach am kompaktesten ist, also pro Vergleich, Vertauschen etc. am wenigsten Overhead produziert.
Eine iterative Variante von Quicksort, die den rekursiven Aufruf mit einem eigenen Stack simuliert, ist noch...
Forum: Sonstige Fragen zu Delphi
Delphi
by alzaimar,
17. Mai 2006
Hier hilft wieder ein Exkurs in Komplexitätsberechnung: Sei LL die (doppelt) verkettete Liste (Linked List) und DA das dynamische Array;
Anhängen:
LL = O(1)
VA = O(1)
(VA einige Takte schneller, da nur ein Speicherzugriff, LL muss noch die Zeiger aktualisieren)
Sortiert Einfügen:
LL = O(n)
VA = O(n) (O (n log n) für binary search und O(n) für das 'Platz machen', also Verschieben)...
