DseWiki: SoftwareDenkSport_1

Von SoftwareDenkSport 1

Gesucht war ein effizienter Algorithmus zur Suche der längsten, sich wiederholenden Zeichenkette in einem Text.

Der Algorithmus am Beispiel des kurzen Textes "Mississippi":

Im ersten Schritt wird eine Tabelle von Substrings erzeugt, die den möglichen Vergleichspositionen entsprechen:

"Mississippi" "ississippi" "ssissippi" "sissippi" "issippi" "ssippi" "sippi" "ippi" "ppi" "pi" "i"

Wichtig ist, dass es eine effiziente Repräsentation für diese Substrings gibt, denn diese Strings explizit aufzubauen wäre für reale Textgrößen (z. B. zwischen 100KB und 1MB) kaum möglich. In C genügt ein Pointer (z. B. 4 Byte) auf die entsprechende Position im Basisstring. In Java hat den Datentyp String an sich schon die Eigenschaft, auf einen gemeinsamen Characterarray verweisen zu können ohne eines Duplikates zu bedürfen (obwohl natürlich nicht so speicherschonend).

Im zweiten Schritt wird nun sortiert:

"Mississippi" "i" "ippi" "issippi" "ississippi" "sissippi" "sippi" "pi" "ppi" "ssippi" "ssissippi"

und im dritten bei einer linearen Suche geprüft, wieviele Zeichen jeweils mit dem Nachfolger identisch sind:

0 "Mississippi" 1 "i" 1 "ippi" 4 "issippi" 0 "ississippi" 2 "sissippi" 0 "sippi" 1 "pi" 0 "ppi" 3 "ssippi" - "ssissippi"

woraus sich zwanglos das Maximum (4 = "issi") ermitteln läßt.

Der Kern des Algorithmus in Java

public static int comlen(String s1,String s2) { int i; int checklen=Math.min(s1.length(),s2.length()); for(i=0; i<checklen; i++) { if(s1.charAt(i) != s2.charAt(i)) { return(i); } } return checklen; } private static String StringRetLongestRepeatingSubstring(String s) { int slen=s.length(); String [] list=new String[slen]; int i; int maxlen=0; int imax=-1; int curlen; for(i=0; i<slen; i++) { list[i]=s.substring(i,slen); } Arrays.sort(list); for (i=0; i<slen-1; i++) { curlen=comlen(list[i],list[i+1]); if(curlen>maxlen) { maxlen = curlen; imax=i; } } return list[imax].substring(0,maxlen); }

Das ist einer der vielen, traumhaft klaren Algorithmen, die Jon Bentley in ProgrammingPearls beschreibt.

Diskussion

Ein sehr schöner Algorithmus - nur leider nicht sehr modern präsentiert (sieht vom Stil her eher nach C aus... ;-).

Leider hast du Recht mit deiner Kritik. Der Originalalgorithmus ist in C und ich habe nur das Nötigste für die Umstellung getan. Werde versuchen, das in Zukunft besser zu machen. -- hl

: Macht gar nichts - schließlich sind ja noch andere da, die das machen können... ;-)
: Siehe RefactoringBeispiel

Der Profiler zeigt, dass der Flaschenhals dieses Algorithmus das Sortieren des Arrays (genauer: das Vergleichen der Strings) ist. Nun könnte man auf die Idee kommen (ich bin es zumindest), die Sortierung lieber mit Hilfe eines TreeSet? vorzunehmen; tatsächlich verdoppelt dies aber die Laufzeit.

Den Flaschenhals schneller machen, also den str-Vergleich.--hs

Entweder das - wobei ich mir den Code noch nicht angeschaut habe, es mich aber wundern würde, wenn da mit Java-Mittlen noch wesentlich mehr rauszuholen wäre. Oder die Anzahl der String-Vergleiche reduzieren, was ich mir von der Benutzung des TreeSets? (offenbar fälschlicherweise) erhofft hatte.

: Komplexere Datenstrukturen erfordern die Erzeugung vieler zusätzlicher Objekte (Tree). Das entspricht technisch malloc/free (dynamisches Speichermanagement) und ist Gift für die Performance. -- hl

SortierAlgorithmenDiskussion?

Arrays.sort scheint mit Hilfe von MergeSort zu sortieren (entnehme ich den Methodennamen aus dem Profiler-Log) - würde hier eine eigene QuickSort-Implementierung etwas bringen? -- ip

