Variable mit mehreren Werten vergleichen ohne "OR" ?

[Tyrael Y.]

Wie wäre es, wenn du die Strings in einem TStringHash verwaltest und dann nur noch innerhalb des Hashes suchst?

Guck dir mal folgendes an.

Hashes

[negaH]

@Mabuse:

Delphi-Quellcode:

// statt '#' kann natürlich auch alles andere genommen werden ;-)
  if pos('#'+Bezeichnung+'#', '#rohr#schraube#schraubendreher#')>0 then ....

ja könnte man, zb.

  if pos('-' + Bezeichnung + '-', '-rohr-schraube-schraubendreher-')>0 then .... ups das hatte ich doch schon 4 Threads vorher gepostet

[edit]
Mist, hat Mabuse auch schon erkannt.
Liest überhaupt einer die blöde rote Box bevor man postet, ich nicht
[/edit]


Die beste Lösung ist die 2. von Mabuse, aus Sicht des besten Codes, allerdings mit kleinen Änderungen:

Delphi-Quellcode:

function IndexOf(const Value: String; const List: array of String): Integer;
var
  I: Integer;
begin
  Result := -1;
  for I := Low(List) to High(List) do
    if Value = List[I] then
    begin
      Result := I;
      Break;
    end;
end;

procedure TestIt(Bezeichnung: String);
begin
  case IndexOf(Bezeichnung, ['rohr', 'schraube', 'schraubendreher']) of
     0: machwas; // 1. String (rohr)
     1: machwas; // 2. String (schraube)
     2: machwas; // 3. String (schraubendreher)
    -1: machnichts; // nicht gefunden
  end;
end;

1.) const Parameter machen die Sache effizienter vom erzeugten Code. Besonders beim const List: array of String ist das enorm wichtig. Denn nun wird unser Array[] im Source das wir übergeben -> ['rohr', 'schraube', 'schraubendreher'] durch den Compiler hardcoded als fertiges Array[] im Code abgelegt. Also auch wenn man vermuten würde das zur Laufzeit unser dynamisches Array[] erst erzeugt wird und die 3 Strings darin eingefügt werden, so passiert eben dies nicht. Aber nur wenn wir konstante Arrays[] benutzen. Denn wenn nicht so wird die Funktion IndexOf() uU. eine komplette Kopie des übergebenen Atrrays anlegen.

2.) du musst nicht zweimal in der Liste Suchen, ein case of reicht aus, also ohne if then vorher.

Gruß Hagen

[Karstadt]

Hallo. Sehr viele Lösungsansätze. Sehr gut!

Wie kann ich erfahren wie schnell jeder einzelne Lösung ist? Sind das "gewaltige" unterschiede? Oder minimale?

das z.B. verwende ich sehr oft in meine Anwendung:

Delphi-Quellcode:

Procedure Gegenstand(Bezeichnung:String);
var
  sl : TStringList;
begin
  sl := TStringList.Create;
  sl.CaseSensitive := true;
  sl.DelimitedText := 'rohr, schraube, schraubendreher';
  IF sl.IndexOf(Bezeichnung) > -1 then
    ShowMessage(Bezeichnung + ' ist enthalten.');
  sl.Free;
end;

Wenn ich ein Eintrag in COMBOX Selektiren möchte.. Somit würde ja diese Funktion hervoragend passen (bessere Lesbarkeit, da ich solchen code (Struktur) sehr oft angewendet habe. Aber ist das SEHR langsam? Wie kann ich das in Zukunft selber "spüren" ? bei 1000 Einträgen?

[negaH]

Zitat:

Wie kann ich erfahren wie schnell jeder einzelne Lösung ist? Sind das "gewaltige" unterschiede? Oder minimale?

Je nach Datenmenge sind es gewaltige Unterschiede, vom schlechtesten zum besten sortiert

1.) TStringList
2.) IndexOf() ohne binärer Suche
3.) Pos()
4.) BoyerMoorePos()
5.) IndexOf() aber mit binärer Suche, statt wie oben einfach linear
6.) Trees wie mein DAWG
7.) Hash-Vergleich

Noch ein par Bemerkungen:

7.) Hash-Vergleich meint KEINE Hash-StringListe oder so ein Quatsch. Man sucht eine geeignetes Prüfsummenverfahren das für alle zu suchenden String in der Liste eine eindeutige Zahl liefert, zb. eine 32Bit Zahl. Diese Zahlen erzeugt man einmalig und kann dann so sehr sehr effizient vergleichen

Delphi-Quellcode:

