Regex, Entfernen Sie doppelte Pfade aus der Zeichenfolge mit Trennzeichen
Ich versuche, doppelte Dateipfade aus einem Semikolon getrennten Strings mit einem regulären Ausdruck zu entfernen. Reihenfolge der letzten Pfade spielt keine Rolle.
Beispieleingabe:
%Vor%Gewünschte Ausgabe:
%Vor%Ich habe die folgende Regex, die funktioniert, ist aber sehr langsam, wenn die Eingabe-Strings sehr lang werden. Hinzu kommt, dass es über Tausende von Zeilen läuft und die Zeit ist sehr schlecht.
%Vor%Alle Tipps, wie Sie die Leistung verbessern können, werden sehr geschätzt!
8 Antworten
Oder die C # -Version:
%Vor%Ausgaben:
%Vor% Teilen Sie die Eingabe in ; , machen Sie sie zu HashSet<string>(..) , um die Duples loszuwerden, und verbinden Sie sich erneut mit ; .
Vorbehalt : Wenn Ihre Pfade ; als Teil des Verzeichnisnamens enthalten, bricht dies - Sie müssten für diesen Fall kreativer werden - aber das gleiche gilt für jede RegEx-Datei verwenden.
Das Entfernen von Duplikaten in Perl erfolgt normalerweise mit einem Hash. Siehe auch perlfaq4: Wie kann Ich entferne doppelte Elemente aus einer Liste oder einem Array?
%Vor% Ich habe das sort dort eingefügt, aber Sie können es entfernen, wenn Sie das nicht brauchen.
Obwohl Sie noch nicht angegeben haben, ob die Implementierung in C # oder Perl sein soll, sollte die gleiche Idee auch für C # gelten. ( Update: siehe Patrick Artners Antwort )
Beachten Sie, dass die Regex langsam ist, weil die Engine für jede Übereinstimmung von \b([^;]+) den gesamten Rest der Zeichenfolge für den Lookahead .*;; scannen muss, also ist es im Wesentlichen wie geschachtelte Schleifen.
Ich denke, das ist viel einfacher in Perl mit dem Perl-Hash-Idiom.
Sehen Sie sich dieses Beispiel an,
%Vor%Ausgabe:
%Vor%Jeder Schlüssel existiert nur einmal in einem Hash. Wenn Sie einem Hash denselben Schlüssel zuweisen, wird nur der zuletzt mit diesem Schlüssel verknüpfte Wert gespeichert. Dieses Verhalten hat Vorteile! Um zum Beispiel eindeutige Elemente einer Liste zu finden:
Wenn Sie undef mit einem Hash-Slice verwenden, werden die Werte des Hash auf undef gesetzt. Dieses Idiom ist der billigste Weg , um Set-Operationen mit einem Hash auszuführen.
Das obige stammt aus dem Buch Moderne Perlbücher Hier ist der Link, den Sie überprüfen können. Hash-Idiome
Das können wir in Ihrem Szenario ganz klar nutzen.
%Vor%Ausgabe:
%Vor%Ich glaube, das ist der schnellste Weg, um das zu erreichen, was Sie wollen. Wenn Leistung ein Problem ist.
Perl, die am meisten optimierte einzeilige RegEx-Version:
%Vor%Auf Ihrer eigenen Eingabezeichenfolge benötigt Ihre eigene Regex ~ 114000 Schritte, um alle Übereinstimmungen zu finden, aber mit dieser müssen Sie 567 Schritte ausführen.
Über 40000 Vorkommen in ~ 4 Sekunden gefunden:
RegEx Breakdown:
%Vor% In Perl benötigt man eine Zeile, um die Bibliothek zu verwenden List::Util , das ist Kern und hoch optimiert:
Wie funktioniert es? split erstellt eine Liste von Pfaden, die sich um das Zeichen ; aufteilen, uniq stellt sicher, dass es keine Wiederholungen gibt; join erstellt eine Reihe von Pfaden, die wieder mit ; getrennt werden.
Wenn der Fall der Pfade nicht wichtig ist, dann:
%Vor%Das vollständige Programm könnte sein:
%Vor%Um die Dinge interessant zu machen, lassen Sie uns diese Lösung gegen die vorgeschlagene Lösung, die einen temporären Hash verwendet, einplanen. Dies ist das Timing-Programm:
%Vor%Er erzeugt 1 Million zufällige Pfade, die ein Verhältnis von 5: 1 Duplikaten haben sollten (5 Duplikate jedes Pfades). Die Zeitvorgaben für den Server, auf dem ich dies getestet habe, sind:
%Vor% Dies macht die uniq -Bibliothek schneller als der temporäre Hash. Mit 100: 1 Duplikaten:
Bei 10000: 1 Duplikaten:
%Vor% Beide Algorithmen arbeiten weniger, je mehr Duplikate gefunden werden. uniq führt mit zunehmender Anzahl der Duplikate immer besser aus.
Fühlen Sie sich frei, mit den Zahlen des Zufallsgenerators zu spielen.
Da Windows-Pfade nicht zwischen Groß- und Kleinschreibung unterschieden werden, möchten Sie wahrscheinlich bis auf case
identische Elemente entfernen (Der nächste Schritt wäre, jedes Element durch File::Spec::canonpath zu schieben, um herauszufinden, ob die Pfade gleich, aber unterschiedlich ausgedrückt sind, und dann vielleicht Links zu berücksichtigen, aber dies ist nur von der Groß- und Kleinschreibung auszugehen)
Ich weiß nicht, ob Ihre Anfrage "einen regulären Ausdruck verwenden" ist eine Voraussetzung, aber es ist, wie Sie herausgefunden haben, ein sehr ineffizienter Weg, dies zu tun
Ich empfehle ein einfaches split für Semikolons und
List::UtilsBy
die fallunabhängige Eindeutigkeit zu tun