Gegeben ein zweidimensionales Array:
%Vor% Gibt es eine effiziente Möglichkeit, Läufe von 1 , die >= N in der Länge sind, zu ersetzen?
Zum Beispiel, wenn N=3
In Wirklichkeit ist das 2D-Array binär und ich möchte Läufe von 1 durch 0 ersetzen, aber aus Gründen der Klarheit habe ich sie im obigen Beispiel durch 2 ersetzt.
Runnable Beispiel: Ссылка
Der Code, den ich gerade benutze, sieht ein bisschen hacky aus und ich habe das Gefühl, dass es eine magische Art gibt, dies zu tun:
UPDATE: Ich bin mir bewusst, dass ich das Beispiel in eine Version geändert habe, die keine Eckfälle behandelt. Das war ein kleiner Implementierungsfehler (jetzt behoben). Ich war mehr interessiert, wenn es eine schnellere Art und Weise, es zu tun.
%Vor%Ausgabe:
%Vor%Verwenden eines Mustervergleichs durch Faltung:
%Vor% 3 mal langsamer als das ursprüngliche replace_runs , aber die Eckfälle erkennen (wie der vorgeschlagene string-basierte Ansatz).
Auf meinem Rechner:
replace_runs_org: 100000 Iterationen benötigten 12.792s
replace_runs_var: 100000 Iterationen benötigten 33.112s
Ich betrachte die Eingabe als ein eindimensionales Array, da es auf zwei Dimensionen verallgemeinert wird.
In binär können Sie überprüfen, ob zwei Elemente 1 sind, indem Sie & verwenden. In Numpy können Sie ein Array effizient durch Slicen "verschieben". Erstellen Sie also ein zweites Array mit einem 1 an allen Stellen, die Sie aufheben möchten (oder zu zwei ändern). Dann ^ oder + in das Original, je nachdem, ob Sie Nullen oder Zweier daraus machen wollen:
Beispiel:
%Vor% Erstens funktioniert Ihr Code nicht richtig ... Er ersetzt durch 2 s einen Cluster von nur zwei 1 s am Ende der zweiten Zeile. Das Folgende, was Ihr Text beschreibt:
Für Ihr Beispiel-Array ist es ~ 2x schneller, aber ich nehme an, dass es für größere Arrays viel schneller sein wird, solange n klein gehalten wird.
Vielleicht möchten Sie Ihren Code testen, er scheint nicht das zu tun, was Sie erwarten. Bitte führen Sie dieses Skript aus, testen Sie Ihren Code gegen meinen und überprüfen Sie die Ausgabe:
%Vor% Benchmarking macht keinen Sinn, solange der Code nicht festgelegt ist. Also werde ich meine, die Funktion replace_py() für das Benchmarking verwenden.
Die replace_py() -Implementierung, von der ich glaube, dass sie das tut, was Sie wollen, ist nicht pythonisch, sie hat viele Anti-Muster. Trotzdem scheint es richtig zu sein.
Timing:
%Vor%Ich denke nicht, dass Ihr Problem leicht umgeschrieben werden kann, um Numpy und Vektorisierung zu verwenden. Vielleicht kann ein Numpy-Guru das tun, aber ich fürchte, der Code wird entweder sehr dunkel oder langsam (oder beides) sein ). Um einen der Numpy-Entwickler zu zitieren:
[...] wenn es entweder eine Doktorarbeit in NumPy-ology erfordert, um den Vektor zu vektorisieren Lösung oder es führt zu viel Speicheraufwand, den Sie erreichen können Cython [...]
Also habe ich die replace_py() und die Funktionen, die sie aufruft, in Cython neu geschrieben, indem ich typisierte Speicheransichten :
Es war ein wenig massiert und der Code ist überladener als der entsprechende Python-Code oben. Aber es war nicht zu viel Arbeit und es war ziemlich einfach.
Timing:
%Vor%Das ist eine 1163-fache Beschleunigung!
Ich habe Hilfe zu Github erhalten und jetzt die Numba Version funktioniert auch; Ich habe gerade @autojit zum reinen Python-Code hinzugefügt , außer a[begin:end] = replace , siehe die Diskussion auf Github, wo ich diese Problemumgehung habe.
Timing (mit der üblichen Eingabe wie oben, Code weggelassen):
%Vor%Das ist eine 110-fache Beschleunigung im Vergleich zum reinen Python-Code für grundsätzlich kostenlose !!! Die Numba-Version ist immer noch 10x langsamer als Cython, wahrscheinlich wegen nicht die winzigen Funktionen eingezeichnet , aber ich finde es erstaunlich, diese Geschwindigkeit im Grunde umsonst zu bekommen, ohne unseren Python-Code durcheinander zu bringen!
>Die Faltungsmethode von toine ist auch ein guter Weg zu gehen. Basierend auf diesen Antworten könnten Sie groupy , um zu bekommen, was Sie wollen.
%Vor%Sie müssen es nur für jede Zeile in arr tun. Sie müssen es für Ihre Bedürfnisse optimieren, wenn Sie wirklich effizient sein möchten (z. B. Entfernen der Listenerstellung).
Mit dem Beispiel, das Paulus in der Antwort, die ich verlinkt habe, gegeben hat, können Sie etwas tun, wie folgt:
%Vor%Das ist nur Essen für. Mit dieser Methode ist es möglich, die gesamte Matrix in einem Durchgang auszuführen und das Array an Ort und Stelle zu modifizieren, was effizient sein sollte. Entschuldigung für den ziemlich rohen Zustand dieser Idee. Ich hoffe es gibt dir Einblicke. Ein guter Beschleunigungshinweis wäre, die for-Schleife zu entfernen.
Dies ist natürlich, wenn Sie aus Gründen der Klarheit zu opfern möchten. Meiner Meinung nach ist dies in Python selten der Fall, wo Sie schnell Ideen entwickeln möchten. Wenn Sie einen Algorithmus haben, der richtig bewiesen wurde, der schnell sein muss, schreiben Sie ihn in C (oder mit Cython) und verwenden Sie ihn in Ihrem Python-Programm (entweder mit ctypes oder CFFI).