: MergeSort ist genauso wie QuickSort O(n*log_2(n)). Eine Implementierung von Quicksort könnte also nur durch effizientere Implementierung Vorteile bringen. Eine Annahme die ich aber zu bezweifeln wage, da Arrays.sort (zumindestens theoretisch) vom JRE-Produzenten als native Methode implementiert werden könnte und daher (rein dogmatisch) vorzuziehen ist.
MergeSort: O(n*log_2(n))
http://www.ads.tuwien.ac.at/teaching/LVA/AlgoDat1/SomSem01/unterlagen/Skript1Kapitel2.pdf (Seite 8)
QuickSort: O(n*log_2(n))
http://www.cs.queensu.ca/home/liuc/cisc842/wks4/wks4.html
HeapSort?: Einfügen: O(log_2(n)), n Elemente einfügen => O(n*log_2(n))
ShellSort?: O(n^1.2)

Alle anderen haben O(n^2) -- hs

Algorithmisch besser geht es nur mit extremen Methoden wie BucketSort, wo dann der Speicherverbrauch stark zunimmt. Wie gut die tatsächliche Implementation ist, und wie gut sie die H/W ausnutzt, ist wieder eine andere Frage.

: Wie mir scheint, ist Mergesort quasi ein Quicksort, wo das mittlere Element jeweils explizit für jede Instanz festgelegt wird - was man bei Quicksort -sowieso- auch machen kann.--hs

MergeSort ist der natürliche Algorithmus für "linked lists", während QuickSort und vor allem HeapSort? für Arrays im allgemeinen besser ist. Es sind i.A. auch typisierte Arrays vorzuziehen, da der Funktionsaufruf zum Vergleich -vor allem bei Java, nicht so bei Lisp- extrem aufwendig ist. Quicksort funktioniert überhaupt nicht gut für "linked lists", "swap" muß atomic sein. Mit Zahlen ist Quicksort sehr schnell, das swapping 2er Zahlen geht ohne zusätzlichen Speicher in 3 CPU Schritten. Für Strings empfiehlt sich der gute Sedgewick Algorithmus von seiner Webseite. --ReiniUrban.

...Arrays.sort scheint mit...

Zur Information: JavaArraysSortObjectSource

Nachtrag: Die Originallösung in C

Das ist die Originallösung. Ergänzt wurde nur die Zeitmessung für Win32.

/* Copyright (C) 1999 Lucent Technologies */ /* From 'Programming Pearls' by Jon Bentley */ #include <stdlib.h> #include <string.h> #include <stdio.h> #include <windows.h> int pstrcmp(char **p, char **q) { return strcmp(*p, *q); } int comlen(char *p, char *q) { int i = 0; while (*p && (*p++ == *q++)) { i++; } return i; } #define M 1 #define MAXN 1000000L char c[MAXN]; char *a[MAXN]; typedef int callee(const void *,const void *); int main() { int i, ch, n = 0, maxi, maxlen = -1; LARGE_INTEGER l1,l2,fr; QueryPerformanceCounter(&l1); while ((ch = getchar()) != EOF) { a[n] = &c[n]; c[n++] = ch; } c[n] = 0; printf("start\n"); qsort(a,n,sizeof(char *),(callee *)pstrcmp); printf("end\n"); for (i = 0; i < n-M; i++) { if (comlen(a[i], a[i+M]) > maxlen) { maxlen = comlen(a[i], a[i+M]); maxi = i; } } QueryPerformanceCounter(&l2); QueryPerformanceFrequency(&fr); printf("Sec=%.3lf\n",(l2.LowPart-l1.LowPart)/(double)fr.LowPart); printf("%.*s\n", maxlen, a[maxi]); return 0; }

Meine Zeitnehmung (750 MHz Athlon) für einen ca. 400 KB Textfile:

Sekunden

Java 1.2 5.99

Java 1.3 3.46

C 1.42

Auch der Platzbedarf dürfte in Java etwa um den Faktor 4 höher liegen.

Interessanterweise haben sowohl Borland C 5.0 als auch lcc für Win32 Probleme mit dem Sortieren der großen Pointertabelle und kehren aus dem qsort nicht zurück. Erst das von mir nicht besonders geliebte Visual C/C++ 5.0 von Microsoft liefert das richtige Resultat und den obigen Wert. --hl

