Doppelte Schleife und Zeit wird immer länger - Wie optimieren?

Für alles, was in den übrigen Lazarusthemen keinen Platz, aber mit Lazarus zutun hat.
Antworten
Epcop
Beiträge: 127
Registriert: Di 29. Mai 2012, 09:36

Doppelte Schleife und Zeit wird immer länger - Wie optimieren?

Beitrag von Epcop »

Hi,

ich habe hier einen code geschrieben, der super funktioniert.
Aus einer Datenbank, will ich einen Datensatz nach dem anderen mit den anderen Datensätzen vergleichen und anschließend modifiziert in eine CSV speichern.
Mit dem Vergleichen, modifizieren und CSV ist kein problem und funktioniert alles.

Das Problem sind eher die Datensätze. Wenn es 10 Datensätze sind, läuft alles schön schnell. Aber sobald es mehr werden, 50, 100, 200,1000,... dauert es sehr lange.

Das Problem ist vermutlich die doppelte Schleife.

Angenommen, für einen Datensatz benötigt das ganze 1 Sekunde (zum rechnen).
Mit der doppelten Schleifen wären das dann a*b=Dauer
Und dann kann man sich ausrechnen, dass die Dauer schnell expontiell in die Höhe schießt. Und die Dauer dann schnell bei ein paar Stunden oder länger sein kann.

Gibt es irgendwelche Tricks um solche Vorgänge zu beschleunigen?

Code: Alles auswählen


procedure TForm1.Button4Click(Sender: TObject);
var
  a,b,z: integer;
  texta: TStringList;
  berechnung,berechnung2,sqla: string;
   startTime: Cardinal;
   temp: string;
   ziel: integer;
begin
  // [...]
  
  sqla := 'SELECT * FROM db a, ue b where a.bID = b.ID;  ';

  ZQuery1.Close;
  ZQuery1.SQL.Clear;
  ZQuery1.SQL.Add(sqla);
  ZQuery1.Open;

  ZQuery2.Close;
  ZQuery2.SQL.Clear;
  ZQuery2.SQL.Add(sqla);
  ZQuery2.Open;



  // [...]

  for a:=0 to ZQuery1.RecordCount-1 do begin    // ==== Erste Schleife
    z:=0;
    if (trim(ZQuery1.FieldByName('vt').AsString)) = '' then begin // wenn leerer datensatz dann weiter
     ZQuery2.First; // und jetzt wieder auf den Anfang setzen!
     ZQuery1.Next;
     continue;
    end;



    berechnung2 := '';
    // csv:
    berechnung2 := berechnung2 + ZQuery1.FieldByName('b').AsString+','+ZQuery1.FieldByName('k').AsString+','+ZQuery1.FieldByName('vn').AsString+'; ';

    for b:=0 to ZQuery2.recordCount-1 do begin  // ==== Zweite schleife berechnung
      if (ZQuery2.FieldByName('a1').AsString+' '+ZQuery2.FieldByName('k').AsString+','+ZQuery2.FieldByName('vn').AsString) =       ZQuery1.FieldByName('a1').AsString+' '+ZQuery1.FieldByName('k').AsString+','+ZQuery1.FieldByName('vn').AsString
      then begin // gleichen datensatz nicht mehr anschauen
       ZQuery2.next;
       continue;
      end;
      if (trim(ZQuery2.FieldByName('vt').AsString)) = '' then begin // wenn leerer datensatz dann weiter
       ZQuery2.next;
       continue;
      end;

         // === Eigentliche Anwendung
      if (  berechneB(ZQuery1.FieldByName('vt').AsString, ZQuery2.FieldByName('vt').AsString  ) >= ziel ) then begin       
       berechnung2 := berechnung2+ ZQuery2.FieldByName('a1').AsString+' '+ZQuery2.FieldByName('k').AsString+','+ZQuery2.FieldByName('vn').AsString+'/';;
       z:=z+1;
      end;

      ZQuery2.Next; //a) nächster Datensatz
    end; //for zweite schleife prüfung

	// [...]

    ZQuery2.First; //b) und jetzt wieder auf den Anfang setzen!
    ZQuery1.Next;
  end; // for erste Schleife




end;
    

Warf
Beiträge: 1679
Registriert: Di 23. Sep 2014, 17:46
OS, Lazarus, FPC: Win10 | Linux
CPU-Target: x86_64

Re: Doppelte Schleife und Zeit wird immer länger - Wie optimieren?

Beitrag von Warf »