case Pruefsumme(Bezeichnung) of
$12345678: ;
$AB450CDE: ;
$DFFFFF12: ;
// usw. usf.
end;

Dh. in dieser Methode wird nur ein String real bearbeitet, nämlich der Suchstring Bezeichnung wir byteweise durch Prüfsumme umgewandelt. Danach gibnt es KEINE weiteren realen Stringvergleiche mehr.

Eine Hash-Liste empfehle ich niemals, da diese immer nur auf bestimmte Probleme bezogen ihren Aufwand lohnen.
Trees benötigen fast immer mehr Speicher sind aber abgesehen von obiger Prüpfsummen-Methode die schnellste Lösung.

Pos() ist schnell implementiert aber schlecht zu warten und nicht sonderlich schnell. Aber weitaus sachneller als

eine TStringList jedesmal zu erzeugen, dann mit dem langsammen CommaText oä. die Liste zuzuweisen, dann vielleicht noch sortieren und dann erst darin suchen, und dann die Liste wieder freigeben. Uff, schon beim Schreiben dieses Satzes wird mir schlecht.

Die Beste Lösung bei nur wenigen Strings in der Liste dürfte die 2. von Mabuse sein -> IndexOf() habe ich si mal genannt. Hier erzeugt der Compiler schonmal eine schöne hardcoded Datenstruktur aller Strings im Codesegement. Also keinerlei Allokationen oder Deallokationen dieser "Liste" mehr notwendig. Sortiert man diese Strings noch von Hand und benutzt in IndexOf() eine binäre Suche so ergibt sich ein ziemlich effizientes Verfahren das auch bei zb. 1024 Strings nur 11 Vergleiche benötigt.

Aber es würden eben noch 11 * 2 Stringzugriff für diese Vergleiche notwendig sein, bei der TStringList wären dies ca. 512 pro Suche. Bei den Hash-Prüfsummen würde man denoch nur 1 String umwandeln in einen 32Bit Wert und diesen dann vergleichen in der CASE OF Abfrage, würde ja bei den anderen Verfahren ebenfalls notwendig sein.

Das Problem bei der Hash-Prüfsummen-Methode ist es das man erstmal eine geeignete Funktion finden muß die bei allen Strings eine wirklich eindeutige Prüfsumme erzeugt. Wenn man davon ausgehen kann das der Wert in Bezeichnung nur aus Werten bestehen kann die in der zu suchenden Liste vorkommen dann ist das noch effizient möglich, sonst aber nicht.

Wie gesagt: am elegantesten ist die const Array[] Methode, rein schon vom sauberen Eindruck den der Source macht und von der sich ergebenden Performance ist sie ein supere Kompromiss. Um längen besser als diese elende TStringList Rechnereien. (hab den Eindruck das es ausreichend ist einem Delphicoder die TStringList zu erklären, mehr benötigt er nicht )

Gruß Hagen

[MaBuSE]

Zitat von negaH:

@Mabuse:
Mist, hat Mabuse auch schon erkannt.
Liest überhaupt einer die blöde rote Box bevor man postet, ich nicht

Ich habe keine rote Box bekommen.
Aber ich ärgere mich dann immer über mich selbst, da es zeigt, wie langsam man doch antwortet.
(Inkl. Delphi Start, e-Mail lesen, ...)

Zitat von negaH:

Die beste Lösung ist die 2. von Mabuse, aus Sicht des besten Codes, allerdings mit kleinen Änderungen:

Danke, ein Lob von Hagen ist gleich doppelt so viel wert

Zitat von negaH:

2.) du musst nicht zweimal in der Liste Suchen, ein case of reicht aus, also ohne if then vorher.

Es war als entweder - oder gedacht. (ein Beispiel halt)

Da Karstdt im 1. Post ein if in seinem Code hatte,
ich aber die case Variante zeigen wollte

[negaH]

Zitat:

Danke, ein Lob von Hagen ist gleich doppelt so viel wert Mr. Green

Hm naja, sind wir doch mal ehrlich. Dein Vorschlag sieht super sauber aus, ist somit enorm leicht verständlich, und wenn man die Arbeitsweise des Compilers kennt so weiß man auch das der erzeugte Laufzeitcode auch relativ effizient ist im Vergleich zu TStringList oder allen anderen dynamisch zu erzeugenden Listenobjekten. Klar, natürlich nur aus Sicht wie in diesem Beispiel, denn bei zb. 1024 Wörtern in unserer Liste wird das Array[] im Source schon wieder ziemlich unübersichtlich und die meistens nachfolgenden CASE OF Abfrage wird durch den Compiler dann so ineffizient implementiert (als lineare Vergleichsliste mit Sprungmarken). Alleine die CASE OF Abfrage würde also bei 1024 Suchbegriffen im Durchschnitt 512 solcher bedingten Sprünge ausführen und morderne CPUs hassen quasi solche Branches und verlieren dabei enorm an Durchsatz/Performance.

