Ich habe Millionen Paare von Saiten gleicher Länge, die ich vergleichen und finden möchte die Position, wo es nicht stimmt.
Zum Beispiel wollen wir für jedes $str1 und $str2 eine fehlende Übereinstimmung finden
Position mit $str_source :
Gibt es einen schnellen Weg dazu? Derzeit habe ich die C-Style-Methode, die ich Schleife jede Position in beiden Strings mit der Funktion 'substr'. Aber dieser Ansatz ist schrecklich langsam.
%Vor%
Die Berechnung ist einfach, machen Sie es mit Inline :: C
(lies perldoc Inline :: C-Cookbook und perldoc Inline :: C zur Dokumentation):
Hier ist die Ausgabe dieses Skripts:
%Vor%Wenn Sie viele Daten in Perl schnell verarbeiten möchten, lesen Sie PDL ( Dokumentation ):
%Vor%(Gleiche Ausgabe wie das erste Skript.)
Anmerkungen: Ich habe PDL sehr gerne in der genomischen Datenverarbeitung verwendet. Zusammen mit dem Speicherzuordnungszugriff auf Daten, die auf der Platte gespeichert sind, können große Datenmengen schnell verarbeitet werden: Die gesamte Verarbeitung erfolgt in hochoptimierten C-Schleifen. Sie können auch einfach auf die gleichen Daten zugreifen, indem Sie Inline :: C auf alle fehlenden Funktionen in PDL .
Beachten Sie jedoch, dass die Erstellung eines PDL-Vektors ziemlich langsam ist (konstante Zeit, für große Datenstrukturen akzeptabel). Sie möchten also lieber ein großes PDL-Objekt mit all Ihren Eingabedaten auf einmal erstellen, als die einzelnen Datenelemente zu durchlaufen.
Diese sehen wie Gensequenzen aus. Wenn die Zeichenfolgen alle aus 8 Zeichen bestehen und die Domäne der möglichen Codes (A, C, G, T) lautet, könnten Sie die Daten vor der Verarbeitung irgendwie transformieren. Das würde Ihnen nur 65536 mögliche Zeichenfolgen geben, so dass Sie Ihre Implementierung spezialisieren können.
Sie schreiben z. B. eine Methode, die eine 8-stellige Zeichenfolge verwendet und sie einer Ganzzahl zuordnet. Memoize , damit die Operation schnell geht. Schreiben Sie als nächstes eine Vergleichsfunktion, die Ihnen bei zwei ganzzahligen Zahlen sagt, wie sie sich unterscheiden. Sie würden dies in einem geeigneten Schleifenkonstrukt mit einem numerischen Gleichheitstest wie unless ( $a != $b ) nennen, bevor Sie den Vergleich aufrufen - ein Kurzschluss für identische Codes, wenn Sie so wollen.
Es klingt, als ob dies ein leistungskritischer Teil Ihrer Anwendung sein könnte. In diesem Fall sollten Sie möglicherweise eine C-Erweiterungsmethode für den Vergleich schreiben.
Perl bietet den Erweiterungsmechanismus XS , der dies relativ einfach macht.
Hier ist ein Benchmark-Skript, um herauszufinden, ob die Unterschiede in der Geschwindigkeit der verschiedenen Ansätze. Bedenken Sie jedoch, dass es eine Verzögerung gibt, wenn ein Skript zum ersten Mal mit Inline :: C aufgerufen wird der C-Compiler wird aufgerufen usw. Führen Sie das Skript also einmal aus und dann benchmarken Sie es.
%Vor% Ergebnisse (mit VC ++ 9 unter Windows XP mit AS Perl 5.10.1) mit $copies = 1 :
Ergebnisse mit $copies = 100 :
Du machst zwei Aufrufe an substr für jeden Zeichenvergleich, was wahrscheinlich dich verlangsamt.
Einige Optimierungen, die ich machen würde
%Vor%Der schnellste Weg, die Strings zu vergleichen, um Unterschiede zu finden, wäre, XOR jedes Byte zusammen zu machen, dann auf null zu testen. Wenn ich das tun müsste, würde ich einfach ein Programm in C schreiben, um den Unterschied zu machen, anstatt eine C-Erweiterung für Perl zu schreiben, dann würde ich mein C-Programm als Teilprozess von Perl ausführen. Der genaue Algorithmus hängt von der Länge der Zeichenfolgen und der Datenmenge ab. Dies würde jedoch nicht mehr als 100 Zeilen von C erfordern. Wenn Sie die Geschwindigkeit maximieren möchten, könnte ein Programm, das XOR-Bytes von Strings mit fester Länge testet und auf Null testet, in Assemblersprache geschrieben werden.
Einige klassische Zeichenketten vergleichen Optimierungen:
optimaler Mismatch - Vergleich am Ende des Suchstrings beginnen. z.B. Suche nach ABC in ABDABEABF Wenn du am Anfang vergleichst, wirst du dich entlang des Musters ein Zeichen nach dem anderen bewegen. Wenn Sie vom Ende aus suchen, können Sie drei Zeichen überspringen
Schlechte Zeichenheuristik - Wählen Sie das am wenigsten häufig auftretende Zeichen und suchen Sie danach zuerst. z.B. Im Englischen ist ein 'z' Zeichen selten und gute Suchfunktionen suchen nach 'maze' und beginnen den Vergleich mit dem 3. Zeichen
Ich weiß nicht, wie effizient es ist, aber Sie könnten immer die zwei Zeichenfolgen, die Sie abgleichen, finden und den Index der ersten Nichtübereinstimmung finden.
%Vor% %Vor%Wenn Sie es durch B :: Concise laufen lassen, werden die CPU-teuren Operationen als einzelne Opcodes ausgeführt. Was bedeutet, dass diese Operationen in C ausgeführt werden.
%Vor% %Vor%Ich wollte sagen: "Schreib es auch in C".
Sobald Sie dort sind, können Sie Optimierung wie 4 Zeichen gleichzeitig (als 32-Bit-Ganzzahlen) verwenden.
Oder ändern Sie Ihre Repräsentation (4-Buchstaben, richtig?), um 2-Bit zu verwenden, um eine Basis (?) darzustellen, so dass Sie 16 Zeichen gleichzeitig vergleichen können.