Funktion optimieren

[alzaimar]

Oh, da stimmt Einiges nicht;
1. Die Funktionen funktionieren alle nicht, weil sie auch für den Fall 'Wort111;Wort222' fälschlicherweise das 'Wort' finden. Das ist aber gar nicht in der Liste.

2. Ausserdem sind die AddK, Addit2 und Addit3 vom Aufwand O(n*m), wobei n die Länge der Liste und m die Länge des Wortes bezeichnet.

3. Abschließend ist das Testverfahren keins.

Hier ein Verfahren mit linearem Aufwand:

Delphi-Quellcode:

Function AddIfUnique (Const aList, aToken : String; aSep : Char) : String;
Var
  l,n : Integer;

  Function TokenExists : Boolean;
  Var
    i,j : Integer;

  Begin
    i := 0;
    j := 1;

    For i:=1 to l Do Begin
      If aList[i] = aSep Then // Separator gefunden? Vergleich initialisieren
        j := 1
      Else if (j>0) Then                  // Wir vergleichen das j.te Zeichen
        If aList[i] = aToken[j] Then      // das passt....
          If (j = n) Then                 // wurde das ganze Wort verglichen ?
            If (i = l) Or (aList[i+1] = aSep) Then Begin // und danach kommt
              Result := True;             // ein Separator? Dann sind wir
              Exit;                       // fertig.
              End
            Else                          // Ansonsten Vergleich bis zum
              j := 0                      // nächsten Separator ausschalten
          Else                            // Vergleich ok, also nächsten 
           Inc (j)                        // Buchstaben des Wortes anvisieren.
        Else                              // Vergleich bis zum nächsten
          j := 0;                         // Separator ausschalten
      End;
    Result := False
  End;

Begin
  l := Length (aList);
  n := Length (aToken);
  If TokenExists Then
    Result := aList
  Else If l = 0 Then  // Beim ersten Mal nur den Token liefern
    Result := aToken
  Else Begin
    Result := aList;  // sonst ';'Token anhängen
    SetLength (Result, l + n + 1);
    Result [l+1] := aSep;
    Move (aToken[1], Result [l+2], n);
    End
End;

Testverfahren:
Eine Wortliste bestehend aus 4000 Wörtern WortX (X=1...4000), durch ';' getrennt, wird erstellt.

a) 4000x wird "Wort[i]" eingefügt (schlägt fehl, da schon in der Liste)
b) 4000x wird "Wort[i]*" eingefügt. (klappt immer)

AddIfUnique a) : 661
AddIfUnique b) : 3645

AddIt3 a) : 6059
AddIt3 b) : 10485

Da ist bestimmt noch Optimierungspotential drin.