Schleifen Optimierung möglich?

[C.Schoch]

Hi,
Ist bei dieser Schleife noch eine Optimierungsmöglichkeit, denn ich hab das Problem, dass die ganze Aktion bei 30.000 Einträgen 10 Minuten dauert.
Das ganze läuft in einem Thread und dient dazu alle Strings aus DestList auszusortieren die in SourceList nicht vorhanden sind.

Delphi-Quellcode:

  for i := 0 to SourceList.Count - 1 do
  begin
    if not Terminated then
    begin
      iFindResult := DestList.IndexOf(SourceList.Strings[i]);
      if iFindResult <> -1 then
      begin
        // Zu einer dritten Liste hinzufügen
      end;
    end
    else
    begin
      break;
    end;
  end;

Ich vermute IndexOf sucht auch mit einer Schleife nach dem String, das wären dann IMHO 900.000.000 Operationen.

[Edit]Formatierung geändert[/Edit]

[Der_Unwissende]

Hi,
könntest du bitte am Code die Formatierung nachbessern? Ist ja so gar nicht lesbar!

Versuch es mal Alternativ mit einer THashedStringList (die gibt's dann schon in der VCL) oder mit einer HashMap (glaube Alzmair hat mal eine zur Verfügung gestellt), die dürften um einiges Schneller sein.

Gruß Der Unwissende

[mkinzler]

Vielleicht würde es etwas bringen, wenn du die beiden Listen sortiert wären, dann könntest du über den Index vergleichen.

[omata]

Hallo C.Schoch,

sind beide Listen gleich gross? Wenn die Listen sortiert vorliegen, bietet sich eine binäre Suche an. Und könnte man vielleicht bei einem Fund diesen aus der DestList löschen, um sie zu verkleinern?

Delphi-Quellcode:

var i:integer;
    abbruch:boolean;
begin
  i:=0;
  abbruch:=false;
  while (i < SourceList.Count) and not abbruch do begin
    if not Terminated then
    begin
      iFindResult := DestList.IndexOf(SourceList.Strings[i]);
      if iFindResult <> -1 then
      begin
        DestList.Delete(iFindResult);
        // Zu einer dritten Liste hinzufügen
      end;
    end
    else abbruch:=true;
    inc(i);
  end;
end;

Ausserdem ist dies mal wieder ein schönes Beispiel dafür, dass man kein break benötigt.

Edit: Nochmal zum Sortieren, teste dochmal wie lange eine Sortierung benötigt.

Gruss
Thorsten

[thkerkmann]

Hi,

genau und die variable abbruch braucht man auch nicht

Delphi-Quellcode:

while not Terminated and (i < Sourcelist.Count) do
begin
  i := 0;
  iFindResult := DestList.IndexOf(SourceList.Strings[i]);
  if iFindResult <> -1 then
  begin
    DestList.Delete(iFindResult);
    // Zu einer dritten Liste hinzufügen
  end;
  inc(i);
end;

und entscheidend ist, dass Destlist sortiert vorliegt, dann läuft IndexOf mit der binären Suche.


Gruss

Thomas

[JasonDX]

Zitat von thkerkmann:

Delphi-Quellcode:

while not Terminated and (i < Sourcelist.Count) do
 ...

Doch, da Terminate eine andere Bedeutung und einen anderen Wert haben kann als abbruch.
Was die non-break-Variante betrifft, so hat sie den "Vorteil", dass ich eine Variable und eine Bedingung mehr in der Schleife habe. Macht aber keinen grossen Unterschied, ist Geschmacksache, und OT.

Was die Schleife an sich betrifft, so ist an der schleife selbst nicht viel zu optimieren.
Ein Compiler wuerde daraus lediglich sowas basteln:

Delphi-Quellcode:

if not Terminated then 
  for i := 0 to SourceList.Count - 1 do 
  begin 
    iFindResult := DestList.IndexOf(SourceList.Strings[i]); 
    if iFindResult <> -1 then 
    begin 
      // Zu einer dritten Liste hinzufügen 
    end
    else 
      break; 
  end;

und das auch nur, weil Terminated hier nicht bearbeitet wird. (Ich denke mal, Terminated wird durch ein Ereignis gesetzt, und hier fehlt lediglich ein ProcessMessages). Ein kleines bisschen wuerde sich durch ein iFindResult < 0 geben, aber einen bemerkbaren Geschwindigkeitsschub wuerde das auch nicht bringen.
Eine Optimierung ist hier - soweit ich das sehen kann - nur im Loesungsansatz moeglich. Denn nach diesem Algorithmus muessen n*m Vergleiche durchgefuehrt werden. Und bei entsprechend grossen Listen kostet dies entsprechend viel Zeit.
Eine Sortierung der Liste wuerde die Laufzeit teils reduzieren (auf ca. O(n*log2(m))), wieviel eine HashedList bringt, weiss ich nicht, duerfte aber noch mehr Geschwindigkeitsschub liefern.

greetz
Mike

[thkerkmann]

Nö,

denn abbruch wird true gesetzt, wenn Terminated true ist. Also kann ich's weglassen.

Und es fehlt kein ProcessMessages - wie wir im Anfang lesen können handelt es sich um einen Thread. Dieser hat eine property Terminated, die angibt ob der Thread beendet wurde bzw. werden soll.

Gruss

Thomas

[C.Schoch]

So ich habe jetzt etwas mit der HashedStringList experimentiert.
Ich hatte mit einer Halbierung der Zeit gerechnet, aber nicht von gemessen 5min16sec auf 11sec
Allerdings dauert das hinzufügen etwas länger was aber vernachlässigbar ist.

@thkerkmann das "Delete" ist schon drin hat ca. 2min gebracht.

@JasonDX das Terminated ist innerhalb der Schleife, weil keiner gerne 5 Minuten auf einen Abbruch warted.
Ich denke schon, dass Terminated verarbeited wird,da dießer code von einem Thread verarbeited wird.

ich finde an "break" nichts verwerfliches.

Ich danke euch für die Hilfe.

[omata]

@thkerkmann:

Zitat von C.Schoch:

ich finde an "break" nichts verwerfliches.

Hab ich auch nicht behauptet. Es ging nur darum, das es nicht nötig ist.

Gruss
Thorsten

[hoika]

Hallo,

dein if Terminated musst du nicht in jedem Schleifendurchlauf prüfen.
Viell. ein

if (i div 100)=0 then if terminatet.. Falls Terminated über eine Thread-Synchronisation
"bearbeitet" wird, bringt es viell. noch was.

*testen*

Heiko