Doppelte Einträge in Array filtern

[dominikkv]

Hi

Ich suche in einem Array of String (vereinfacht) und bekomme als Ergebnis nen Array of ^String:
SuchErgebnis: Array of ^String; in diesem können allerdings Einträge doppelt vorkommen.
Ich suche nun die beste (und schnellste!) Möglichkeit doppelte Einträge zu finden.
Soll heißen zum Schluss möchte ich ein
EndErgebnis: Array of ^String haben der keine doppelten Einträge hat!

Bisher mache ich das so:

Delphi-Quellcode:

var Gefunden: Boolean;
    I, J: Cardinal;
begin
  SetLength(EndErgebnis, 1);
  EndErgebnis[0] :=  Addr(SuchErgebnis[0]^);  // SuchErgebnis hat IMMER mindestens einen Eintrag
  for I := 1 to high(SuchErgebnis) do
    begin
      gefunden := false;
      for J := 0 to high(EndErgebnis) do
        if EndErgebnis[J]^ = SuchErgebnis[I]^ then
          begin
            gefunden := True;
            break;
          end;
      if not gefunden then
        begin
          SetLength(EndErgebnis, Succ(Length(EndErgebnis)));
          EndErgebnis[high(EndErgebnis)] := Addr(SuchErgebnis[I]^);
        end;
    end;  // for I
end;

Bei 25000 Suchergebnissen dauert das ca 1-2 Sekunden.
Hat jemand ein Optimierungsvorschlag?

mfg.Dominik

[Klaus01]

Hallo,

bis Du auf ein Array festgelegt?
Wenn nicht schaut Dir mal die TStringList an, da kannst Du mit
den Optionen "sorted" und "DupIgnore" arbeiten.

Grüße

[dominikkv]

hmm bei der StringList muss ich aber mit strings arbeiten und nicht mit pointern, was ich glaube um einiges langsamer ist.

[grenzgaenger]

sag mal, ist dein array sortiert? falls nicht, würde ich es dir dringend anraten, dann kannste auch recht perfomant prüfen ob der string enthalten ist und ggf. diesen gar nicht einfügen, oder mit EINEM durchlauf die duplikate entfernen.

im anderen fall, ist deine routine ziemlich optimal... und du wirst dich an die zeiten (und längere) gewöhnen müssen...

[FAlter]

Hi,

Zitat von dominikkv:

hmm bei der StringList muss ich aber mit strings arbeiten und nicht mit pointern, was ich glaube um einiges langsamer ist.

Ist dir bewusst, wie ein (Ansi/Wide)String Delphi-intern aufgebaut ist? Es handelt sich um einen Zeiger auf das erste Zeichen. Vorher stehen 4 Bytes für die Länge, nach dem letzten Zeichen kommt noch #0. Ein ^String wäre also genaugenommen ein Zeiger auf einen Zeiger (außer bei {$H-}).

Und wenn du a^ := b^ machst, kommst du bestimmt nicht schneller als mit c := d (wobei a und b ^String und c und d normale Strings sind). In deinem Code sehe ich keinen Grund, nicht direkt Strings zu verwenden.

Mfg
FAlter

[dominikkv]

ähh ja ist mir klar... nur mein String ist eigendlich ein
String255 = String[255]; und somit
SuchErgebnis, EndErgebnis: Array of ^String255 Sry hätte ich vllt erwähnen sollen... nur ich wollte das so unkompliziert wie möglich machen, damit das verstanden wird.
SuchErgebnis ist darüber hinaus in Wirklichkeit ein String255 in einem Record in einem Record -.-

Ich were mal schauen ob ich die ganzen SetLength in der schleife umgehen kann... vllt bringts ja was

[marabu]

Hallo Dominik,

bedenke, dass für jeden ShortString der maximal benötigte Speicherplatz reserviert wird - AnsiStrings sind da viel ökonomischer.

Delphi-Quellcode:

procedure ExtractUniqueStrings(list, result: TStrings);
var
  temp: TStringList;
begin
  temp := TStringList.Create;
  temp.Sorted := True;
  temp.Duplicates := dupIgnore;
  try
    temp.Assign(list);
    result.Assign(temp);
  finally
    temp.Free;
  end;
end;

Grüße vom marabu

[dominikkv]

Allerdings brauche ich um Strings in eine Datei zu speichern eine finalization, geht also nur mit ShortStrings.
Ich werde trotzdem mal die StringList ausprobieren...