: Man nehme meine qsort_(), damit passiert sowas nicht.--hs :-)

Da wäre es allerdings praktisch, wenn es eine Parameter-kompatible Version deines qsort_ gäbe. -- hl

: Gibts inzwischen.--hs

Es gibt da noch einen anderen Aspekt:
Ich hab den Algorithmus mit meiner qsort() realisiert, so daß auch binäre Quellen möglich sind.
Ich erhalte einwandfreie Endresultate.

Jedoch der Zeitbedarf sieht bei mir so aus:

Quelle Zeit (ca.) 13 KB 1 s 250 KB 3 min ! 350 KB 10 min ! 400 KB 19 min !

Und damit hatte ich im voraus sogar gerechnet, denn 400 KB bedeuten ja, daß aus Sicht von qsort() eine Datei mit einer Größe von 8 GigaByte? sortiert werden muß!
Es sind ja etwa 400000 Zeilen mit einer mittleren Länge von je 200000 Zeichen!

Wie kommst du da drauf? qsort sieht die Pointertabelle und cmp sieht im Mittel vermutlich nur maximal 2-3 gleiche Zeichen, bevor es das strcmp abbricht. ??? --hl

: abcde ist die Quelldatei. qsort sieht aber die virtuelle Datei abcde bcde cde de e.
: das ist Arithm. Reihe 5*(5+1)/2=15 Zeichen.
: Bei 400000 Quelle sieht qsort() durch das Substring-Herausstechen per Pointer tatsächlich eine zu sortierende Datei mit einer scheinbaren Größe von 8 GB!
: Meine Zeiten entsprechen dem sogar ... und liefern korrekte Resultate.--hs

Die Zeit hängt natürlich nicht nur von der Textlänge, sondern auch von den Testdaten ab. Versuchs mal mit meinen Testdaten:

http://www.wikiservice.at/upload/HelmutLeitner/sawyr10.txt . --hl

: Tja, Tom Sawyer braucht 19 Minuten!
: Resultat: "ouncel of the prosecution ..."
: Dann habe ich mit meiner zweiten qsort (siehe QuickSort) getestet, die den gleichen Algo hat: 1.39 Sekunden! (?!)
: Dann habe ich mit qsort aus meiner C-Lib getestet: 1.35 Sekunden! (PIII700, UnixWare)
: Ich hab auch mein Programm auf char* und strcmp() umgestellt -- keine Änderung!
: Meine Index-Variante mit gleichem Algo: 19 Min.! -- ich versteh es nicht!--hs

Resultat ist ok. 1.4 Sekunden auch. 19 Minuten sind ein Rätsel. Wie ist memcmp_F implementiert? Hast du einen Profiler zur Verfügung? --hl

: Rätsel gelöst, aber neues Rätsel da:
: Der Profiler hat mir letztlich mitgeteilt, daß meine strcmp_F() etwa 700-fach!
: langsamer ist als strcmp()!!!
: mit strcmp_F(siehe unten) 1140 Sekunden, mit strcmp() 1.61 Sekunden! - Das ist das neue Rätsel.
: 1.61 sek sind übrigens okay, wegen externem Swap(). --hs

static int strcmp_F(byte *d0, byte *s0)
{
   register byte *d=d0, *s=s0;
   if (d!=s)  {  // NEU
     for (;  1;  ++d,++s)  {
        if (*d!=*s)  return ( (int)*d - (int)*s );
        if (!*s)  break;
     }
   }
   return (0);
}

: Lösung ist da:
: Ich habe mal strcmp() mit strcmp_F() verglichen.
: Meine strcmp_F() ist bei kürzeren Strings 2.2-fach schneller!
: Dann habe ich qsort_() und strcmp_F() innerhalb im Detail
: untersucht:

   Datei    n-compare  equal-ptr  max-len  mittel-len
   12990     284226     22667      12990!   512!    (ohne Maßnahme)
   sawyr10   12317354   726929     61       2       (Maßn. 0)
   sawyr10   11745944   155519     61       2       (Maßn. 12)
   sawyr10   11590425   0          61       2       (Maßn. 124)

   Meine qsort_() braucht jetzt nur noch 1.28 Sekunden für sawyr10.txt

