Entwickler-Ecke

Algorithmen, Optimierung und Assembler - Suchalgo funzt nicht


AXMD - Fr 31.12.04 18:38
Titel: Suchalgo funzt nicht
Hi :)!

Ich programmiere ja seit einiger Zeit an einer Terminverwaltung; damit das Ganze von der Netzwerkauslastung her so schonend wie möglich werden soll, soll sich der Client natürlich nur die Termine holen, die er darstellt. Beispiel: April 2005 ist die aktuelle Ansicht; also benötigt der Client nur die Termine, die sich zwischen dem 1.4.2005 und dem 30.4.2005 befinden. Also habe ich zwei Funktionen geschrieben, die genau das machen: den ersten bzw. letzten Termin aus einem Zeitraum zu bestimmen und den Index (im Array) zurückzugeben. Hier der Code:


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:
47:
48:
49:
//* FindFirstDateIndexInPeriod
//************************************************
//* Find out the index of the first date in a certain date period
//* Parameters:
//    - Username
//    - Period start
//    - Period end
//* Result: Index (-1 if no date matches)
function FindFirstDateIndexInPeriod(Username: String; FirstDateTime, LastDateTime: TDateTime): Integer;
var
  idx, i, temp: Integer; //To save the date collection index
begin
  temp := -1//No match by default
  idx := DateCollectionIndex(Username);
  for i := 0 to High(DateArray[idx].DateCollection.Dates) do begin
    if (DateArray[idx].DateCollection.Dates[i].FromDateTime >= FirstDateTime) and (DateArray[idx].DateCollection.Dates[i].FromDateTime <= LastDateTime) then begin
      temp := DateArray[idx].DateCollection.Dates[i].Index;
      break; //Break loop because array is sorted!
      end;
    end;
  Result := temp; //Return result [-1 if no match found]
end;

//* FindLastDateIndexInPeriod
//************************************************
//* Find out the index of the last date in a certain date period
//* Parameters:
//    - Username
//    - Period start
//    - Period end
//* Result: Index (-1 if no date matches)
function FindLastDateIndexInPeriod(Username: String; FirstDateTime, LastDateTime: TDateTime): Integer;
var
  idx, i, temp: Integer; //To save the date collection index
  Start: Integer; //Index to start from (calls FindFirstDateIndexInPeriod)
begin
  idx := DateCollectionIndex(Username);
  Start := FindFirstDateIndexInPeriod(Username, FirstDateTime, LastDateTime); //Determine index to start from
  if Start = -1 then //No match found
    Start := 0//Start from beginning
  temp := Start; //Index of first date in period by default
  for i := Start to High(DateArray[idx].DateCollection.Dates) do begin
    if DateArray[idx].DateCollection.Dates[i].FromDateTime > LastDateTime then begin
      temp := DateArray[idx].DateCollection.Dates[i].Index - 1 {because FromDate already out of period};
      break; //Break loop because array is sorted!
      end;
    end;
  Result := temp; //Return result [Start if no match found]
end;


Vielleicht zur Info: das mit DateArray tut hier nichts zur Sache; ich hab nur grade keine Lust, den Code umzuschreiben (is ja der Originalcode ausm Programm). So: nun mein Problem: es werden immer die falschen Indizes zurückgegeben. Sogenau kann ich das leider nicht beschreiben; hier [http://www.users.fh-sbg.ac.at/~aunterwe/DSTP2.zip] könnt ihr das Prog. herunterladen und selbst testen. Hinweise zur Verwendung: Server mit init starten; mit "send adddate rand" (ohne ") ein paar Zufalls-Termine hinzufügen [listdates listet alle Termine auf] und dann die Funktionen aufrufen (entweder ffdiip oder fldiip - siehe auch cmds.txt).

Meine Frage: wo ist mein Denkfehler in diesem Code?

AXMD


BenBE - Sa 01.01.05 01:07

Kurze Frage zur Versicherung, hab den Source nicht durchgeschaut, aber entspricht Data[i].Index = i?

Weiterhin, kleine Optimierung: Result kann direkt zugewiesen werden, Temp entfällt dann.

Außerdem, weist du in Zeile 39-41, wenn kein StartDatum gefunden wird, 0 zu, anstatt -1, was auf Grund der Prüfung in FindFirstDateInPeriod zwar nicht notwendig ist. Wenn FindFirstDateInPeriod -1 zurückgibt, gilt dies automatisch auch für FindLastDateInPeriod, da ein erstes Datum existieren muss, damit es ein letztes geben kann.

Guck mal, ob der Fehler dann behoben ist ...


AXMD - Sa 01.01.05 01:12

BenBE hat folgendes geschrieben:
Kurze Frage zur Versicherung, hab den Source nicht durchgeschaut, aber entspricht Data[i].Index = i?

Ja

Zitat:
Weiterhin, kleine Optimierung: Result kann direkt zugewiesen werden, Temp entfällt dann.

Gut, danke ;)