Du kannst dir diese Berechnung wie eine Matrix vorstellen. Jeder eintrag in Datensatz 1 bildet eine spalte und jeder eintrag in Datensatz 2 eine reihe. Die felder dieser matrix sind dann deine Berechnungen die du machst. Dein Ergebnis ist dann einfach die Summe der berechnungen.

Also um deine Berechnung durchzuführen musst du jedes Feld dieser Matrix einmal besuchen. Daher ist die Anzahl an berechnungen Reihen*Spalten. In der Informatik spricht man von der Komplexität eines Problems, also wie viele berechnungen braucht man für einen Input einer bestimmten größe. Da du alle Zellen der Matrix ausrechnen musst um dein Problem zu lösen, ist die Komplexität Zwangsläufig in O(N*M) (für Datensatzgrößen N und M). Das O ist übrigens die Landau Notation und beschreibt die Größenordnung rein abbhängig von der Inputgröße. Also wenn du in einer Liste jedes Element mit jedem Vergleichen musst hast du O(N*N), aber auch wenn du das 2 oder 10 mal machen musst ist es auch in O(N*N), da es nur um die Größenordnung geht werden Konstante faktoren weggelassen.

Zurück zum Problem, also du kommst nicht drum rum alle Zellen zu berechnen, die Komplexität ist also O(N*M), deine einzige Möglichkeit ist zu versuchen N oder M möglichst zu reduzieren.
Z.B.

Code: Alles auswählen

      if (trim(ZQuery2.FieldByName('vt').AsString)) = '' then begin // wenn leerer datensatz dann weiter
       ZQuery2.next;
       continue;
      end;
Dieser Code ist effektiv identisch damit das du in die komplette Zeile deiner Matrix nichts reinschreibst, also wäre hier eine möglichkeit diese Zeile komplett zu ignorieren. Das machst du am besten indem du diese Zeile aus dem Datensatz für die berechnung rausnimmst (z.B. wenn es ein SQL query ist, einfach ein WHERE vt <> '') dranhängst. Du kannst auch den Datensatz vorher laden und alle Leeren Zeilen rausschmeißen.
Effektiv heist das dieser Test nicht im inneren Loop gemacht wird, sondern vorher, und somit nur einmal, statt für jede iteration des äußeren loops einmal gemacht wird (du damit M um 1 reduzierst und damit die Komplexität um 1*N).

Ansonsten hast du einfach ein Quadratisches Problem (also eins was in N^2 skaliert wenn wenn beide Datensätze in der selben Größenordnung sind). Quadratische Probleme sind aber nicht so schlimm. Da kann man relativ gut mit mehr Rechenleistung gegensteuern (Bei Polynomiellen Wachstum sind die Effekte von mehr Leistung auch Polynomiell). Deshalb werden solche Probleme für gewöhnlich als Effizient Lösbar bezeichnet.
Problematisch wird es bei Exponentiellem wachstum. Für jeden Weiteren Datensatz fügst du eine Dimension zu der Matrix hinzu, also bei 3 datensätzen hast du O(N^3), für 4 O(N^4) und so weiter. Wenn also die Anzahl an Datensätzen auch Variabel ist dann hat man O(N^M) und das ist exponentielles wachstum. Das ist tatsächlich ein riesen Problem, denn wenn du hier mehr leistung drauf wirfst bekommst du nur Logarithmisch mehr Arbeit geleistet, also wenn du deine Leistung verzehnfachst bekommst du nur linear mehr arbeit geleistet. Daher werden diese Probleme als nicht effizient lösbar bezeichnet.

Solang du also nur eine Feste Anzahl an Datensätzen versuchst zu berechnen ist alles noch relativ einfach. Wenn du in die Exponentielle Ecke kommst, kannst du eigentlich gleich aufgeben, diese Probleme skalieren nicht.

Das was du hier machst ist übrigens auch im grunde das gleiche was SQL bei einem Join macht. In der Relationalen Algebra (welche SQL unterliegt) gibt es dann ein set an optimierungen die Bewiesenermaßen optimal sind. Eine davon ist Filter so früh wie möglich anzuwenden, was im grunde das ist mit dem "vt <> ''" was ich oben beschrieben habe

charlytango
Beiträge: 500
Registriert: Sa 12. Sep 2015, 12:10
OS, Lazarus, FPC: Laz 2.0 fixes FPC 3.2 fixes
CPU-Target: Win 32Bit, 64bit
Wohnort: Wien

Re: Doppelte Schleife und Zeit wird immer länger - Wie optimieren?

Beitrag von charlytango »

