Schnelle Textvergleiche?
Matthias Jaekle
ich habe eine Array mit ca. 1000 Strings und einen Vektor mit ca.
150.000 gültigen Stringanfängen und zugehörigen Werten.
Um nun zu den 1000 String die zugehörigen Werte aus dem Vektor zu
bestimmen laufe ich 1000 mal den Vektor mit seinen 150.000 Elementen
Element für Element durch und vergleiche die Stringanfänge mit einem
java.util.regex.Pattern.matches.
Sehr sehr langsam :( Aber wie gehts schneller?
Besten Dank für Eure Hilfe!
Matthias Jaekle
Achim Peters
> ich habe eine Array mit ca. 1000 Strings und einen Vektor mit ca.
> 150.000 gültigen Stringanfängen und zugehörigen Werten.
>
> Um nun zu den 1000 String die zugehörigen Werte aus dem Vektor zu
> bestimmen laufe ich 1000 mal den Vektor mit seinen 150.000 Elementen
> Element für Element durch und vergleiche die Stringanfänge mit einem
> java.util.regex.Pattern.matches.
Sind die Stringanfänge denn reguläre Ausdrücke?
> Sehr sehr langsam :( Aber wie gehts schneller?
Wenn obige Frage mit "ja" beantwortet wird, fiele mir auf Anhieb nichts ein.
Falls "nein":
Mache Dir HashMaps in die jeweils Stringanfänge gleicher Länge kommen,
in der Hoffnung, dass da meistens mehr als ein Stringanfang drin ist,
und klappere die der Reihe nach für jeden der 1000 Strings mit
contains.(myStrings[i].substring(1,laengeDerStringAnfaengeInDieserHashMap)
ab - evtll. vorher schauen, ob der String überhaupt so lang ist, etc.
HTH
Bye
Achim
Jan Lange
Hi
schneller geht das durch effiziente Sortier und Search Alghorithmen.
Da ich jetzt nich weiß, wie genau deine beiden String Arrays aussehen,
weiß ich nich was ich das empfehlen würde.
Allerdinge würde ich hier schonmal behaupten das angesichts der Menge
an Daten, ein binary search verfahren sicherlich nich schlecht ist.
unteranderem: muss es ein regexp sein?? reicht nicht ein equals bzw
compare methode, oder eine andere reine string methode?
die sind 100mal fixer.
Tobias Vogele
Matthias Jaekle spoke:
> Hallo,
>
> ich habe eine Array mit ca. 1000 Strings und einen Vektor mit ca.
> 150.000 gültigen Stringanfängen und zugehörigen Werten.
>
> Um nun zu den 1000 String die zugehörigen Werte aus dem Vektor zu
> bestimmen laufe ich 1000 mal den Vektor mit seinen 150.000 Elementen
> Element für Element durch und vergleiche die Stringanfänge mit einem
> java.util.regex.Pattern.matches.
Sind die "Stringanfänge" in dem Vektor feste Strings? Dann brauchst Du schon
mal keine regulären Ausdrücke.
In dem Fall würde statt eines Vektors einen Trie verwenden
(http://en.wikipedia.org/wiki/Trie).
Grüße,
tobi
--
URL: http://www.wartmal.de Email: ne...@wartmal.de
Remo Hartwig
Tobias Vogele schrieb:
> Hallo,
>
> Matthias Jaekle spoke:
>
>
>>Hallo,
>>
>>ich habe eine Array mit ca. 1000 Strings und einen Vektor mit ca.
>>150.000 gültigen Stringanfängen und zugehörigen Werten.
>>
Verstehe ich nicht ganz. Sind die Elemente im Vector Strukturen oder
einfache Strings (und zugehoerige Werte)? Bei einfachen Strings reicht
Collections.sort(), bei Strukturen brauchst Du
Collections.sort(Comparator). Das gleiche Verfahren beim
Collections.binarySearch.
Vielleicht ist es ja sinnvoll, dass bei Dir synchronisiert werden muss,
wenn nicht, nimm statt Vector lieber ArrayList, das ist bedeutend schneller.
> Sind die "Stringanfänge" in dem Vektor feste Strings? Dann brauchst Du schon
> mal keine regulären Ausdrücke.
> In dem Fall würde statt eines Vektors einen Trie verwenden
> (http://en.wikipedia.org/wiki/Trie).
>
Erzeugt das nicht etwas viel Overhead (Speicher)?
Weiterhin wuerde in jedem Knoten wieder eine Binaersuche erfolgen, beim
Durchschleifen durch die Knoten bis zum Ziel sind das vielleicht mehr
Abfragen als eine direkte Binaersuche in einer Liste von 150 000
Elementen (log n == 5 bis 6 Abfragen zum Ziel, wenn ich mich nicht
gerade verrechnet habe, und das sollte doch bei geringstem
Schreibaufwand schnell genug sein).
Gruesse
Remo
Remo Hartwig
> gerade verrechnet habe,
Hat er! :)
17 - 18 natuerlich
Johann Burkard
> Um nun zu den 1000 String die zugehörigen Werte aus dem Vektor zu
> bestimmen laufe ich 1000 mal den Vektor mit seinen 150.000 Elementen
> Element für Element durch und vergleiche die Stringanfänge mit einem
> java.util.regex.Pattern.matches.
>
> Sehr sehr langsam :( Aber wie gehts schneller?
Du kannst mal auf
http://johannburkard.de/software/stringsearch/apidoc/com/eaio/stringsearch/ShiftOrClasses.html
kucken, ob dir die Möglichkeiten der Implementierung reichen. Shift-Or
ist in meiner Implementierung in den IBM-VMs ziemlich flott, in den
Sun-VMs etwas lahmer.
Johann
--
Möchtest du eine vernünftige Antwort, frage mich, den Guten, oder Sabine
Schulz oder dau° und viele andere, die auch zu den Guten gehören!
("Marco Desloovere" in <478qnuscl2fp3daa2...@4ax.com>)
Tobias Vogele
Remo Hartwig spoke:
>> In dem Fall würde statt eines Vektors einen Trie verwenden
>> (http://en.wikipedia.org/wiki/Trie).
>>
>
> Erzeugt das nicht etwas viel Overhead (Speicher)?
Nein, eher weniger, weil bei mehreren Strings mit einem gleichen Präfix
das Präfix nur einmal gespeichert wird. Je mehr und je längere solche
Präfixe es gibt, desto größer ist die Speicherersparnis. Wenn es solche
Präfixe kaum gibt, könnte es schon sein, daß man ein klein wenig mehr
Overhead hat, aber das dürfte nicht viel ausmachen.
> Weiterhin wuerde in jedem Knoten wieder eine Binaersuche erfolgen,
> beim Durchschleifen durch die Knoten bis zum Ziel sind das vielleicht
> mehr Abfragen als eine direkte Binaersuche in einer Liste von 150 000
> Elementen (log n == 5 bis 6 Abfragen zum Ziel, wenn ich mich nicht
> gerade verrechnet habe, und das sollte doch bei geringstem
> Schreibaufwand schnell genug sein).
Das kommt immer auf die Daten darauf an. :-)
Tries haben die Eigenschaft, das der String, den man sucht, nur einmal
durchlaufen wird, während er in einer sortierten Liste bei jedem
Vergleich durchlaufen werden muß. Die Komplexität wächst also mit der
Länge des gesuchten Strings linear. Bei langen Strings macht das was
aus, bei kurzen nicht so sehr.
Remo Hartwig
>
>
> Nein, eher weniger, weil bei mehreren Strings mit einem gleichen Präfix
> das Präfix nur einmal gespeichert wird. Je mehr und je längere solche
> Präfixe es gibt, desto größer ist die Speicherersparnis. Wenn es solche
> Präfixe kaum gibt, könnte es schon sein, daß man ein klein wenig mehr
> Overhead hat, aber das dürfte nicht viel ausmachen.
>
Verstehe.
Die Referenz mit 40 Bytes schlaegt allerdings bei 150 000 mit n
zusaetzlichen Referenzen auch zu Buche.
>
> Das kommt immer auf die Daten darauf an. :-)
> Tries haben die Eigenschaft, das der String, den man sucht, nur einmal
> durchlaufen wird, während er in einer sortierten Liste bei jedem
> Vergleich durchlaufen werden muß. Die Komplexität wächst also mit der
> Länge des gesuchten Strings linear. Bei langen Strings macht das was
> aus, bei kurzen nicht so sehr.
>
Auch akzeptiert. Die Frage ergibt sich nun, ob dann ein concat oder
sogar ein + schneller ist, als ein compareTo oder sogar ein ==. (alles
jetzt erwaehnte auf der Basis von Pfennigfuchserei(manchmal sinnvoll,
manchmal nicht) :) )
> Grüße,
>
> tobi
>
Gruesse
Remo
Tobias Vogele
Remo Hartwig spoke:
> Verstehe.
> Die Referenz mit 40 Bytes schlaegt allerdings bei 150 000 mit n
> zusaetzlichen Referenzen auch zu Buche.
Das soll vermutlich 4 Bytes heißen, oder? Ja, stimmt.
Java hat hier noch ein weiteres Problem. Da man in einem Trie keine
String-Objekte mehr speichert, sondern die einzelnen Zeichen, könnte
man sich evtl. auf einen kleineren Zeichensatz beschränken und jedes
Zeichen statt in einem char (= 2 Bytes) in nur ein byte speichern und
damit 1 Byte pro Zeichen sparen. Da aber die meisten VMs glaub ich für
byte, char, short und int immer 4 Bytes verbrauchen, braucht man hier
nochmal mehr Speicher.
> Auch akzeptiert. Die Frage ergibt sich nun, ob dann ein concat oder
> sogar ein + schneller ist, als ein compareTo oder sogar ein ==. (alles
> jetzt erwaehnte auf der Basis von Pfennigfuchserei(manchmal sinnvoll,
> manchmal nicht) :) )
Warum concat? Da werden ja nie String konkateniert. Es wird nur auf
einzelne Zeichen des Strings zugegriffen und dieses Zeichen mit einem
anderen Zeichen (dem Baumknoten) verglichen.
Und bei einer sortierten Liste reicht ja meist ein == nicht, weil man
nicht nur die Ungleichheit wissen muß, sondern auch, ob's kleiner oder
größer ist. Deshalb braucht man schon compareTo.
Marco Lange
Hier könnte Dir ein Suffixbaum helfen. Du ordnest die Stringanfänge
(Präfixe) in einem Baum. Dabei ist ein Wort w genau dann Vater eines
Wortes w', wenn
w' = wa
ist, also w und ein beliebiger Buchstabe a angehangen. Die Kinder eines
einzigen Knoten sortierst Du noch nach diesem angehandenen Buchstaben,
so dass Du da auch noch eine binäre Suche machen kannst.
Sagen wir, Du hast als Liste mit Präfixen folgende:
gesund, viel, heute, heiter
dann beginnt Dein Baum mit dem leeren Wort, darunter kommen die Kinder
"g", "v" und "h"
(bitte nur mit Festbreitenschrit ansehen!)
<leer>
/ | \
g v h
| | |
e i e
| | / \
s e i u
| | | |
u l t t
| | |
n e e
| |
d r
Nun musst Du noch in jedem Knoten ein Flag speichern, ob Du an dieser
Stelle das Wort akzeptieren willst, ansonsten könntest Du nicht z.B.
sowohl heiter und heiterkeit akzeptieren (jetzt mal case insensitive).
Du musst jetzt beim Stringvergleich nur immer diesen Baum entlang laufen
solange es geht und überprüfen ob Du an einem Flag vorbeigekommen bist,
dass Dir andeutet, ob Du akzeptieren kannst. Ist das der falls,
akzeptierst Du das Wort, ansonsten nicht.
Den Baum muss man dabei nur einmal aufbauen, und das geht auch recht
effizient (O(Anzahl der Präfixe * max. Länge eines Präfix)), dies
Vergleiche laufen danach jeweils in O(Länge des Wortes) ab.
Viele Grüße,
Marco
Stefan Matthias Aust
> damit 1 Byte pro Zeichen sparen. Da aber die meisten VMs glaub ich für
> byte, char, short und int immer 4 Bytes verbrauchen, braucht man hier
> nochmal mehr Speicher.
Ohne das davor gelesen zu haben: Wenn man nur A-Z und ein paar
Sonderzeichen hat und 32 verschiedene Zeichen reichen, kann man in einem
int 5 Zeichen speichern. Man muss es nur geeignet kodieren. Nun kann
man sich einen String aus int[] bauen, wo etwa die obersten 8 bit des
ersten ints die Länge (0..255) angeben, schon 4 zeichen in diesen int
passen und ansonsten 5 in allen weiteren. Das gibt natürlich
verschnitt, vielleicht ist ein short noch besser als repräsentation.
Oder man hantiert mit byte[] herum, wo man die 6-bit-Zeichen dicht an
dicht packt. Nachteil hier, vergleiche gehen nicht so gut. Bei "int"
vergleicht man ja immer bis zu 5 Zeichen auf einmal. Taugt aber nur für
Gleichheitstests, nicht so sehr für größer/kleiner.
Ansonsten, ja man sollte damit rechnen, das einzelne byte, char, short
und int jeweils mindestens 4 Byte brauchen. Auf 64-Bit-Prozessoren
könnte es sogar 8 Byte sein.
bye
--
Stefan Matthias Aust // "A new beginning always starts at the end" -WT
Remo Hartwig
Tobias Vogele schrieb:
> Hallo,
>
> Remo Hartwig spoke:
>
>
>>Verstehe.
>>Die Referenz mit 40 Bytes schlaegt allerdings bei 150 000 mit n
>>zusaetzlichen Referenzen auch zu Buche.
>
>
> Das soll vermutlich 4 Bytes heißen, oder?
Gehen wir vom java.lang.String aus, nein.
Das spuckt der Profiler:
String {
int hashcode == 4 byte
int count == 4 byte
int offset == 4 byte
char[] == referenz == 12 byte
char[] selbst ist laut Profiler grundsaetzlich mit 16 byte
initialisiert,
egal ob "", "1", "12", "123", "1234" wird mit "12345" aber
entsprechend groesser
}
Dann stelle ich fest, dass ja zusaetzlich noch 12 byte fuer die Referenz
auf String hinzukommen.
Macht also 52 byte.
> Java hat hier noch ein weiteres Problem. Da man in einem Trie keine
> String-Objekte mehr speichert, sondern die einzelnen Zeichen, könnte
> man sich evtl. auf einen kleineren Zeichensatz beschränken und jedes
> Zeichen statt in einem char (= 2 Bytes) in nur ein byte speichern und
> damit 1 Byte pro Zeichen sparen. Da aber die meisten VMs glaub ich für
> byte, char, short und int immer 4 Bytes verbrauchen, braucht man hier
> nochmal mehr Speicher.
>
Will ich jetzt nichts falsches sagen, ich glaube aber, sie verbrauchen
die richtige Anzahl bytes, casten allerdings zwischenzeitlich mit int,
da die auf den Datentyp ausgefuehrten Operationen die des int
entsprechen und int bereits optimiert ist.
Es dauert ebend vergleichsweise lange zwei short's zu addieren, als
dieses mit zwei int's zu tun, belegt letztendlich aber weniger Speicher.
Letztendlich werden zB bei short die vorderen 2 Byte des int angefuegt
und nach der Operation einfach wieder abgeschnitten. Das Ergebnis des
short sind dann die letzten 2 byte des int.
>
>>Auch akzeptiert. Die Frage ergibt sich nun, ob dann ein concat oder
>>sogar ein + schneller ist, als ein compareTo oder sogar ein ==. (alles
>>jetzt erwaehnte auf der Basis von Pfennigfuchserei(manchmal sinnvoll,
>>manchmal nicht) :) )
>
>
> Warum concat? Da werden ja nie String konkateniert. Es wird nur auf
> einzelne Zeichen des Strings zugegriffen und dieses Zeichen mit einem
> anderen Zeichen (dem Baumknoten) verglichen.
> Und bei einer sortierten Liste reicht ja meist ein == nicht, weil man
> nicht nur die Ungleichheit wissen muß, sondern auch, ob's kleiner oder
> größer ist. Deshalb braucht man schon compareTo.
>
Verstehe, also (vorausgesetzt String wird verwendet) substring (der
Eingehende) vs. compareTo, da aber im Trie, wie oben erwaehnt, char[]
gespeichert wird, substring in char[] casten und Zeichenweise
vergleichen-->das koennte durchaus schneller sein ;)
> Grüße,
>
> tobi
Gruesse
Remo
Remo Hartwig
> und int jeweils mindestens 4 Byte brauchen. Auf 64-Bit-Prozessoren
> könnte es sogar 8 Byte sein.
>
>
> bye
Gruesse Remo
Stefan Matthias Aust
> Das spuckt der Profiler:
> String {
> int hashcode == 4 byte
> int count == 4 byte
> int offset == 4 byte
> char[] == referenz == 12 byte
> char[] selbst ist laut Profiler grundsaetzlich mit 16 byte initialisiert,
> egal ob "", "1", "12", "123", "1234" wird mit "12345" aber
> entsprechend groesser
> }
Alles Glaubensfrage. Das da oben glaube ich nicht. Vorweg - die
genauen Größen sind Implementationsabhängig je nach VM. Man kann nur
eine Abschätzung nach unten machen und dann gut raten. Ich nehme eine
32-Bit-Architektur an.
Normale Objekte, auf die nicht synchronisiert werden, haben
wahrscheinlich einen 8-Byte Header. Wird synchronisiert, kommen nochmal
4 Byte für die Referenz auf den Monitor hinzu. Auf Strings wird
normalerweise nicht synchronisiert. Jeder int und jede Referenz braucht
4 Bytes. Die 12 bei char[] scheint schon den Header des char[]-Objekts
zu berücksichtigen. Dieser Header ist meines Wissens aber mindestens 12
(bzw. 16 bei synchronized) Bytes groß, denn er muss die Anzahl der
Elemente noch enthalten. Die Chars selbst haben 2 Bytes.
Macht dann 8 + 16 + 12 + 2 für einen String mit einem Zeichen. Laut
Quelltext wird das char[] immer auf die korrekte Länge gebracht.
Nun kann es sein, dass im Heap niemals Objekte stehen, deren absolute
Größe nicht durch 16 teilbar ist. Dann könnte die Größe des
String-Objekts auf 32 und die des char[]-Objekts auf 16 aufgerundet werden.
Es könnte auch sein, dass das Array-Objekt nochmal eine Referenz auf die
eigentlichen Daten hält, damit diese bei einer GC nicht mitkopiert
werden müssen sondern in einem eines vorhandenen Heap länger unangefasst
stehen. Schlecht für die Lokalität, aber gut für den GC. Lisp würde
etwa einen Heap die die allgegenwärtigen (immer gleich großen)
CONS-Zellen und einen für die Symbole haben. In diesem Fall wäre das
Array-Objekt nochmal 4 Byte größer, dafür könnten die 2 Byte ungepadded
abgelegt werden. Vielleicht wird auch die Länge an dieser Stelle
abgelegt, dadurch würde das Objekt wieder auf 12 bzw. 16 bei
synchronized schrumpfen und unter der Annahme, der Heap wird in
16-Byte-Segmente unterteilt, effizienter genutzt.
Wir langen jedenfalls bei einer Größe von ca. 50 Bytes. Für 1 Zeichen :)
Klasse, was? Für längere Strings ist der Overhead natürlich nicht mehr
so groß. Trotzdem ist Java's implementierung alles andere als
speichereffizient. Dafür ist sie aber dann auch recht schnell.
Man hätte sich ja z.B. überlegen können verschiedene String-Unterklassen
zu haben, eine für kurze ISO-8859-1 oder ASCII-Strings, eine für längere
Unicode-Strings, UTF-8 encoded. Würde (jedenfalls in unseren breiten)
einiges Sparen. VisualWorks-Smalltalk macht das so. Und es wäre
einfacher, was jetzt zu einem riesen Problem wird - die chars reichen
nämlich auch nicht mehr für ein Unicode-4-Zeichen und man muss sich
jetzt für Java 1.5 eine UTF-16-Kodierung in den Strings überlegen.
Dumm nur, dass String final ist und man sich keine eigenen Strings bauen
kann, die kompatibel zum restlichen System sind. Dumme entscheidung in
Java 1.0, da kein String-INterface zu machen...
Remo Hartwig
Stefan Matthias Aust schrieb:
[...]
Wieder einmal bestens dargelegt. ;)
Remo
Tobias Vogele
Remo Hartwig spoke:
> Gehen wir vom java.lang.String aus, nein.
>
> Das spuckt der Profiler:
> String {
> int hashcode == 4 byte
> int count == 4 byte
> int offset == 4 byte
> char[] == referenz == 12 byte
> char[] selbst ist laut Profiler grundsaetzlich mit 16 byte
> initialisiert,
> egal ob "", "1", "12", "123", "1234" wird mit "12345" aber
> entsprechend groesser
> }
> Dann stelle ich fest, dass ja zusaetzlich noch 12 byte fuer die Referenz
> auf String hinzukommen.
> Macht also 52 byte.
Wie kommst Du eigentlich auf 12 Byte für eine Referenz? Ich würde für den
Pointer selbst 4 Byte annehmen, aber da das Objekt selbst hat noch einen
Overhead von 8 bis 12 Byte hat, kann das schon hinkommen, wenn man nur eine
Referenz auf das Objekt (was hier wohl der Fall ist).
Was Du aber übersiehst, ist, daß in dem Trie ja gar keine Strings
gespeichert sind, sondern jeder Knoten hat nur ein Zeichen als Schlüssel,
den man in einem char speichern kann (also 2 oder 4 byte, je nach
Implementierung in der VM).
Allerdings muß man in einem Trie ja zusätzlich die Kind-Knoten speichern,
z.B. in einem eigenem Array. Damit hat man ein Array-Objekt und eine
Referenz darauf pro Knoten mehr.
Das spart man sich bei einer Liste, die die Daten in einem großen Array
hält.
>> Da aber die meisten VMs glaub ich für
>> byte, char, short und int immer 4 Bytes verbrauchen, braucht man hier
>> nochmal mehr Speicher.
>>
>
> Will ich jetzt nichts falsches sagen, ich glaube aber, sie verbrauchen
> die richtige Anzahl bytes, casten allerdings zwischenzeitlich mit int,
> da die auf den Datentyp ausgefuehrten Operationen die des int
> entsprechen und int bereits optimiert ist.
Ich habs irgendwo mal anders gelesen, aber ich weiß nicht mehr, wo, deshalb
kann ich auch keine Quelle angeben. Einigen wir uns auf unentschieden? :-)
> Verstehe, also (vorausgesetzt String wird verwendet) substring (der
> Eingehende) vs. compareTo, da aber im Trie, wie oben erwaehnt, char[]
> gespeichert wird, substring in char[] casten und Zeichenweise
> vergleichen-->das koennte durchaus schneller sein ;)
Ich bin mir nicht sicher, ob wir aneinander vorbei reden. Jedenfalls versteh
ich nicht genau, was Du sagen willst.
In einem Trie hat ja jeder Knoten einen char als Schlüssel, evtl. einen Wert
und ein Array von Kind-Knoten. Wenn man nun nach einem String sucht und an
der Wurzel steht, holt sich man von dem String das erste char mit charAt(0)
und sucht in den Kind-Knoten, ob es einen Knoten gibt mit diesem char als
Schlüssel. Das geht mit binärer Suche, wobei aber immer nur chars
verglichen werden. Wenn man einen gefunden hat, gehts weiter, diesmal aber
mit dem zweiten char des Suchstrings.
Man braucht also kein substring, sondern für jedes Zeichen einmal charAt()
und führt damit dann eine binäre Suche durch.
Bei einer sortierten Liste hat man aber eine große binäre Suche, wobei jeder
Vergleich mit compareTo erfolgt. Und bei jedem compareTo geht man die
Zeichen mit charAt() durch und vergleicht sie in den zu vergleichenden
Strings (bis man zu einem Unterschied kommt).
Deshalb ist bei gemeinsamen, langen Präfixen der Trie besonders gut.
Achim Peters
> Wenn man nur A-Z und ein paar
> Sonderzeichen hat und 32 verschiedene Zeichen reichen, kann man in einem
> int 5 Zeichen speichern.
Ich komme auf 6 speicherbare Zeichen. Für 32 Zustände braucht man 5 Bit,
weil 2^5 == 32. Ein int hat 32 Bit und somit Platz für sechs dieser
Fünfbitter, weil 6*5=30.
Bye
Achim
Tobias Vogele
Marco Lange spoke:
> Hier könnte Dir ein Suffixbaum helfen. Du ordnest die Stringanfänge
> (Präfixe) in einem Baum. Dabei ist ein Wort w genau dann Vater eines
> Wortes w', wenn
>
> w' = wa
>
> ist, also w und ein beliebiger Buchstabe a angehangen.
Das ist gerade ein Trie. ;-)
Stefan Matthias Aust
Du hast natürlich recht. Ich kann nicht rechnen.
Remo Hartwig
> Ich habs irgendwo mal anders gelesen, aber ich weiß nicht mehr, wo,
deshalb
> kann ich auch keine Quelle angeben. Einigen wir uns auf
unentschieden? :-)
>
Angenommen. ;)
> Ich bin mir nicht sicher, ob wir aneinander vorbei reden. Jedenfalls versteh
> ich nicht genau, was Du sagen willst.
> In einem Trie hat ja jeder Knoten einen char als Schlüssel, evtl. einen Wert
> und ein Array von Kind-Knoten. Wenn man nun nach einem String sucht und an
> der Wurzel steht, holt sich man von dem String das erste char mit charAt(0)
> und sucht in den Kind-Knoten, ob es einen Knoten gibt mit diesem char als
> Schlüssel. Das geht mit binärer Suche, wobei aber immer nur chars
> verglichen werden. Wenn man einen gefunden hat, gehts weiter, diesmal aber
> mit dem zweiten char des Suchstrings.
> Man braucht also kein substring, sondern für jedes Zeichen einmal charAt()
> und führt damit dann eine binäre Suche durch.
>
> Bei einer sortierten Liste hat man aber eine große binäre Suche, wobei jeder
> Vergleich mit compareTo erfolgt. Und bei jedem compareTo geht man die
> Zeichen mit charAt() durch und vergleicht sie in den zu vergleichenden
> Strings (bis man zu einem Unterschied kommt).
>
> Deshalb ist bei gemeinsamen, langen Präfixen der Trie besonders gut.
>
> Grüße,
>
> tobi
>
Ich glaube, ich habe es jetzt verstanden (dank Deiner ausfuerlichen
Erklaerung und Marco Lange's Grafik ;) ). Zuvor hatte ich angenommen,
dass auch "hei" bei "heiter" als Knoten gelten koenne (also 3 chars).
Zusaetzlich kam mir charAt delizioeser Weise gar nicht in den Sinn,
weshalb ich auch oben gerade von Dir gnadenlos ausgebuht wurde (Ich
weise auch nicht die Schuld an die heute NICHT-aufrufbare Java-Doc :) ).
Ich bemerke also, Trie ist scheinbar bedeutend schneller. Das absolute
Laufzeitverhalten und den absoluten Speicherverbrauch beider Verfahren
moechte ich nun allerdings nicht mehr gegenueberstellen, wenn Du
verstehst, was ich meine ;)
Beste Gruesse
Remo
Tobias Vogele
Remo Hartwig spoke:
> Zusaetzlich kam mir charAt delizioeser Weise gar nicht in den Sinn,
> weshalb ich auch oben gerade von Dir gnadenlos ausgebuht wurde
Ups, das war nicht meine Absicht, sorry.
> Das absolute
> Laufzeitverhalten und den absoluten Speicherverbrauch beider Verfahren
> moechte ich nun allerdings nicht mehr gegenueberstellen, wenn Du
> verstehst, was ich meine ;)
Möchte ich auch nicht. :-)
Marco Lange
>>Hier könnte Dir ein Suffixbaum helfen. Du ordnest die Stringanfänge
>>(Präfixe) in einem Baum. Dabei ist ein Wort w genau dann Vater eines
>>Wortes w', wenn
>>
>> w' = wa
>>
>>ist, also w und ein beliebiger Buchstabe a angehangen.
>
>
> Das ist gerade ein Trie. ;-)
Ok, kannte den Begriff noch nicht :) Wieder was gelernt :)
Viele Grüße,
Marco