AGB  ·  Datenschutz  ·  Impressum  







Anmelden
Nützliche Links
Registrieren
Zurück Delphi-PRAXiS Sprachen und Entwicklungsumgebungen Object-Pascal / Delphi-Language Delphi Schnellster Stringmatching-Algorithmus in ASM übersetzen

Schnellster Stringmatching-Algorithmus in ASM übersetzen

Offene Frage von "Sereby"
Ein Thema von alzaimar · begonnen am 5. Dez 2007 · letzter Beitrag vom 3. Jul 2008
Antwort Antwort
Seite 1 von 8  1 23     Letzte » 
alzaimar
(Moderator)

Registriert seit: 6. Mai 2005
Ort: Berlin
4.956 Beiträge
 
Delphi 2007 Enterprise
 
#1

Schnellster Stringmatching-Algorithmus in ASM übersetzen

  Alt 5. Dez 2007, 22:30
Hi ASM profis,

Ich habe hier einen wirklich schnellen Stringmatching-Algorithmus (also, sowas wie 'POS'), der aber wesentlich schneller als POS ist (2-20x).

Ich möchte gerne testen, ob dieser Algorithmus in Assembler noch (und vor allen Dingen, um wieviel) schneller ist. Er ist relativ simpel. Er basiert auf dem QuickSearch-Algorithmus von Daniel Sunday, mit einer Optimierung von mir. Diese wurde von Timo Raita (University of Turku) angeregt. Seine Arbeit behandelt diese Optimierung im Rahmen des Boyer-Moore Algorithmus.

Hier der Algorithmus. Er verwendet eine Sprungtabelle, die pro Substring nur einmal angelegt werden muss. Dieses Optimierungspotential interessiert mich aber jetzt nicht...

Hier der Algorithmus;
Delphi-Quellcode:
Function QSSearch(Const sSubStr, sText: String): Integer;
Var
  j, i, k, iTextLength: Cardinal;
  n, n1, n2: Cardinal;
  c1, cp: Char;
  Skip: Array[Char] Of Cardinal;
  c: Char;
  pPtr: Pointer;

Begin
  n := Length(sSubStr);
  c1 := sSubStr[1];
  cp := sSubStr[n];
  n1 := n - 1;
  n2 := n - 2;
  pPtr := @sSubStr[2];

  For c := Low(Char) To High(Char) Do
    Skip[c] := n + 1;
  For i := 1 To n Do
    Skip[sSubStr[i]] := n - i + 1;

  i := 1;
  j := 1;
  iTextLength := Length(sText);
  k := iTextLength - n + 1;
  While i < k Do Begin // Bei PChar: i <= k
    If (c1 = sText[i]) And (cp = sText[i + n1]) Then
      If (n < 3) Or CompareMem(@sText[i + 1], pPtr, n2) Then Begin
        Result := i;
        Exit;
      End;
    inc(i, Skip[sText[i + n]]); // Bei PChar und i=k ist sText[i+n] = #0, bei Strings erfolgt ein Überlauf
  End;

// Wegen o.g. Kommentare (PChar vs. String) Muss man hier eine extra Abfrage einbauen, ob
// der String nicht ganz am Ende auftaucht...
  Result := 0;
  If i = k Then
    If (c1 = sText[i]) And (cp = sText[i + n1]) Then
      If (n < 3) Or CompareMem(@sText[i + 1], pPtr, n2) Then
        Result := i;
End;
Im Prinzip geht es darum: Sei ABCDE (=T) mein Text, und ich suche nach 'CDE' (=S)
Ich fange an, und vergleiche die letze Stelle von S mit der 3.Stelle von T (weil len(S)=3). Wenn die beiden ungleich sin, und T[3] gar nicht in S vorkommt, kann ich gleich 3(!) Stellen nach rechts hüpfen. Kommt T[3] in S vor, dann entsprechend weniger. Das wird durch die 'Skip'-Tabelle festgelegt. Wenn die beiden Zeichen jedoch gleich sind, vergleiche ich T[1] mit S[1]. Stimmt das auch, vergleiche ich den Rest (das ist übrigens die Optimierung von Timo Raita: Kleine Ursache, riesen Wirkung)