Epcop hat geschrieben:
Mi 11. Mai 2022, 17:14
Gibt es irgendwelche Tricks um solche Vorgänge zu beschleunigen?
Zur besseren Verständlichkeit:
Eine "Datenbank" besteht aus 1 bis n Tabellen.
Du holst also "Datensätze" oder "Abfrageergebnisse" (was nicht immer das selbe ist) mittels SQL-Abfrage aus den Tabellen.
Aber einerlei...

Ich sehe im Code ein "SELECT *" was mich per se schon unrund macht. Denn der größte Performancegewinn (bei Abfragen) kann durch präzise Einschränkung der nötigen Daten erzielt werden. Denn Daten die nicht übertragen werden müssen, verbrauchen keine Zeit und auch keinen Speicherplatz auf dem Zielrechner.

Dann sehe ich zwei TZQueries mit dem gleichen SELECT .... grübel.
BTW... gib den Tabellen sinnvolle Namen, Aliase kannst du in SELECTs immer noch verwenden
"db" ist als Tabellenname für mich eher bedenklich/missverständlich.

Du steppst das erste Select durch und fragst deine erste Bedingung ab

Code: Alles auswählen

trim(ZQuery1.FieldByName('vt').AsString) = ''
Was bedeutet, du hast Daten geholt die du gar nicht brauchst. Dann steppst du das gleiche Select durch (ZQuery2), was praktisch einem manuellen Natural JOIN gleichkommt. Also ein JOIN von jedem Datensatz mit jedem. Damit hab ich in meiner Anfangszeit auch große Datenbanken gekillt gggg. Sowas dauert ewig und produziert eine riesige Datenmenge.
Der Administrator hatte immer besondere Freude wenn alle Entwicklungsdatenbanken blockiert waren.

Für mich sieht das so aus als ob du eine Datenbank nutzt aber in FlatFile-Tabellen oder dBase Tabellen denkst. Eine Datenbank kann viel mehr.

Daten die man nicht braucht holt man nicht ab, was du ins SELECT (per where-klausel) schreiben kannst.

Code: Alles auswählen

SELECT * 
FROM db a, ue b 
where a.bID = b.ID
  AND vt<>'';
und wenn ich deinen Code richtig interpretiere machst du den ganzen Aufwand um Datensätze aus zwei Tabellen zu holen die dieser Bedingung entsprechen:

Code: Alles auswählen

berechneB(ZQuery1.FieldByName('vt').AsString, ZQuery2.FieldByName('vt').AsString  ) >= ziel
Ich hoffe jetzt nicht dass die Funktion berechneB so komplex ist, aber ich vermute dass du Daten aus den Tabellen holen willst die >=ziel sind. Auch komplexere Berechnungen lassen sich direkt im SELECT erledigen.

Code: Alles auswählen

SELECT * 
FROM db a, ue b 
where a.bID = b.ID
  AND vt<>''
  AND StringToIntegerFunktion(vt)>=<ZIEL>;
wobei <ZIEL> durch deinen Wert ersetzt werden muss und StringToIntegerFunktion durch die jeweils spezifische Funktion der benutzen Datenbank (da hat jede ihren eigenen Funktionsumfang)

Was mich dann noch zu der Frage führt warum du in der Tabelle Spalten mit der Eigenschaft STRING hast, wenn du damit rechnen willst.

Unter der Annahme dass du die Spalte vt auf INTEGER setzt wäre das Select nur mehr:

Code: Alles auswählen

SELECT b,k,vn
FROM db a, ue b 
where a.bID = b.ID
  AND vt=<ZIEL>;
oder

Code: Alles auswählen

  sqla := 'SELECT b, k, vn 
               FROM db a, ue b 
               where a.bID = b.ID 
                    AND vt >= :ziel ; ';

  ZQuery1.Close;
  ZQuery1.SQL.Clear;
  ZQuery1.SQL.Add(sqla);
  ZQuery1.ParamByName('ziel').AsInteger := Ziel;
  ZQuery1.Open;  
  
wenn du den Zielwert sauber ins SQL Statement bringen willst.
Dann hättest du jenes Ergebnis das du vermutlich exportieren willst.
Das kannst du per Hand machen oder auch mittels TCSVExporter (Tab "Data Export" der Lazarus Komponentenpalette).

Wenn die Performance dann noch immer nicht zufriedenstellend ist, kann man an den Indizes der Datenbank schrauben (z.B. ein Index auf vt, denn ohne Index macht die DB dann das was du manuell versucht hast - einen Full Table Scan)

Alles nur meine 2cents unter der Annahme vieler Vermutungen -- die auch komplett falsch sein könnten
Zuletzt geändert von charlytango am Mi 11. Mai 2022, 20:53, insgesamt 2-mal geändert.

