Ich habe zwei sehr große Saiten. Wie kann ich sie vergleichen, um festzustellen, ob sie identisch sind oder ob sich eine von der anderen unterscheidet? (Auf diese Weise kann ich die identischen Strings alleine lassen und die ändern, die sich geändert haben).Wie kann man am effizientesten prüfen, ob zwei Strings unterschiedlich sind?
Sie könnten Hashwerte vergleichen oder eine Wrapper-Klasse erstellen, die die fragliche Zeichenfolge und ein "geändert" -Flag enthält, das bei jeder Änderung der Zeichenfolge auf true gesetzt wird.
Der effizienteste Weg ist zu tun:
$string1 == $string2
Es macht einen bitweise Vergleich der Saiten, so sollte im schlimmsten FallO(n) wo n ist die Größe des kleineren String sein. Ich glaube nicht, dass du viel besser als das werden wirst (ohne die Strings zu verfolgen und wenn sie geändert wurden, aber so wie deine Frage formuliert ist, scheint es, dass du alles nur vergleichen willst).
Ich würde sogar annehmen, dass ich keine Bytes (nicht Bits!) Überhaupt vergleichen werde, wenn die Länge unterschiedlich ist. Nicht möglich in C mit 0-terminierten 'char'-Arrays, aber perfekt möglich in jeder anderen Sprache :) – delnan
@delnan: Es verwendet die [' memcmp() '] (http://www.cprogramming.com/fod/ memcmp.html) C-Funktion (Siehe 'zend_binary_strcmp' in [der Quelle] (http://svn.php.net/repository/php/php-src/branches/PHP_5_3/Zend/zend_operators.c)). – ircmaxell
Richtig, aber um Hashwerte zu vergleichen, müssen Sie jede Zeichenfolge vollständig durchlaufen, um den Hash zu generieren, und dann den Hashwert durchlaufen. Daher ist es bei BEST "O (m + n + 1)" und im schlimmsten Fall "O (m + n + c)" (wobei "m" die Länge einer Zeichenfolge ist, "n" die Länge der anderen und 'c' ist die Hash-Länge) ... Und das ist sogar das Ignorieren der Komplexität der Hash-Funktion ... Definitiv nicht der effizienteste Weg, es sei denn, Sie speichern bereits den Hash. – ircmaxell
Das ist, was ich meinte: Berechnen und speichern Sie den Hash, wenn eine Zeichenfolge geschrieben wird, nicht im Vergleich. – weltraumpirat