Je länger der zu suchende Text, desto schneller (im Mittel) der Algorithmus.

Man kann natürlich noch die Startposition mit übergeben (das wäre dann die Zeile mit dem '***')

Ach, er klappt sowieso nur für Suchstrings mit mehr als einem Zeichen...

Also, hat Jemand Bock, das Teil in ASM zu übersetzen (oder sonstwie schneller zu machen)? Haben ja schließlich alle was davon....

Bin mal gespannt....

[Edit]Fehlerhafte Version rausgeschmissen. Kommt davon, wenn man aus einer PChar in Strings umwandelt und ungenügend testet...[/edit]

[edit]
hier der Code von Sunday aus Charras & Lecroq
Code:
void preQsBc(char *x, int m, int qsBc[]) {
   int i;

   for (i = 0; i < ASIZE; ++i)
      qsBc[i] = m + 1;
   for (i = 0; i < m; ++i)
      qsBc[x[i]] = m - i;
}


void QS(char *x, int m, char *y, int n) {
   int j, qsBc[ASIZE];

   /* Preprocessing */
   preQsBc(x, m, qsBc);
 
   /* Searching */
   j = 0;
   while (j <= n - m) {
      if (memcmp(x, y + j, m) == 0)
         OUTPUT(j);
      j += qsBc[y[j + m]];              /* shift */
   }
}
[/edit]
Angehängte Dateien
Dateityp: zip test-project_158.zip (1,9 KB, 52x aufgerufen)
"Wenn ist das Nunstruck git und Slotermeyer? Ja! Beiherhund das Oder die Flipperwaldt gersput!"
(Monty Python "Joke Warefare")
  Mit Zitat antworten Zitat
Amateurprofi

Registriert seit: 17. Nov 2005
Ort: Hamburg
1.039 Beiträge
 
Delphi XE2 Professional
 
#2

Re: Schnellster Stringmatching-Algorithmus in ASM übersetzen

  Alt 6. Dez 2007, 04:34
@alzaimar:
Sieht ja sehr schön aus, kann aber meines Erachtens nicht funktionieren.

Nehmen wir mal an :
sText hat die Länge 100 und enthält nur 'A's
sSubStr ist 'BBBBB'

Vor der While-Schleife wird definiert:
n := 5; // Length(sSubStr)
j := 1;
iTextLength := 100; // Length(sText)
k := 95; // iTextLength - n;

Innerhalb der While-Schleife wird ausschließlich i verändert, also
haben wir nach Beendigung der While-Schleife folgenden Zustand
iTextLength = 100
k = 95
j = 1

Und nun kommt der Abschluß der Routine
Delphi-Quellcode:
  If j <= iTextLength + 1 Then
    Result := k + 1
  Else
    Result := 0;
j wird jetzt sicherlich <= iTextLength + 1 sein, also wird Result = k + 1 gesetzt,
und die Funktion wird als Fundstelle 96 ausgeben.
Gruß, Klaus
Die Titanic wurde von Profis gebaut,
die Arche Noah von einem Amateur.
... Und dieser Beitrag vom Amateurprofi....
  Mit Zitat antworten Zitat
alzaimar
(Moderator)

Registriert seit: 6. Mai 2005
Ort: Berlin
4.956 Beiträge
 
Delphi 2007 Enterprise
 
#3

Re: Schnellster Stringmatching-Algorithmus in ASM übersetzen

  Alt 6. Dez 2007, 07:34
Au Backe, falsche Version... Na ja. Hab oben die Richtigere reingestellt.
"Wenn ist das Nunstruck git und Slotermeyer? Ja! Beiherhund das Oder die Flipperwaldt gersput!"
(Monty Python "Joke Warefare")
  Mit Zitat antworten Zitat
Benutzerbild von SirThornberry
SirThornberry
(Moderator)

Registriert seit: 23. Sep 2003
Ort: Bockwen
12.235 Beiträge
 
Delphi 2006 Professional
 
#4

Re: Schnellster Stringmatching-Algorithmus in ASM übersetzen

  Alt 6. Dez 2007, 08:04
