Autor |
Beitrag |
Bergmann89
Beiträge: 1742
Erhaltene Danke: 72
Win7 x64, Ubuntu 11.10
Delphi 7 Personal, Lazarus/FPC 2.2.4, C, C++, C# (Visual Studio 2010), PHP, Java (Netbeans, Eclipse)
|
Verfasst: Sa 01.05.10 06: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: 6
Linux
CodeTyphon
|
Verfasst: Do 06.05.10 12:27
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
Beiträge: 19285
Erhaltene Danke: 1743
W11 x64 (Chrome, Edge)
Delphi 11 Pro, Oxygene, C# (VS 2022), JS/HTML, Java (NB), PHP, Lazarus
|
Verfasst: 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
Beiträge: 1742
Erhaltene Danke: 72
Win7 x64, Ubuntu 11.10
Delphi 7 Personal, Lazarus/FPC 2.2.4, C, C++, C# (Visual Studio 2010), PHP, Java (Netbeans, Eclipse)
|
Verfasst: 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: 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
|
Verfasst: Mi 23.03.11 11:53
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.
|
|
|