Hallo zusammen,
ich möchte im Rahmen einer Änderungsprüfung bei Bedarf, andere Kennzeichen wie Länge wurden vorher bereits geprüft, den Unterschied zwischen zwei Strings aufzeigen. Also in etwa:
int diffStarts =0;
while (str1[diffStarts] == str2[diffStarts] & diffStarts
Damit zeige ich den Text aus str1 an, ab dem ein Unterschied zu str2 besteht.
Das tuts auch, dauert aber recht lange. Geht das schneller/einfacher?
Vielen Dank schonmal!
mfg
Dirk.Pegasus
Hallo!
Zwei Anmerkungen zu Deinem Code:
Für genau dieses Problem (Bestimmung des größten gemeinsamen Präfix) fiele mir aus dem Stand nichts Schnelleres ein. Inwiefern wäre denn die Geschwindigkeit relevant? Du schreibst, der Unterschied müsse „bei Bedarf“ ermittelt werden, also nehme ich an, dass es nicht um tausende/Millionen von Strings geht, die Du auf einmal vergleichst.
Du könntest Dir natürlich auch einen Präfixbaum aufbauen, aber das wird auf jedem Fall aufwändiger als die jetzige ad-hoc-Präfixbestimmung und rentiert sich damit nur in bestimmten Fällen.
Wenn Du noch mehr zum Unterschied wissen willst als nur das gemeinsame Präfix und die strings nicht zu lang sind, würde ich Dir empfehlen, Dir mal die Levenshtein-Distanz zu Gemüte zu führen. Das ist ein Algorithmus, mit dem man feststellen kann, in wie vielen Schritten (Einfügen/Löschen einzelner Zeichen) String1 in String2 überführt werden kann.
Gruß,
Martin
[Bei dieser Antwort wurde das Vollzitat nachträglich automatisiert entfernt]
Hallo Martin,
vielen Dank für die Antwort.
Hallo!
Zwei Anmerkungen zu Deinem Code:
- ‚&‘ ist das binäre Und, in Deinem while bräuchtest Du
eigentlich && für das logische Und- Die Schleife fällt auf die Nase, wenn str2 kürzer als str1
ist.
Guter Hinweis mit &&/& und ||/| steh ich eh auf dem Kriegfuss!
Da die Anzahl der Zeichen schon vorab geprüft wird, hat’s noch keinen Fehler gegeben.
Du könntest Dir natürlich auch einen Präfixbaum aufbauen, aber
das wird auf jedem Fall aufwändiger als die jetzige
ad-hoc-Präfixbestimmung und rentiert sich damit nur in
bestimmten Fällen.
Da alle Texte „immer ganz anders“ sind, macht da wohl keinen Sinn. Im Moment hab ich so 3000 Zeilen mit je zwei Texten. Der Vergleich erfolgt immer innerhalb einer Zeile. Aber selbst bei 30 Treffern, die ich so analysieren will, dauert das schon „sichtbar“. Also ca. 35 sec für aktuell 450 Zeilen.
Wenn Du noch mehr zum Unterschied wissen willst als nur das
gemeinsame Präfix und die strings nicht zu lang sind, würde
ich Dir empfehlen, Dir mal die Levenshtein-Distanz zu Gemüte
zu führen. Das ist ein Algorithmus, mit dem man feststellen
kann, in wie vielen Schritten (Einfügen/Löschen einzelner
Zeichen) String1 in String2 überführt werden kann.
Es geht sich darum aufzuzeigen, dass Texte unterschiedlich sind. Da die Texte eigentlich XML sind prüfe ich vorab andere Kriterien (wie die Anzahl der Knoten). Ich benutze erst den String-Vergleich, wenn diese Methoden keinen Unterschied gezeigt haben. Wie „groß“ dieser ist, ist dann eigentlich egal.
Ich werd das dann mal erstmal so lassen. Ich hatte halt gehoft, dass es sowas wie or(str1, str2) gibt. Ein logischer Vergleich je Char würde ja false liefern, wenn das Char unterschiedlich ist.
mfg
Dirk.Pegasus
Hi nochmal!
Guter Hinweis mit &&/& und ||/| steh ich eh auf dem Kriegfuss!
Da die Anzahl der Zeichen schon vorab geprüft wird, hat’s noch
keinen Fehler gegeben.
Im Zweifel würde ich immer && bzw. || nehmen - falls doch mal binäre Operationen benötigt werden, meckert der Compiler i.d.R.
Sinn. Im Moment hab ich so 3000 Zeilen mit je zwei Texten. Der
Vergleich erfolgt immer innerhalb einer Zeile. Aber selbst bei
30 Treffern, die ich so analysieren will, dauert das schon
„sichtbar“. Also ca. 35 sec für aktuell 450 Zeilen.
Das muss dann aber an etwas anderem liegen als der Präfixbestimmung.
Ich hab’ mal spaßeshalber ein Testprogramm geschrieben, das 500000 zufällige Strings und 500000 gleiche Strings mit Länge
Hallo Martin,
Das muss dann aber an etwas anderem liegen als der
Präfixbestimmung.
Ich hab’ mal spaßeshalber ein Testprogramm geschrieben, das
500000 zufällige Strings und 500000 gleiche Strings mit Länge
Hallo!
Noch eine Frage zu && im Vergleich zu &. Nach dem was ich
gelesen habe, ist der Unterschied nur, ob das nächste Argument
auch ausgewertet werden soll.Also (aus MS Hilfe):
Die Operation
x && y
entspricht der Operation
x & y
mit der Ausnahme, dass y nicht ausgewertet wird, wenn x false
ist (weil das Ergebnis der AND-Operation unabhängig vom Wert
von y false lautet). Dies wird als „Kurzschlussauswertung“
bezeichnet.Ist es das, was du mit binär und logisch meinst?
Im Wesentlichen, ja.
& und | führen binäre Operationen auf (Binär-)Zahlen aus. Bsp: Untere 8 bit bestimmen:
int number = ...
int lowerBits = number & 0x000F;
&& und || verknüpfen boole’sche Werte mit logischen Operationen. Bsp: Praktisch alle Vergleiche mit mehr als einer Eingangsgröße:
if (wert1 \> 0 && wert1
Gruß,
Martin
Hallo Martin,
Im Wesentlichen, ja.
& und | führen binäre Operationen auf (Binär-)Zahlen aus. Bsp:
Untere 8 bit bestimmen:int number = …
int lowerBits = number & 0x000F;&& und || verknüpfen boole’sche Werte mit logischen
Operationen. Bsp: Praktisch alle Vergleiche mit mehr als einer
Eingangsgröße:if (wert1 > 0 && wert1
Aber auch das ist doch zulässig:
if (wert1 \> 0 & wert1
Oder etwa nicht?
mfg
Dirk.Pegasus
Hallo Martin,
Im Wesentlichen, ja.
& und | führen binäre Operationen auf (Binär-)Zahlen aus. Bsp:
Untere 8 bit bestimmen:int number = …
int lowerBits = number & 0x000F;&& und || verknüpfen boole’sche Werte mit logischen
Operationen. Bsp: Praktisch alle Vergleiche mit mehr als einer
Eingangsgröße:if (wert1 > 0 && wert1
Aber auch das ist doch zulässig:
if (wert1 > 0 & wert1
Ja, schon, weil & auch für boole’sche Werte das gleiche Ergebnis liefert wie &&, aber bei & wird eben auch bei einem false auf der linken Seite weiter ausgewertet, was in geschätzt >90% der Fälle nicht notwendig oder sogar fehlerträchtig ist.
Nicht zuletzt darum habe ich mir angewöhnt, immer (wo geht natürlich) die doppelten Operatoren zu verwenden.
Oder etwa nicht?
mfg
Dirk.Pegasus