in asm übersetzen ist einfach. Schau dir einfach das CPU-Fenster an in Delphi oder nimm einen Disassembler.

Delphi-Quellcode:
For c := Low(Char) To High(Char) Do
  Skip[c] := n + 1;
Und anstelle des Aufrufs von comparemem könnte man den Code vielleicht direkt dort plazieren um zu vermeiden das erst auf den Stack gepackt wird und später wieder davon runter genommen wird.

das nächste ist folgendes
Delphi-Quellcode:
If j <= iTextLength + 1 Then
  Result := k + 1
Else
  Result := 0;
Die Prüfung ist falsch. Wie du bereits mitbekommen hast funktioniert die Funktion nicht wenn n = iTextLength.

Und wie ich grad noch mitbekommen hab. Wenn n > iTextLength kommen völlig falsche Ergebnisse raus (auf Grund eines Überlaufes)

Bevor man also die Geschwindigkeit der Funktion optimiert sollte man solche Fehler unbedingt beseitigen. Solange solche Fehler drin sind ist ein Geschwindigkeitsvorteil gegenüber einer funktionierenden Funktion uninteressant. (denn was bringt mir eine schnelle nicht funktionierende Funktion?)

[Edit]
ok, da war wohl noch eine falsche Version hochgeladen
[/Edit]
Jens
Mit Source ist es wie mit Kunst - Hauptsache der Künstler versteht's
  Mit Zitat antworten Zitat
alzaimar
(Moderator)

Registriert seit: 6. Mai 2005
Ort: Berlin
4.956 Beiträge
 
Delphi 2007 Enterprise
 
#5

Re: Schnellster Stringmatching-Algorithmus in ASM übersetzen

  Alt 6. Dez 2007, 08:27
Hi Sir Thornberry,

In ASM übersetzen UND/ODER schneller machen, darum geht es.

Das CompareMem wird i.a. relativ selten aufgerufen, hier steckt also kaum Potential. Ich hatte eine PChar-Variante, aber die ist einfach zu langsam.
"Wenn ist das Nunstruck git und Slotermeyer? Ja! Beiherhund das Oder die Flipperwaldt gersput!"
(Monty Python "Joke Warefare")
  Mit Zitat antworten Zitat
Benutzerbild von SirThornberry
SirThornberry
(Moderator)

Registriert seit: 23. Sep 2003
Ort: Bockwen
12.235 Beiträge
 
Delphi 2006 Professional
 
#6

Re: Schnellster Stringmatching-Algorithmus in ASM übersetzen

  Alt 6. Dez 2007, 08:35
kaum potenzial ist aber auch potenzial Wenn du das ganze fixer haben willst und an mehreren Stellen auf minimale Geschwindigkeitsgewinne verzichtest kommt am ende auch kein großer Geschwingigkeitsvorteil dabei heraus.
Jens
Mit Source ist es wie mit Kunst - Hauptsache der Künstler versteht's
  Mit Zitat antworten Zitat
Benutzerbild von sirius
sirius

Registriert seit: 3. Jan 2007
Ort: Dresden
3.443 Beiträge
 
Delphi 7 Enterprise
 
#7

Re: Schnellster Stringmatching-Algorithmus in ASM übersetzen

  Alt 6. Dez 2007, 08:49
Viel Potenzial sehe ich auf Anhieb nicht. Man könnte die Sprungtabelle schon mal hard codieren (aber sowas hast du sicher eh schon vor).
Evtl. kann man die Register effektiver nutzen. Ansonsten ist Delphi in der Optimierung schon nicht schlecht.
Und bei Comparemem ... der überprüft erst in 4 Byte-Schritten und wenn da alles geklappt hat, vergleicht er nochmal alles in Byte-Schritten.
Edit: Irrtum bei Comparemem. Der überprüpft die Bytes nicht nochmal von vorn (Habe zuerst das AND EDX,3 übersehen, was ich grad einfügen wollte )
Also: kein Potenzial
Dieser Beitrag ist für Jugendliche unter 18 Jahren nicht geeignet.
  Mit Zitat antworten Zitat
QuickAndDirty

Registriert seit: 13. Jan 2004
Ort: Hamm(Westf)
1.882 Beiträge
 