Also: bei kleinen Listen mit > 3 aber oft < 32 Einträgen ist die Array[] Methode die eleganteste und stellt den besten Kompromiss dar. Wenn man jetzt noch die IndexOf() Funktion um drei Features erweiteren würde

1.) Suche mit und ohne Berücksichtigung der Groß/Kleinschreibung
2.) Suche per Binärer Suche
3.) Partielle Suche, dh. der erste Eintrag der die längste Übereinstimmung mit dem Suchmuster hat wird gefunden, statt keinem Resultat.

dann wäre sie ein idealer Beitrag für die CodeLib.

Gruß hagen

[MaBuSE]

Zitat von negaH:

...und die meistens nachfolgenden CASE OF Abfrage wird durch den Compiler dann so ineffizient implementiert (als lineare Vergleichsliste mit Sprungmarken). Alleine die CASE OF Abfrage würde also bei 1024 Suchbegriffen im Durchschnitt 512 solcher bedingten Sprünge ausführen und morderne CPUs hassen quasi solche Branches und verlieren dabei enorm an Durchsatz/Performance.

Was hällst Du denn von folgender Idee:

Wenn der Vergleich (case) im Programm häufig vorkommt (z.B. in einer Schleife), könnte man ja statt dem Case ein array of procedure verwenden, das zuvor initialisiert wurde.
Das müsste doch funktionieren, oder?

Delphi-Quellcode:

var
  i: Integer;
  machWas: array of procedure;
...
begin
... 
  while (...) do
  begin
...
    i := IndexOf(s, [...]); // [...] -> viele Einträge
    if i>-1 then machWas[i]
            else machNix; 
...

[MaBuSE]

Zitat von MaBuSE:

Das müsste doch funktionieren, oder?

Ich habe es mal getestet, es funktioniert

Jetzt nur noch die Frage ist es schnell?
Ich glaube schneller als ein Case schon (ohne Init)

Delphi-Quellcode:

var
  i: Integer;
  machWas: array of procedure;
...
procedure rohr;
...
procedure schraube;
...
procedure schraubendreher;
...
begin
  // ein mal init
  SetLength(machWas, 3)
  machwas[0] := rohr;
  machwas[1] := schraube;
  machwas[2] := schraubendreher;
... 
  while (...) do
  begin
...
    // vielfacher Aufruf (z.B. in Schleife)
    i := IndexOf(s, ['rohr', 'schraube', 'schraubendreher']); 
    if i>-1 then machWas[i]
            else machNix; 
...

(Mit procedure of object könnte man natürlich auch Methoden in das Array legen )

[Hawkeye219]

Hallo MaBuSE,

hier eine Erweiterung deiner Idee:

Delphi-Quellcode:

// uses StrUtils (AnsiIndexText)

procedure MachNix;
begin
end;

procedure rohr;
begin
end;

procedure schraube;
begin
end;

procedure schraubendreher;
begin
end;

const
  JumpTable: array [-1..2] of procedure = (MachNix, rohr, schraube, schraubendreher);

var
  s : string;
  i : Integer;
begin
  s := 'ScHrAuBe';
  i := AnsiIndexText(s, ['rohr', 'schraube', 'schraubendreher']);
  JumpTable[i];
end;

Gruß Hawkeye

[negaH]

JumpTable[AnsiIndexText(s, ['rohr', 'schraube', 'schraubendreher'])]; und ja ist sehr schnell da nur ein Lookup in einer festen Tabelle entsteht und dann ein call ausgeführt wird. Schneller als jede CASE OF Abfrage.

AnsiIndexText() kannte ich noch garnicht, in D5 gibts die noch nicht. Hast du mal in die Implementierung geschaut wie Borland die Suche implementiert hat ?

Jetzt müsste man noch eine Funktion schreiben die den CALL der durch den Compiler erzeugt wird ersetzt durch einen CALL zu einer nested Procedure. Dadurch ist es möglich die Procedures lokal und nested zu codieren und innerhalb dieser Procedures kann man auf den übergeordneten Stack zugreifen. Also wie gewohnt bei nested Funktionen. Das macht dann den Source noch übersichtlicher.

Gruß Hagen