DoubleLinkedList

Bergmann89 · Verfasst: Sa 01.05.10 05:23

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.

Einloggen, um Attachments anzusehen!

_________________
Ich weiß nicht viel, lern aber dafür umso schneller^^

spawn89 · Beiträge: 82 Erhaltene Danke: 7 Linux CodeTyphon

Soweit ich weiß ist deine Klasse nicht schneller beim Zugriff auf einzelne Elemente. Du nutzt Schleifen um das benötigte Element zu suchen, die TList-Klasse liefert den Index einfach *bäm* sofort zurück. Solange aber GetItemByIndex nicht (oft) aufgerufen wird, lohnt es sich auf jeden Fall.

jaenicke · Verfasst: So 09.05.10 21: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 · Verfasst: Mo 10.05.10 00: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:

markieren

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

Einloggen, um Attachments anzusehen!

_________________
Ich weiß nicht viel, lern aber dafür umso schneller^^

Pepp3r · Beiträge: 82

jaenicke hat folgendes geschrieben :

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.

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.

	Mitgliederliste
	Gruppen
	Das Team
	Richtlinien
	Synonyme