Performanz bei geschachtelten for-Schleifen

[Stephan Schneider]

Hallo,

im Programm wird vom Benutzer eine Liste an Einträgen erstellt. Die Darstellung erfolgt in einem ExpressQuantumGrid.

Nun sollen Vergleiche durchgeführt werden, dass sich z.B. keine doppelten Einträge in der ersten Spalte befinden dürfen. Demzufolge wurde folgendes Verfahren implementiert:

in Pseudocode:<pre>
for I := 0 to Anzahl do
for J := I+1 to Anzahl do
if Eintrag[I] = Eintrag[J] then
Fehlermeldung</pre>

Irgendwie habe ich das Gefühl, dass diese ineinandergeschachtelten for-Schleifen nicht unbedingt der Bringer in punkto Perfomanz sind. Bei etlichen tausend Einträgen dauert das ganze schon ungewöhnlich lange.

Bessere Alternativen?

Danke im voraus

[Mario.Noack]

Ja, Listen sind besser. Du kannst Dir beispielsweise eine StringList erzeugen. Ich müsste nachschauen, aber es gibt eine property, die Dublikate vermeidet. Dann fügst Du in einer For-Schleife alle Einträge hinzu und bekommst entweder einen Fehler, oder nicht.<p>
Schöne Grüße, Mario Noac

[Michael Koecher]

Hi,<br>
Stringlist ist richtig, der Befehl lautet:<br>
dupIgnore Der Versuch, der sortierten Liste ein String-Duplikat hinzuzufügen, wird ignoriert.
<br&gt

[shadows]

Man könnte es auch notfalls per Hand prüfen, wenn man mehr Kontrolle haben will. Und zwar mit indexOf(s: string): integer;. Wenn der integer = -1 ist, ist der eintrag nicht vorhanden. Wenn der eintrag >= 0 ist, bibt das die position an, an in der er in der liste steht. Dann kann man ihn entweder hinzufügen, oder eben nicht, bzw. einen fehler ausgeben, oder sonnst etwas machen.
Ich habe allerdings nicht ausprobiert, was Delphi mit der Laufzeit anstellt. Wenn Delphi über Hashtabellen geht, oder wenn Delphi Sortierte Listen von der Laufzeit anders behandelt als Normal, dann ist das schneller. Wenn Delphi aber keins von beiden macht ist es nicht schneller. Das kannst du ja mal ausprobieren.

<pre>
var
liste: TStringlist;
i: integer;

begin
for i := 0 to Anzahl do
if Liste.indexOf(Eintrag[i]) < 0 then
Liste.add(Eintrag[i])
else
Fehlermeldung

end;
</pre>
&#10

[shadows]

Es geht aber noch besser.
Dabei muß man allerdings die Quellliste Sortieren. Wenn das nicht geht, würde ich mir eine Hilfsliste bauen, die Quellliste reinkopieren und die dann sortieren.

<pre>
if QuellList.count>0 then
begin
QuellList.sort;
ZielList.add(QuellList[0]);

for i:= 1 to QuellList.count-1 do
if QuellList[i]<>ZielList[ZielList.count-1] then
ZeilList.add(QuellList[i])
else
Fehlermeldung;

end;
</pre>

Schneller geht es eigenlich nur, wenn du für die Quellliste eine eigene Sortier routine schreibst. Soweit ich weiß verwendet Delphi Quicksort. Dieser hat im normal Fall in etwas n*log n an komplexität. In seltenen fällen hat er allerdings eine sehr ungünstige laufzeit, n*n. Wenn du sicher gehen willst, das er schnell sortiert mußt du dir einen MergeSort schreiben. In den meißten fällen wird es aber nichts bringen

[Roy Blandau]

hi,<br><br>
ein dekrementieren (for quelle.count-1 to 0 do ...) der schleife sollte bei grossen<br>
datenmengen auch ein geschwindigkeits-zuwachs bringen.<br>
jedenfalls ist das unter c/c++ der fall.<br>
kommt drauf an, wie der borland-compiler das umsetzt.<br>
aber das koenntest mal benchmarken.<br><br>
gruss roy<br><br>
edit: evtl. auch mal mit kopf- oder fuss-gesteuerten dekrementierenden while-schleifen probieren.<br&gt

[Stephan Schneider]

Hi,

danke für Eure Antworten. Das Ergebnis, das ich erhalten habe, ist phänomenal.

Vorher bin ich in einer ineinandergeschachtelten for-Schleife über das Grid iteriert. Zeitliche Dauer bei ca. 20000 Einträgen: im Minutenbereich (<= 10 min).

Jetzt habe ich diese ineinandergeschachtelten for-Schleifen eliminiert. An ihrer Stelle schreibe ich im Rahmen einer einfachen Iteration den Wert in eine Stringliste (Sorted = True, Duplikates = dupError), die Exception fange ich dabei ab. Zeitliche Dauer: im Sekundenbereich (<= 1 min.