Entwickler-Ecke

Algorithmen, Optimierung und Assembler - listbox items-anzahl


huhn - Mo 03.10.05 12:09
Titel: listbox items-anzahl
Hi leute!
leider ist mir kein gescheiter titel für das topic eingefallen, vielleicht fällt euch ja noch was ein ;-).
So nun zu meinen problem:
ich habe eine stringlist mit jeder menge string(wirklich viel über 5000) und die strings enthalten einen namen und eine koordinate, ich will nun zählen wieviele items es von jedem namen gibt, dazu hab ich folgenden code gemacht:

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:
 
procedure TWeiteresForm.ToplistButtonClick(Sender: TObject);
var n,c:Tstringlist;
    name:string;
    count,lauf:integer;
begin
n:=Tstringlist.Create; //2 listen für name und anzahl (n=name, c=anzahal)
c:=Tstringlist.Create;
if listbox1.Items.Count=0 then exit;
repeat
  name:=copy(listbox1.Items.Strings[0],0,pos('--',listbox1.Items.Strings[0])-1);//name extrahieren immer vom ersten string (wird nachher immer gelöscht)
  lauf:=0;//zurücksetzen der variablen
  count:=0;
  repeat
    application.ProcessMessages;
    if pos(name,listbox1.Items.Strings[lauf])<>0 then //wenn der name enthalten ist löschen und den die anzahl um 1 erhöhen
      begin
        listbox1.Items.Delete(lauf);
        count:=count+1;
      end;
    lauf:=lauf+1;
  until lauf>=listbox1.Items.Count-1;//wenn lauf größer als die itemsanzahl ist dann nächster name durchgehen, vorher aber in die stringlists einfügen
  n.Add(name);
  c.Add(inttostr(count));
until listbox1.Items.Count-1=0;
...//später werden diese noch sortiert, dies ist aber nicht wesentlich

so, dieser code scheint zu funktionieren, jedoch ist er sehr langsam!
warum ist er so langsam und wie kann ich ihn viel schneller machen?
mfg huhn


huhn - Mo 03.10.05 12:25
hab noch mal eingehen mein code studiert und bin über einen fehler gestoßen, er hängt mit dem lauf und dem löschen der einträge zusammen.
wenn eine übereinstimmung da ist wird zum nächsten gesprungen auch wenn es hochgerutscht ist


uall@ogc - Mo 03.10.05 13:19
hallo huhn,

da du 2 repeatschleifen ineinander hast, wirste nen laufzeitverhalten von n² haben. und das ist extrem langsam. (n anzahl der einträge)

deshalb würd ich dir vorschlagen das du die liste sortierst, mit nem algorithmus das nen laufzewitverhalten von n*log(n) hat. (quicksort, hate ne TStringlist nicht nen eigene sortiert algo eingebaut?) und anschließend einfach von 1 bis zum letzen element durchläuft und schaust ob das darauffolgende den selbigen namen wie das eigene hat, dann bleibt das laufzeitverhalten bei n*log(n)+n ~ n*log(n) also linearlogarithmisch ;)


kurz: sortieren und dann vergleichen mit dem nachbarn und nicht mit allen.


huhn - Mo 03.10.05 14:46
ja stimmt hätte ich au machen können^^
ich habs aber auch so hinbekommen, lag daran das ich aktiv mit der listbox gearbeitet habe.

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:
 
procedure TWeiteresForm.ToplistButtonClick(Sender: TObject);
var n,c,o:Tstringlist;
    name:string;
    count,lauf,z:integer;
label here;
begin
if listbox1.Items.Count=0 then exit;
o:=Tstringlist.Create;
o.Assign(Listbox1.Items);
n:=Tstringlist.Create;
c:=Tstringlist.Create;
z:=o.Count;
repeat
  name:=copy(o.Strings[0],0,pos('--',o.Strings[0])-1);
  count:=0;
  lauf:=0;
  repeat
    application.ProcessMessages;
    repeat
      begin
      if pos(name,o.Strings[lauf])<>0 then
        begin
          o.Delete(lauf);
          count:=count+1;
        end;
      if lauf>o.Count-1 then goto here;
      end;
    until pos(name,o.Strings[lauf])=0; 
    lauf:=lauf+1;
  until lauf>=o.Count;
  here:
  n.Add(name);
  c.Add(inttostr(count));
  Progressbar1.Position:=z-o.Count;
until o.Count-1=0;
//sortier angepasst für 2 listen
BubbleSort(c,n);
for lauf:=0 to n.Count-1 do n.strings[lauf]:=inttostr(lauf+1)+'. '+n.strings[lauf]+' ('+c.Strings[lauf]+')';
sd.filter:='Textfile |*.txt';
if sd.Execute then  n.SaveToFile(sd.FileName+'.txt');
c.Free;n.Free;o.Free;
end;

ich hoff ihr bringt mich nicht um wegen den vielen repeatschleifen und wegen so ein paar anderen sachen^^
mfg huhn


Entwickler-Ecke.de based on phpBB
Copyright 2002 - 2011 by Tino Teuber, Copyright 2011 - 2026 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!