Entwickler-Ecke :: Thema anzeigen

Bergmann89 - Sa 01.05.10 06:23
Titel: DoubleLinkedList

Hey,

ich hab heut ne Klasse für ne DoubleLinkedList (doppelt verkettete Liste) geschrieben. Die is beim normalen Zugriff n ganz kleinen Tick schneller, als die normale TList. Der gewichtigere Vorteil der DoubleLinkedList liegt beim durchzählen, hier kann sie rein theoretisch sogar fast doppelt so schnell wie die normale Liste sein. Weiterhin sollte die auch schneller beim löschen und hinzufügen von Daten sein, da immer nur ein neues Objekt erstellt und rein gehängt wird. Die normale Liste basiert ja auf einem Array und da muss immer neuer Speicher reserviert und das Array umkopiert werden. Ich mess das alles nochmal nach un poste es dann hier. Wollt nur erstma die Unit hochladen und eure Meinung hören...

MfG Bergmann.

jaenicke - So 09.05.10 22:34

Sinnvoll ist eine solche Liste immer dann, wenn hauptsächlich sequentiell auf die Elemente zugegriffen wird. Ein wahlfreier Zugriff auf bestimmte Elemente über den Index ist dagegen extrem aufwendig.

Zeit sparen tut man, wenn viel an der Liste geändert wird, das stimmt. Aber das auch nur, wenn nicht über den Index auf bestimmte Einträge zugegriffen wird, z.B. beim Löschen. Denn dann macht das zumindest einen Teil der Ersparnis wieder zunichte.

Deshalb macht es Sinn die Elemente über die entsprechenden Objektzeiger selbst anzusprechen und mit diesen zu arbeiten, da so der direkte Zugriff auf die Verknüpfungszeiger der Liste gegeben ist. So ist dann z.B. eine Löschoperation in der Tat sehr schnell.

Bergmann89 - Mo 10.05.10 01:04

Hey,

habs ma durchprobiert. Bei den random Zugriffen ist die normale Liste eindeutig schneller. Bei den sequensiellen Zugriffen ist die LinkedList bei einer Anzahl von 50.000 Elementen im Vorteil, bei allem was drüber geht ist die normale Liste wieder schneller. Hier ma der TestCode:

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:
62:
63:
64:
65:
66:
67:
68:
69:
70:
71:
72:
73:
74:
75:
76:
77:
78:
79:
80:
81:
82:
83:
84:
85:
86:
87:
88:
89:
90:
91:

const
  ItmN = 50000;
  RndN = 1000000;
  SeqN = 10000;

procedure TForm1.FormCreate(Sender: TObject);
var i: Integer;
begin
  NList := TList.Create;
  DList := TDoubleLinkedList.Create;
  for i := 0 to ItmN do begin
    NList.Add(Pointer(i));
    DList.Add(Pointer(i));
  end;
  randomize;
end;

procedure TForm1.Button1Click(Sender: TObject);
var i, value: Integer;
var fStartTime, fStopTime, fFrequency: Int64;
var rnd: Integer;
begin
  QueryPerformanceFrequency(fFrequency);
  rnd := NList.Count;

  QueryPerformanceCounter(fStartTime);
  for i := 0 to RndN do begin
    value := Integer(NList[random(rnd)]);
  end;
  QueryPerformanceCounter(fStopTime);

  Button1.Caption := 'normal List random:' + FloatToStr(RoundTo((fStopTime-fStartTime)/fFrequency, -3));
end;

procedure TForm1.Button2Click(Sender: TObject);
var i, value: Integer;
var fStartTime, fStopTime, fFrequency: Int64;
var rnd: Integer;
begin
  QueryPerformanceFrequency(fFrequency);
  rnd := DList.Count;

  QueryPerformanceCounter(fStartTime);
  for i := 0 to RndN do begin
    value := Integer(DList[random(rnd)]);
  end;
  QueryPerformanceCounter(fStopTime);

  Button2.Caption := 'linked List random:' + FloatToStr(RoundTo((fStopTime-fStartTime)/fFrequency, -3));
end;

procedure TForm1.Button3Click(Sender: TObject);
var i, j, value: Integer;
var fStartTime, fStopTime, fFrequency: Int64;
var rnd: Integer;
begin
  QueryPerformanceFrequency(fFrequency);
  rnd := NList.Count;

  QueryPerformanceCounter(fStartTime);
  for i := 0 to SeqN do begin
    for j := 0 to NList.Count-1 do
      NList[j] := Pointer(j);
  end;
  QueryPerformanceCounter(fStopTime);

  Button3.Caption := 'normal List sequensiell:' + FloatToStr(RoundTo((fStopTime-fStartTime)/fFrequency, -3));
end;

procedure TForm1.Button4Click(Sender: TObject);
var i, j, value: Integer;
var item: TListItem;
var fStartTime, fStopTime, fFrequency: Int64;
var rnd: Integer;
begin
  QueryPerformanceFrequency(fFrequency);
  rnd := DList.Count;

  QueryPerformanceCounter(fStartTime);
  for i := 0 to SeqN do begin
    item := DList.Items[0];
    j := 0;
    while Item <> nil do begin
      Item.Value := Pointer(j);
      Item := Item.Next;
    end;
  end;
  QueryPerformanceCounter(fStopTime);

  Button4.Caption := 'linked List sequensiell:' + FloatToStr(RoundTo((fStopTime-fStartTime)/fFrequency, -3));
end;

Im Anhang ma noch das komplette projekt, wenn noch jmd rumprobieren möchte.

MfG Bergmann.

TestSystem:
Athlon64 4000+ @2.41GHz
WinXP 32Bit SP3 getestet

Pepp3r - Mi 23.03.11 11:53

jaenicke hat folgendes geschrieben :

so aufwändig ist das eigendlich nicht. ordne die Liste als suchbaum und setze einen pointer also cursor, der durch den baum wandert. im schnitt würde man viel mehr zeiit sparen als eine kette zu durchkaufen.

Entwickler-Ecke.de based on phpBB
Copyright 2002 - 2011 by Tino Teuber, Copyright 2011 - 2024 by Christian Stelzmann Alle Rechte vorbehalten.
Alle Beiträge stammen von dritten Personen und dürfen geltendes Recht nicht verletzen.
Entwickler-Ecke und die zugehörigen Webseiten distanzieren sich ausdrücklich von Fremdinhalten jeglicher Art!