: Maßn.0: strcmp_F(): if (aptr!=bptr) { ...
: Maßn.12: l!=ve&&(*cmp)(l,ve) r!=ve&:: Maßn.124: dies auch beim 4. (*cmp) --hs

D. h. das Problem deines qsort (und vielleicht auch der von mir negativ getesteten Bprland qsort etc.) war, dass routinemäßig auch gleiche Elemente verglichen wurden, was bei diesem Algorithmus das strcmp in einzelnen Fällen über ca. 200.000 Zeichen laufen ließ? --jl

: Ja, hauptsächlich ein Problem von strcmp_F im Unterschied zu strcmp, und zwar im Zusammenhang damit, daß bei *dieser* Aufgabe die Strings extrem lang sind, so lang wie die ganze Datei groß ist.
: Bei normalen Stringlängen ist das kaum zu bemerken. Eine strcmp sollte also pauschal bei Pointergleichheit mit 0 retournieren, auch eine memcmp, wie das offenbar bei der UnixWare-Lib-strcmp auch der Fall ist.
: Dennoch hab ich die qsort_() ebenfalls davor geschützt, da immerhin der ganze (*cmp)-Aufruf unterlassen wird bei Index-Gleichheit.
: Es sind ja nur etwa 6% Anteil Index-Gleichheiten. Aber die immensen String-Längen haben das hier zeitlich deutlich bemerkbar werden lassen.
: Meine Algos hier sind bis auf diesen vorherigen Schwachpunkt doch recht gut. Die strcmp_F ist bei kurzen Strings bzw. frühem Abbruch sehr gut, obwohl code-klein.
: Wenn es gleiche Probleme woanders gibt, dann nur, wenn die dortige strcmp() trotz Pointer-Gleichheit die Strings abklappert.
: Interessantes Problem, wegen der Wirkung. Ich hab immer erst Ruhe, wenn sowas total geklärt ist. --hs

Ich mach's genauso. Oft entdeckt man solche Dinge in Code, der 10 Jahre oder länger in diversen Projekten gelaufen ist, und den man für optimal gehalten hat. Das ist auch der Grund, warum ich ein fanatischer Reuse-Anhänger bin, weil das die einzige Chance ist, langfristig wirklich erstklassigen Code zu liefern. -- hl

Diskussion

...Platzbedarf...Faktor 4...

: Woraus schließt Du das? (Wie man Geschwindigkeit misst, weiß ich, aber mit dem Speicherbedarf habe ich etwas Probleme...)

Ich habe mich seinerzeit auch um die Messung von JavaSpeicherBedarf? bemüht und daraus einige Faustformeln für mein System abgeleitet. In diesem Fall leite ich es aber direkt aus den benötigten Datenstrukturen ab.

In C benötigt die Pointertabelle 4 Byte je Substring.

In Java benötigt der String-Array für die Referenz zum Substring 4 Byte und zusätzlich für jedes String-Object mindestens 12, vermutlich aber 16 Byte:

public final //aus dem Java 1.2 Originalsource class String implements java.io.Serializable, Comparable { private char value[]; private int offset; private int count; ... }

Der value-Array wird ja gemeinsam benutzt, so dass Java wahrscheinlich eine der wenigen Sprachen außer C ist, die diesen Algorithmus überhaupt effizient umsetzen kann.

Welche Java-Version hast Du benutzt? Das kann unter Umständen erhebliche Geschwindigkeitsunterschiede ausmachen...

Es ist jedenfalls das Original Java 1.2 unter Windows 98 mit JIT (1.2.2 Classic VM build 1.2.2-W native threads, symcjit). Als IDE verwende ich Visual Cafe. Im Allgemeinen habe ich eine gute relative Performance zu C (bei Benchmarks im Mittel ca. 10-30% langsamer). -- hl

: Dann würde mich interessieren, wie die Performance unter 1.3 aussieht - wäre spannend zu sehen, ob die aktuelle HotSpot? Engine da noch was rausreißen kann. -- ip

Ich werde das 1.3 installieren und liefere dann den Wert (siehe oben). -- hl

: Herzlichen Dank! -- ip

Ist im Algorithmus evtl. eine Optimierungsmöglichkeit versteckt? Und zwar in Schritt 2: die Sortierung. Ein Stringvergleich tut doch auch nichts anderes, als das erste Paar ungleicher Zeichen in zwei Strings zu suchen. Schritt 3 wiederholt das nur noch einmal, zwar sehr gezielt, aber trotzdem ist das eine Wiederholung. --RichardVoß

KategorieAlgorithmus