Ich versuche, mit etwas R-Code zu experimentieren, den ich kürzlich gefunden habe und der Teile von Norvigs Rechtschreibprüfung in Python geschrieben; Insbesondere versuche ich, den richtigen Weg zu finden, um die Funktion edit2 in R zu implementieren:
In meinen Benchmarks scheint es jedoch so zu sein, dass die Generierung von Tausenden kleiner Strings in R mit paste0 (oder str_c von stringr oder stri_join von stringi) zu Code führt, der ungefähr 10x (oder ~ 100x, oder ~ 50x) langsamer als die von Norvig gezeigte Python-Implementierung. (Ja, die Funktionen stringr und stringi sind interessanterweise noch langsamer als mit paste0 .) Meine Fragen sind (wobei # 3 die Hauptfrage ist, die ich lösen möchte):
Mache ich das richtig (ist der Code "richtig")?
Wenn ja, ist das ein bekanntes Problem von R (extrem langsame Stringverkettung)?
Gibt es irgendetwas, was ich tun kann, um das signifikant schneller zu machen (mindestens eine oder mehrere Größenordnungen) ohne die ganze Funktion umzuschreiben Rcpp11 oder so ähnlich?
Hier ist mein R-Code, den ich für die Funktion edit2 entwickelt habe:
Wenn Sie mit der Profilerstellung dieses Codes beginnen, sehen Sie, dass replacements und insertions verschachtelte "lapplies" haben und 10x länger dauern als die deletions oder transpositions , weil sie weit mehr Schreibvarianten generieren.
Das dauert etwa 8 Sekunden auf meinem Core i5 MacBook Air, während der entsprechende Python-Benchmark (mit der entsprechenden edit2 -Funktion 20 mal ausgeführt) etwa 0,6 Sekunden dauert, dh etwa 10-15 mal schneller ist!
Ich habe versucht, expand.grid zu benutzen, um den inneren lapply loszuwerden, aber das hat den Code langsamer gemacht, nicht schneller. Und ich weiß, dass die Verwendung von lapply anstelle von sapply meinen Code etwas schneller macht, aber ich sehe keinen Sinn darin, die "falsche" Funktion (ich möchte einen Vektor zurück) für eine kleine Geschwindigkeitsüberhöhung zu verwenden. Aber vielleicht kann man das Ergebnis der Funktion edit.2 viel schneller in reinem R machen ?
Im ursprünglichen Titel wurde gefragt, ob paste0 in R 10x langsamer ist als die String-Verkettung in Python. Wenn dies der Fall ist, gibt es keine Hoffnung, einen Algorithmus zu schreiben, der stark von der String-Verkettung in R abhängig ist, die so schnell ist wie der entsprechende Python-Algorithmus.
Ich habe
%Vor%und
%Vor%Hier ist ein erster Vergleich
%Vor%(etwa 1s für alle Replikate) gegenüber
%Vor%Ich schätze, das ist der 10-fache Leistungsunterschied, den das ursprüngliche Poster beobachtet hat. R funktioniert jedoch besser bei Vektoren und der Algorithmus beinhaltet Vektoren von Wörtern sowieso, also könnte uns der Vergleich interessieren
%Vor%und
%Vor%Dies legt nahe, dass wir mit unserem R-Algorithmus auf dem richtigen Weg wären sollten mit 1/4 der Geschwindigkeit von Python laufen; das OP fand ein 10-faches Unterschied, so sieht es aus wie es Raum für Verbesserungen gibt.
Das OP verwendet die Iteration ( lapply und Freunde) anstelle der Vektorisierung. Wir können die Vektorversion mit verschiedenen Ansätzen zur Iteration mit dem folgenden vergleichen:
Skalierung der Daten zurück, Definition der "vektorisierten" Lösung als f0, und Vergleichen dieser Ansätze
%Vor% mit f4 ist zu langsam, um
Hieraus kann man den Rat von Dr. Tierney entnehmen, dass es einen Vorteil für die Vektorisierung dieser lapply -Aufrufe geben kann.
@fnl nahm den ursprünglichen Code an, indem er die Schleifen teilweise abwickelte. Es gibt Möglichkeiten für mehr davon, zum Beispiel
%Vor%könnte überarbeitet werden, um einen einzigen Aufruf auszuführen, der auf der Wiederverwendung von Argumenten beruht (kurze Vektoren werden recycelt, bis ihre Länge mit längeren Vektoren übereinstimmt)
%Vor%Die Werte sind in unterschiedlicher Reihenfolge, aber das ist für den Algorithmus nicht wichtig. Das Löschen von Indizes (Präfix mit -) ist möglicherweise speichereffizienter. Ähnliches
%Vor%Wir haben dann
%Vor%mit etwas Beschleunigung
%Vor% Das OP zeigt an, dass die ursprüngliche Version 10x langsamer war als
Python, und dass ihre ursprünglichen Änderungen zu einem 5x führten
beschleunigen. Wir bekommen eine weitere 1,2-fache Beschleunigung, also sind wir vielleicht bei der
erwartete Leistung des Algorithmus mit R's paste0. Ein nächster Schritt ist die Frage, ob alternative Algorithmen oder Implementierungen leistungsfähiger sind, insbesondere substr könnte vielversprechend sein.
Nach @ LukeTierneys Tipps in den Kommentaren der Kommentare zum Aufruf von paste0 und dem Zurückgeben von zwei Vektoren binary.splits habe ich die Funktionen so bearbeitet, dass sie korrekt vektorisiert werden. Ich habe die zusätzlichen Modifikationen hinzugefügt, wie sie von @MartinMorgan in seiner Antwort beschrieben wurden: Drop-Elemente mit einzelnen Suffixen anstelle von Auswahlbereichen (zB "[-1]" anstelle von "[2:n]" , etc .; NB: für mehrere Suffixe, wie verwendet in transpositions , ist dies tatsächlich langsamer) und insbesondere mit rep , um die paste0 -Aufrufe in replacements und insertions weiter zu vektorisieren.
Dies ergibt die bestmögliche Antwort (bis jetzt?), edit.2 in R zu implementieren (danke, Luke und Martin!). Mit anderen Worten, mit den wichtigsten Hinweisen von Luke und einigen späteren Verbesserungen von Martin endet die R-Implementierung ungefähr halb so schnell wie Python (aber siehe Martins letzte Kommentare in seiner Antwort unten). (Die Funktionen edit.1 , edit.2 und bigram.unsafe bleiben unverändert, wie oben gezeigt.)
Insgesamt und um diese Übung abzuschließen, haben Lukes und Martins Vorschläge die R-Implementierung ungefähr halb so schnell laufen lassen wie der Python-Code von Anfang an, was meinen ursprünglichen Code um etwa einen Faktor 6 verbesserte. Was mich noch mehr beunruhigt Das Ende sind jedoch zwei verschiedene Probleme: (1) Der R-Code scheint viel ausführlicher zu sein (LOC, könnte aber ein bisschen aufgefrischt werden) und (2) die Tatsache, dass sogar eine geringe Abweichung von "korrekter Vektorisierung" besteht R-Code funktioniert schrecklich, während in Python leichte Abweichungen von "korrektem Python" normalerweise keine so extreme Auswirkung haben. Nichtsdestotrotz werde ich mit meiner "coding efficient R" -Aktion weitermachen - danke an alle Beteiligten!