Forum: FreePascal
FreePascal
by Namenloser,
17. Apr 2014
Das Suchen ist wohl auch eher nicht das Problem. Aber das Einfügen und Löschen eines Elements ist beim Array O(n), weil die Elemente im Speicher umkopiert werden müssen.
Forum: FreePascal
FreePascal
by Namenloser,
17. Apr 2014
Eine Speicherseite (4096 Bytes) erscheint mir recht viel. Bei der Größe würde es mich doch wundern, wenn ein Baum nicht schneller wäre. Ich kann mir vorstellen, dass Arrays bis ~100 oder vielleicht 200 Elemente (sagen wir mal Ints) überlegen sind.
Forum: FreePascal
FreePascal
by Namenloser,
16. Apr 2014
Ich hatte deswegen auch erst überlegt, einfach ein Array zu nehmen. Aber dann kam der Perfektionist in mir wieder durch und dachte sich, es wäre doch schön, wenn trotzdem garantiert wäre, dass die asymptotische Laufzeit nicht aus dem Ruder läuft. Hab mir dann erst überlegt, ob man das Array vielleicht irgendwie erweitern könnte, aber habe dann nach einer Weile gemerkt, dass ich eigentlich gerade...
Forum: FreePascal
FreePascal
by Namenloser,
15. Apr 2014
So, ich habe jetzt noch mal einen saubereren Test in einem neuen Projekt geschrieben.
B+ Tree
Ascending linear (1000000)
Insert: 451 ms
Locate: 273 ms
Remove: 543 ms
Descending linear (1000000)
Insert: 661 ms
Forum: FreePascal
FreePascal
by Namenloser,
15. Apr 2014
Naja, nur dafür hätte ich es wohl auch nicht gemacht. Eine sortierte Liste braucht man z.B. hierfür. Ein Binomialheap ist da auch schon im Einsatz, reicht aber nur für eine der beiden Datenstrukturen.
Ich hatte erst mal nur Sorted-Inserts getestet, weil es eigentlich spannender ist. Für wirklich zufällige Inserts bräuchte man theoretisch gar keinen balancierten Baum.
Für einen umfangreichen...
Forum: FreePascal
FreePascal
by Namenloser,
14. Apr 2014
Der Testcode ist ziemlich hässlich und mit heißer Nadel gestrickt, aber gut:
const
c = 500000;
begin
Tree := TABTree.Create;
t0 := GetTickCount64();
for i := 1 to c do
Tree.Insert(i,i);
for i := 2*c downto c+1 do
Forum: FreePascal
FreePascal
by Namenloser,
14. Apr 2014
Der scheint wirklich ziemlich schnell zu sein, zumindest wenn er erst mal einen Pool an TreeNodes angelegt hat, die er dann recyclen kann:
B+ 1000000 Inserts: 447
B+ 1000000 Locates: 280
B+ 500000 Removes: 201
B+ 500000 Reinserts: 241
SL 1000000 Inserts: 713
SL 1000000 Locates: 212
SL 500000 Removes: 324
SL 500000 Reinserts: 347
Forum: FreePascal
FreePascal
by Namenloser,
13. Apr 2014
Die Zahlen stammen so 1:1 aus dem Systemmonitor.
Ich meinte eigentlich die Speicherverwaltung. Denn das kann man ja sicher mal wieder gebrauchen. Den Baum werde ich aber möglicherweise auch als Open Source veröffentlichen.
B+-Bäume machen auch im Arbeitsspeicher Sinn, weil sie deutlich cachefreundlicher sind als etwa Rot-Schwarz-Bäume. Falls dich Zahlen interessieren, unser Übungsleiter...
Forum: FreePascal
FreePascal
by Namenloser,
12. Apr 2014
Ich habe das mit der eigenen Speicherverwaltung jetzt so weit umgesetzt. Komme jetzt mit dem FPC-Speichermanager in Kombination mit meiner eigenen Speicherverwaltung auf ca 98 MB, also geringfügig mehr als mit dem C-Speichermanager. Geschwindigkeitsmäßig kann die Implementierung ebenfalls mithalten. Und es wird sogar der Speicher am Ende vollständig wieder freigegeben. :)
Wäre vielleicht auch...
Forum: FreePascal
FreePascal
by Namenloser,
12. Apr 2014
Also hier unter Linux gibt der FPC-Speichermanager auch den Speicher zurück. Der C-Manager hingegen behält ihn. Finde ich aber nicht so toll, ich finde, der Speicher sollte schon zurückgegeben werden, es laufen schließlich noch andere Programme auf dem Rechner.
Forum: FreePascal
FreePascal
by Namenloser,
12. Apr 2014
var
i: integer;
begin
// 7 MB
for i := 0 to 1000000 - 1 do
New(recs);
// 77 MB
for i := 1000000 to 2000000 - 1 do
New(recs);
// 144 MB