charlytango
Beiträge: 500
Registriert: Sa 12. Sep 2015, 12:10
OS, Lazarus, FPC: Laz 2.0 fixes FPC 3.2 fixes
CPU-Target: Win 32Bit, 64bit
Wohnort: Wien

Re: Doppelte Schleife und Zeit wird immer länger - Wie optimieren?

Beitrag von charlytango »

blöd geklickt... schäm :oops:

Benutzeravatar
corpsman
Lazarusforum e. V.
Beiträge: 1360
Registriert: Sa 28. Feb 2009, 08:54
OS, Lazarus, FPC: Linux Mint Mate, Lazarus GIT Head, FPC 3.0
CPU-Target: 64Bit
Wohnort: Stuttgart
Kontaktdaten:

Re: Doppelte Schleife und Zeit wird immer länger - Wie optimieren?

Beitrag von corpsman »

Was auch hilft ist "ineffiziente" zugriffe zu reduzieren

Code: Alles auswählen

// Select vt from ...
ZQuery1.FieldByName('vt').AsString
wird dann zu

Code: Alles auswählen

// Select vt from ...
ZQuery1.Fields([0]).AsString
Das brachte bei meinen Programmen auch schon extrem viel, weil das FieldByName anscheinend nicht das schnellste ist ...
--
Just try it

Benutzeravatar
af0815
Lazarusforum e. V.
Beiträge: 5235
Registriert: So 7. Jan 2007, 10:20
OS, Lazarus, FPC: FPC fixes Lazarus fixes per fpcupdeluxe (win,linux,raspi)
CPU-Target: 32Bit (64Bit)
Wohnort: Niederösterreich
Kontaktdaten:

Re: Doppelte Schleife und Zeit wird immer länger - Wie optimieren?

Beitrag von af0815 »

corpsman hat geschrieben:
Do 12. Mai 2022, 06:30
Das brachte bei meinen Programmen auch schon extrem viel, weil das FieldByName anscheinend nicht das schnellste ist ...
Dann ist ein SELECT * FROM das tödlichste was man machen kann. Nicht gleich, aber später umso sicherer.
Blöd kann man ruhig sein, nur zu Helfen muss man sich wissen (oder nachsehen in LazInfos/LazSnippets).

Benutzeravatar
corpsman
Lazarusforum e. V.
Beiträge: 1360
Registriert: Sa 28. Feb 2009, 08:54
OS, Lazarus, FPC: Linux Mint Mate, Lazarus GIT Head, FPC 3.0
CPU-Target: 64Bit
Wohnort: Stuttgart
Kontaktdaten:

Re: Doppelte Schleife und Zeit wird immer länger - Wie optimieren?

Beitrag von corpsman »

ok ein Select * from habe ich noch nie in einen Produktiven Code eingebaut, ich wähle meine Spalten die ich haben will immer aus.

Was aber auch geht, ist dass man sich das fieldbyname einmal aufruft und dann "merkt", während man mit query.next durchgeht. Dann wird das fieldbyname wenigstens nur 1 mal pro Abfrage aufgerufen und nicht bei jedem Zugriff.
--
Just try it

Epcop
Beiträge: 127
Registriert: Di 29. Mai 2012, 09:36

Re: Doppelte Schleife und Zeit wird immer länger - Wie optimieren?

Beitrag von Epcop »

Vielen Dank für die Ideen.
Ich bin noch beim übearbeiten meines codes. Ich schreibe dann wieder wenn ich fertig bin.

Benutzeravatar
af0815
Lazarusforum e. V.
Beiträge: 5235
Registriert: So 7. Jan 2007, 10:20
OS, Lazarus, FPC: FPC fixes Lazarus fixes per fpcupdeluxe (win,linux,raspi)
CPU-Target: 32Bit (64Bit)
Wohnort: Niederösterreich
Kontaktdaten:

Re: Doppelte Schleife und Zeit wird immer länger - Wie optimieren?

Beitrag von af0815 »

Es ist von der DB abhängig, wie man das optimieren kann. Ich würde komplexere Auswertungen in der Datenbank selbst optimieren, das mit dem MS-SQL Server und Transact SQL sehr gut.

Eine alternative ist, das ganze von der DB in Strukturen im Speicher zu bringen und dort zu bearbeiten. Wenn man genug Speicher hat.
Blöd kann man ruhig sein, nur zu Helfen muss man sich wissen (oder nachsehen in LazInfos/LazSnippets).

Antworten