TList durchzählen

Bergmann89 · Verfasst: Do 03.09.09 13:26

HI,

ich bin grad dabei n Geschwindigkeitstest zwischen Array, TList und ner doppelt verketteten Liste von mir zu machen. Und ich hab n par Probleme bei der TList. Wenn ich auf die Items mit List.Item[index] zugreif dauert es sehr lang. Ich such sowas wie List.GetNext gibts das bei den Listen nich, oder funzt das hier bloß bisl anders?

MfG & Thx Bergmann.

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

Gausi · Verfasst: Do 03.09.09 13:53

TList ist intern ein Array. Der Zugriff auf aList[aIndex] geht da prinzipiell genauso schnell wie bei einem Array. Deshalb gibt es kein TList.GetNext - man nimmt einfach den nächsthöheren Index.

_________________
We are, we were and will not be.

Dude566 · Verfasst: Do 03.09.09 14:56

Müsste doch mit einer Schleife in der du den Index höchzählst recht schnell gehen solange es nicht zu große Datenmengen sind.

_________________
Es gibt 10 Gruppen von Menschen: diejenigen, die das Binärsystem verstehen, und die anderen.

Bergmann89 · Verfasst: Do 03.09.09 17:03

Hey,

es is bedeutend langsamer als ein normales Array:

OnCreate:

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:
6:

  List := TList.Create;
  for i := 0 to 99 do
    begin
      Arr[i] := i;
      List.Add(PInteger(i));
    end;

Liste durchzählen (ca. 1600ms):

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:

  StartTime := GetTickCount;
  for j := 0 to 1000000 do
    for i := 0 to 99 do
      List[i] := PInteger(Integer(List[i]) + 1);
  Button3.Caption := IntToStr(GetTickCount - StartTime);

Array durchzählen(ca. 160ms):

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:

  StartTime := GetTickCount;
  for j := 0 to 1000000 do
    for i := 0 to 99 do
      Arr[i] := Arr[i] + 1;
  Button2.Caption := IntToStr(GetTickCount - StartTime);

da ich das Ganze für ein Spiel verwenden will, is die Performance extrem wichtig...

MfG Bergmann.

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

Gausi · Verfasst: Do 03.09.09 17:11

Ich würde vermuten, dass bei TList die ganzen Casts und andere interne Dinge die Laufzeit zerhauen. Daher auch das "prinzipiell" in meiner vorigen Aussage. Kann gut sein, dass da ein Faktor 10 durch diesen Kram reinkommt - im O-Kalkül ist das wurscht. ;-)

_________________
We are, we were and will not be.

Bergmann89 · Verfasst: Do 03.09.09 17:21

Im O-Kalkül vieleicht, aber nich bei den FPS meines Spiels ^^

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

Tilman · Verfasst: Do 03.09.09 17:36

Du darfst beim Initialisieren den Wert nicht in einen PInteger wandeln, weil der Zeiger nach ablauf der Lokalen Prozedur weg ist (okay war nur ein Test, aber Normalerweise geht das nicht so deswegen sag ichs hier, man muss erst Speicher mit New oder GetMem besorgen).

So haben beide Prozeduren bei mir dieselbe Performance:

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:

procedure TForm1.Button1Click(Sender: TObject);
  var
    zahl: pInteger;
begin
  StartTime := GetTickCount;
  for j := 0 to 1000000 do
    for i := 0 to 99 do
      begin
        zahl := list[i];
        inc(zahl^);
      end;
  label1.Caption := IntToStr(GetTickCount - StartTime);
end;

procedure TForm1.Button3Click(Sender: TObject);
  var
    zahl: pInteger;
begin
 List := TList.Create;
  for i := 0 to 99 do
    begin
      Arr[i] := i;
      new(zahl);
      zahl^ := i;
      List.Add(zahl);
    end;
end;

