Autor Beitrag
Bergmann89
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
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)
BeitragVerfasst: 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
ontopic starontopic starontopic starontopic starontopic starhalf ontopic starofftopic starofftopic star
Beiträge: 82
Erhaltene Danke: 6

Linux
CodeTyphon
BeitragVerfasst: 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
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 18694
Erhaltene Danke: 1620

W10 x64 (Chrome, IE11)
Delphi 10.2 Ent, Oxygene, C# (VS 2015), JS/HTML, Java (NB), PHP, Lazarus
BeitragVerfasst: 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 Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
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)
BeitragVerfasst: 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:
ausblenden volle Höhe 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
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starontopic star
Beiträge: 82



BeitragVerfasst: Mi 23.03.11 11:53 
user profile iconjaenicke hat folgendes geschrieben Zum zitierten Posting springen:
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.