Delphi 12 Athens
 
#8

Re: Schnellster Stringmatching-Algorithmus in ASM übersetzen

  Alt 6. Dez 2007, 08:50
Wenn das letzte Zeichen des gesuchten Strings, im gesuchten string nochmal vorkommt wird es nihct gehen ne?


Gesucht
S=ADD
in
T=abADDcfgh

ich vergleiche S[3] mit T[3] und springe dann 3 weiter ja?

und dann?

Ich hab mir nur deine beschreibung durchgelesen den Code sehe ich mir gleich noch mal an.
Vielleicht gebt es das Problem im Code ja garnicht.

[Edit]
OK die skip Tabelle löst das Problem, schon gut hab nichts gesagt
[/EDIT]
Andreas
Monads? Wtf are Monads?
  Mit Zitat antworten Zitat
alzaimar
(Moderator)

Registriert seit: 6. Mai 2005
Ort: Berlin
4.956 Beiträge
 
Delphi 2007 Enterprise
 
#9

Re: Schnellster Stringmatching-Algorithmus in ASM übersetzen

  Alt 6. Dez 2007, 09:16
@sirius: Mit direkten PChar in ASM zu arbeiten, würde nichts bringen? Wenn ich das in Delphi mache (in PChar umwandeln) kann ich mir die blöde Abfrage am Ende zwar sparen, dafür wird der Code aber um ein Vielfaches langsamer.

Kann man da gar nichts machen?

Und was meinst du mit 'Sprungtabelle hart codieren'?
"Wenn ist das Nunstruck git und Slotermeyer? Ja! Beiherhund das Oder die Flipperwaldt gersput!"
(Monty Python "Joke Warefare")
  Mit Zitat antworten Zitat
QuickAndDirty

Registriert seit: 13. Jan 2004
Ort: Hamm(Westf)
1.882 Beiträge
 
Delphi 12 Athens
 
#10

Re: Schnellster Stringmatching-Algorithmus in ASM übersetzen

  Alt 6. Dez 2007, 09:22
zum Optimieren:
du kannst dir die vergleiche in der While Schleife (i > k) sparen
und eine
While true do
Schleife nehmen

wenn du vorher am ende von SText für einen garantierten Treffer sorgst!!! (Methode von Wirth der Typ von Pascal)
Das ist zwar nicht so einfach weil do eine art PosEx auf die letzen length(sSubstring) zeichen in sText ausführen must
um heraus zufinden welche der zeichen von sSubstring noch angehängt werden müssen, aber dann sollte es gehen.

Beispiel 1
S=FG
T=ABCDEFGHIJKLMN

anhängen
ABCDEFGHIJKLMNFG

Beispiel 2
S=NG
T=ABCDEFGHIJKLMN

anhängen
ABCDEFGHIJKLMNG


am ende der Schleife brauchst du nur prüfen ob der Treffer DEIN Treffer ist oder ein Echter Treffer.
So sparst du dir bei großen Texten auf jeden Fall ne Menge vergleiche.
Andreas
Monads? Wtf are Monads?
  Mit Zitat antworten Zitat
Themen-Optionen Thema durchsuchen
Thema durchsuchen:

Erweiterte Suche
Ansicht

Forumregeln

Es ist dir nicht erlaubt, neue Themen zu verfassen.
Es ist dir nicht erlaubt, auf Beiträge zu antworten.
Es ist dir nicht erlaubt, Anhänge hochzuladen.
Es ist dir nicht erlaubt, deine Beiträge zu bearbeiten.

BB-Code ist an.
Smileys sind an.
[IMG] Code ist an.
HTML-Code ist aus.
Trackbacks are an
Pingbacks are an
Refbacks are aus

Gehe zu:

Impressum · AGB · Datenschutz · Nach oben
Alle Zeitangaben in WEZ +1. Es ist jetzt 22:10 Uhr.
Powered by vBulletin® Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.
LinkBacks Enabled by vBSEO © 2011, Crawlability, Inc.
Delphi-PRAXiS (c) 2002 - 2023 by Daniel R. Wolf, 2024 by Thomas Breitkreuz