procedure TForm1.Button2Click(Sender: TObject);
begin
  StartTime := GetTickCount;
  for j := 0 to 1000000 do
    for i := 0 to 99 do
      Arr[i] := Arr[i] + 1;
  label1.Caption := IntToStr(GetTickCount - StartTime);
end;

_________________
Bringe einen Menschen zum grübeln, dann kannst du heimlich seinen Reis essen.
(Koreanisches Sprichwort)

Dude566 · Verfasst: Do 03.09.09 18:08

Was steht denn in StartTime, die Uhrzeit wo es gestartet wird oder ist das ein Startwert der auf Null steht?

_________________
Es gibt 10 Gruppen von Menschen: diejenigen, die das Binärsystem verstehen, und die anderen.

Xentar · Verfasst: Do 03.09.09 18:18

Dude566 hat folgendes geschrieben :

Was steht denn in StartTime, die Uhrzeit wo es gestartet wird oder ist das ein Startwert der auf Null steht?

Steht doch im Quellcode, wo der Wert gesetzt wird :roll:

GetTickCount, also Zeit in ms seit Systemstart.

_________________
PROGRAMMER: A device for converting coffee into software.

Bergmann89 · Verfasst: Do 03.09.09 22:02

Hey,

@Tilman: bei mir sind die Zeien nich gleich. Hab aber alles genau so wie du:

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:

procedure TForm1.FormCreate(Sender: TObject);
var i: Integer;
var Zahl: PInteger;
[...]
begin
  [...]
  List := TList.Create;
  for i := 0 to 99 do
    begin
      new(Zahl);
      zahl^ := i;
      Arr[i] := zahl;

      new(zahl);
      zahl^ := i;
      List.Add(Zahl);

      [...]
    end;
end;

//156ms
procedure TForm1.Button1Click(Sender: TObject);
var StartTime: Cardinal;
var i,j: Integer;
begin
  StartTime := GetTickCount;
  for j := 0 to 1000000 do
    for i := 0 to 99 do
      Arr[i]^ := Arr[i]^ + 1;
  Button1.Caption := IntToStr(GetTickCount-StartTime);
end;

//563ms
procedure TForm1.Button2Click(Sender: TObject);
var StartTime: Cardinal;
var i,j: Integer;
begin
  StartTime := GetTickCount;
  for j := 0 to 1000000 do
    for i := 0 to 99 do
      inc(PInteger(List[i])^);

  Button2.Caption := IntToStr(GetTickCount-StartTime);
end;

un dann hab ich ma noch ne SingleLinkedList implementiert:

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:

TListItem = class(TObject)
  p: Pointer;
  NextItem: TListItem;
end;

procedure TForm1.FormCreate(Sender: TObject);
[...]
var Zahl: PInteger;
var tmp: TListItem;
begin
  FirstItem := TListItem.Create;
  tmp := FirstItem;
  [...]
  for i := 0 to 99 do
    begin
      [...]    
      new(zahl);
      zahl^ := i;
      tmp.p := Zahl;
      if i <> 99 then
        begin
          tmp.NextItem := TListItem.Create;
          tmp := tmp.NextItem;
        end;
    end;
end;

//344ms
procedure TForm1.Button4Click(Sender: TObject);
var tmp: TListItem;
var i: Integer;
var StartTime: Cardinal;
begin
  StartTime := GetTickCount;
  for i := 0 to 1000000 do
    begin
      tmp := FirstItem;
      while Assigned(tmp.NextItem) do
        begin
          inc(PInteger(tmp.p)^);
          tmp := tmp.NextItem;
        end;
      inc(PInteger(tmp.p)^);
    end;
  Button4.Caption := IntToStr(GetTickCount-StartTime);
end;

Ich denk ma das is die beste Lösung. Das is ganz einfach gehalten, is schneller als die TList und ich kann auch sehr gut Elemente hinzufügen und löschen. Das is das, was ich für mein Spiel brauch. Also werd ich das dann wohl so umsetzten...

Mfg Bergmann.

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

	Mitgliederliste
	Gruppen
	Das Team
	Richtlinien
	Synonyme