Zitat:
Außerdem, weist du in Zeile 39-41, wenn kein StartDatum gefunden wird, 0 zu, anstatt -1, was auf Grund der Prüfung in FindFirstDateInPeriod zwar nicht notwendig ist. Wenn FindFirstDateInPeriod -1 zurückgibt, gilt dies automatisch auch für FindLastDateInPeriod, da ein erstes Datum existieren muss, damit es ein letztes geben kann.
Guck mal, ob der Fehler dann behoben ist ...


Damit wird der Fehler verschlimmert, weil er auf da -1te Element vom Array zugreift. Und da es das nicht gibt: ACCESS VIOLATION! ;)

AXMD


BenBE - Sa 01.01.05 01:44

AXMD hat folgendes geschrieben:
BenBE hat folgendes geschrieben:
Kurze Frage zur Versicherung, hab den Source nicht durchgeschaut, aber entspricht Data[i].Index = i?

Ja

Gut, dann solltest Du das aus Performance- und Übersichtsgründen auch glaich so ersetzen.

AXMD hat folgendes geschrieben:
Zitat:
Weiterhin, kleine Optimierung: Result kann direkt zugewiesen werden, Temp entfällt dann.

Gut, danke ;)

NP.

AXMD hat folgendes geschrieben:
Zitat:
Außerdem, weist du in Zeile 39-41, wenn kein StartDatum gefunden wird, 0 zu, anstatt -1, was auf Grund der Prüfung in FindFirstDateInPeriod zwar nicht notwendig ist. Wenn FindFirstDateInPeriod -1 zurückgibt, gilt dies automatisch auch für FindLastDateInPeriod, da ein erstes Datum existieren muss, damit es ein letztes geben kann.
Guck mal, ob der Fehler dann behoben ist ...


Damit wird der Fehler verschlimmert, weil er auf da -1te Element vom Array zugreift. Und da es das nicht gibt: ACCESS VIOLATION! ;)


Gut, ich wende Dir das mal auf deinen Source-Abschnitt an, so wie ich das meinte:

AXMD hat folgendes geschrieben:

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:
47:
48:
49:
50:
51:
//* FindFirstDateIndexInPeriod
//************************************************
//* Find out the index of the first date in a certain date period
//* Parameters:
//    - Username
//    - Period start
//    - Period end
//* Result: Index (-1 if no date matches)
function FindFirstDateIndexInPeriod(Username: String; FirstDateTime, LastDateTime: TDateTime): Integer;
var
  idx, i: Integer; //To save the date collection index
begin
  Result := -1; //No match by default
  idx := DateCollectionIndex(Username);
  for i := 0 to High(DateArray[idx].DateCollection.Dates) do 
  begin
    if (DateArray[idx].DateCollection.Dates[i].FromDateTime >= FirstDateTime) and (DateArray[idx].DateCollection.Dates[i].FromDateTime <= LastDateTime) then 
    begin
      Result := i; //Return result [-1 if no match found]
      break; //Break loop because array is sorted!
    end;
  end;
end;

//* FindLastDateIndexInPeriod
//************************************************
//* Find out the index of the last date in a certain date period
//* Parameters:
//    - Username
//    - Period start
//    - Period end
//* Result: Index (-1 if no date matches)
function FindLastDateIndexInPeriod(Username: String; FirstDateTime, LastDateTime: TDateTime): Integer;
var
  idx, i: Integer; //To save the date collection index
  Start: Integer; //Index to start from (calls FindFirstDateIndexInPeriod)
begin
  idx := DateCollectionIndex(Username);
  Result := FindFirstDateIndexInPeriod(Username, FirstDateTime, LastDateTime); //Determine index to start from
  If Result < 0 Then
    Exit;

  Start := Result; //Index of first date in period by default
  for i := Start to High(DateArray[idx].DateCollection.Dates) do 
  begin
    if DateArray[idx].DateCollection.Dates[i].FromDateTime > LastDateTime then 
    begin
      Result := I - 1; // {because FromDate already out of period};
      break; //Break loop because array is sorted!
    end;
  end;
end;


Ich hoffe, ich hab alles angepasst und nix übersehen. Aber ich weiß nicht, ob Du die Erfindung With-Anweisung schonmal entdeckt hast ;-) Die verkürzt den Source merklich und macht ihn nebenbei noch Übersichtlicher ;-)

Bei weiteren Fragen einfach nochmal melden ;-)