Dieser Artikel stammt aus AtCoder Library, DSU. Und Fenwick Tree wird mit Cython von Python zur Verfügung gestellt. Ich habe nicht bestätigt, ob es etwas anderes als DSU und Fenwick Tree gibt, das auf die gleiche Weise verwendet werden kann, aber zum Beispiel Segtree. html) verwendet nicht typisierte Vorlagen, und Cython unterstützt (wahrscheinlich) keine nicht typisierten Vorlagen, daher denke ich, dass es schwierig ist.
Die AtCoder-Bibliothek ist in C ++ geschrieben und daher schneller als die Implementierung derselben in Python. Wie ich später erläutern werde, ist das Ergebnis im Vergleich zu PyPy jedoch nicht schnell.
Dieser Artikel berührt selten die Grammatik von Cython. Wenn Sie sich also für Cython in diesem Artikel interessieren, lesen Sie bitte auch andere Artikel. (Cython funktioniert auch, wenn Sie den Python-Code so schreiben, wie er ist.)
Es ist eine Sprache zum Erstellen von Python-Erweiterungsmodulen mit C / C ++ und kann C / C ++ - Klassen und -Funktionen aufrufen. Es ist eine Sprache, um genau das zu tun. (Ja wirklich?)
Cython und AtCoder Library sind erforderlich, daher werden wir sie installieren. Beachten Sie, dass Windows-Benutzer beim Kompilieren von Cython stolpern können. Wir empfehlen daher, wenn möglich Linux oder WSL zu verwenden.
terminal
$ pip3 install cython
Ich werde es bei tun. Mal sehen, ob Cython verwendet werden kann.
hello.pyx
print("Hello, World!")
Ein Programm, das Hello, World! Ausgibt. Beachten Sie, dass die Erweiterung ".pyx" lautet. Lassen Sie uns dies kompilieren und ausführen.
terminal
$ cythonize -i -3 hello.pyx
$ python3 -c "import hello"
Ich kompiliere mit dem Befehl cythonize in der ersten Zeile.
Die Option -i konvertiert es zuerst in C-Code und kompiliert es in ein Format, das von Python importiert werden kann ( .so unter Linux, .pyd unter Windows).
Die Option -3 wird verwendet, wenn Python 3-Serien ist.
Wie in der zweiten Zeile ist die Umgebungskonstruktion von Cython erfolgreich, wenn Sie den Code ausführen, der Hallo in Python und Hello, World! Is importiert. AtCoder Library Erstellen Sie einen Ordner "/ opt / ac-library /". (Es entspricht der Richterumgebung von AtCoder.) Kopieren Sie den Ordner "atcoder" in https://img.atcoder.jp/practice2/ac-library.zip direkt darunter.
DSU Aktivieren Sie zunächst DSU. Um die AtCoder-Bibliothek von Python verwenden zu können, benötigt Cython die folgenden zwei Schritte:
# distutils: language=c++
# distutils: include_dirs=/opt/ac-library
from libcpp cimport bool
from libcpp.vector cimport vector
cdef extern from "<atcoder/dsu>" namespace "atcoder":
cdef cppclass dsu:
dsu(int n) #Konstrukteur
int merge(int a, int b) #Seite(a, b)Hinzufügen
bool same(int a, int b) #Apex a,Ob b verkettet ist
int leader(int a) #Repräsentatives Element der Verbindungskomponente, zu der der Scheitelpunkt a gehört
int size(int a) #Die Größe der verketteten Komponente, zu der der Scheitelpunkt a gehört
vector[vector[int]] groups() #Liste von "Liste der Scheitelpunktnummern einer verketteten Komponente"
Dies ist der Code, der DSU in Cython verfügbar gemacht hat. Die erste Zeile gibt an, dass C ++ verwendet wird, und die zweite Zeile gibt den Speicherort der AtCoder-Bibliothek an. Die Zeilen 3 und 4 werden importiert, um C ++ Bool und Vektor zu nutzen. Ab der 5. Zeile die Methoden der Klasse "dsu" im Namespace "atcoder" von "atcoder / dsu.hpp" (ehrlich gesagt bin ich mir bei C ++ nicht sicher, daher bin ich mir nicht sicher, daher werde ich es intern implementieren und DSU-Dokumentation Bitte lesen Sie (: //atcoder.github.io/ac-library/production/document_ja/dsu.html) …….), Das in Cython verwendet wird. Jetzt haben Sie eine DSU in Cython
cdef dsu *u = new dsu(3)
u.merge(0, 1)
print(u.same(0, 1)) # True
print(u.same(0, 2)) # False
Es ist jetzt verfügbar als.
cdef class DSU:
cdef dsu *_thisptr
#Konstrukteur
def __cinit__(self, int n):
self._thisptr = new dsu(n)
#Seite(a, b)Hinzufügen
cpdef int merge(self, int a, int b):
return self._thisptr.merge(a, b)
#Apex a,Ob b verkettet ist
cpdef bool same(self, int a, int b):
return self._thisptr.same(a, b)
#Repräsentatives Element der Verbindungskomponente, zu der der Scheitelpunkt a gehört
cpdef int leader(self, int a):
return self._thisptr.leader(a)
#Die Größe der verketteten Komponente, zu der der Scheitelpunkt a gehört
cpdef int size(self, int a):
return self._thisptr.size(a)
#Liste von "Liste der Scheitelpunktnummern einer verketteten Komponente"
cpdef vector[vector[int]] groups(self):
return self._thisptr.groups()
In cpdef definierte Funktionen und Methoden können auch von Python aus aufgerufen werden. Durch das Erstellen einer DSU-Klasse und das interne Aufrufen der Methode der dsu-Klasse wird die Verwendung von DSU aus Python realisiert.
Dies vervollständigt den Cython-Code.
dsu.pyx
# distutils: language=c++
# distutils: include_dirs=/opt/ac-library
from libcpp cimport bool
from libcpp.vector cimport vector
cdef extern from "<atcoder/dsu>" namespace "atcoder":
cdef cppclass dsu:
dsu(int n)
int merge(int a, int b)
bool same(int a, int b)
int leader(int a)
int size(int a)
vector[vector[int]] groups()
cdef class DSU:
cdef dsu *_thisptr
def __cinit__(self, int n):
self._thisptr = new dsu(n)
cpdef int merge(self, int a, int b):
return self._thisptr.merge(a, b)
cpdef bool same(self, int a, int b):
return self._thisptr.same(a, b)
cpdef int leader(self, int a):
return self._thisptr.leader(a)
cpdef int size(self, int a):
return self._thisptr.size(a)
cpdef vector[vector[int]] groups(self):
return self._thisptr.groups()
Kompilieren wir es so, dass es in Python importiert werden kann.
terminal
$ cythonize -i -3 dsu.pyx
Schreiben wir den Code zum Lösen von DSU-Übung in Python.
ALPC-A.py
from dsu import DSU
n, q = map(int, input().split())
dsu = DSU(n)
res = []
for i in range(q):
t, u, v = map(int, input().split())
if t == 0:
dsu.merge(u, v)
else:
if dsu.same(u, v):
res.append(1)
else:
res.append(0)
print('\n'.join(map(str, res)))
Wenn Sie versuchen, ein Beispiel der Übung einzugeben und die richtige Ausgabe zu erhalten, ist dies vorerst ein Erfolg.
Ich möchte es tatsächlich bei DSU-Übungen einreichen und bestätigen, dass es sich um AC handelt, aber bei Coders Richterseite dsu. Es gibt kein pyx oder ein Modul, das es kompiliert. Wenn Sie es also so einreichen, wie es ist, ist es RE.
Sie müssen also dsu.pyx in Ihren Einreichungscode einbetten.
ALPC-A.py
cycode = r"""
# distutils: language=c++
# distutils: include_dirs=/opt/ac-library
from libcpp cimport bool
from libcpp.vector cimport vector
cdef extern from "<atcoder/dsu>" namespace "atcoder":
cdef cppclass dsu:
dsu(int n)
int merge(int a, int b)
bool same(int a, int b)
int leader(int a)
int size(int a)
vector[vector[int]] groups()
cdef class DSU:
cdef dsu *_thisptr
def __cinit__(self, int n):
self._thisptr = new dsu(n)
cpdef int merge(self, int a, int b):
return self._thisptr.merge(a, b)
cpdef bool same(self, int a, int b):
return self._thisptr.same(a, b)
cpdef int leader(self, int a):
return self._thisptr.leader(a)
cpdef int size(self, int a):
return self._thisptr.size(a)
cpdef vector[vector[int]] groups(self):
return self._thisptr.groups()
"""
import os, sys
if sys.argv[-1] == 'ONLINE_JUDGE':
open('dsu.pyx', 'w').write(cycode)
os.system('cythonize -i -3 dsu.pyx')
from dsu import DSU
n, q = map(int, input().split())
dsu = DSU(n)
res = []
for i in range(q):
t, u, v = map(int, input().split())
if t == 0:
dsu.merge(u, v)
else:
if dsu.same(u, v):
res.append(1)
else:
res.append(0)
print('\n'.join(map(str, res)))
AtCoders Python befindet sich in der Kompilierungsphase (zu diesem Zeitpunkt benötigte Zeit) für Numbas AOT (lesen Sie diesen Artikel, um weitere Informationen zu erhalten). Ist nicht in der Ausführungszeit enthalten) und ONLINE_JUDGE wird während der Kompilierungsphase als Befehlszeilenargument angegeben.
Auf diese Weise bestimmt if sys.argv [-1] == 'ONLINE_JUDGE': in der 30. Zeile, ob es sich in der Kompilierungsphase befindet, und wenn es sich in der Kompilierungsphase befindet, schreibt es die Datei in dsu.pyx. , Cythonize Befehl zum Kompilieren.
Ich habe diesen Code eingereicht und er wurde in 424 ms sicher AC.
Zum Vergleich haben Freiwillige DSU in der AtCoder Library Python Port. Bei Verwendung von python / blob / master / atcoder / dsu.py), bei In Python senden, 635 ms, [In PyPy senden] ](Https://atcoder.jp/contests/practice2/submissions/17535461) Es waren 551 ms.
~~ Nun, trotz der harten Arbeit wird es nicht so schnell ~~
Fenwick Tree
Stellen Sie in ähnlicher Weise Fenwick Tree in Python zur Verfügung.
fenwick_tree.pyx
# distutils: language=c++
# distutils: include_dirs=/opt/ac-library
cdef extern from "<atcoder/fenwicktree>" namespace "atcoder":
cdef cppclass fenwick_tree[T]:
fenwick_tree(int n)
void add(int p, T x)
T sum(int l, int r)
ctypedef long long ll
cdef class FenwickTree:
cdef fenwick_tree[ll] *_thisptr
def __cinit__(self, int n):
self._thisptr = new fenwick_tree[ll](n)
cpdef void add(self, int p, ll x):
self._thisptr.add(p, x)
cpdef ll sum(self, int l, int r):
return self._thisptr.sum(l, r)
Es ist im Grunde das gleiche wie DSU, aber Fenwick Tree verwendet Vorlagen.
Laut Dokument ist int / uint (unsigned int) / ll (long long) / ull (unsigned long long) Es scheint, dass / modint als Typ angegeben werden kann.
Hier ist der Typ ll. (Weil ich denke, dass int und uint durch ll ersetzt werden können)
Wenn Sie einen vollständigen Fenwick-Baum möchten, schreiben Sie ihn neu oder erstellen Sie eine andere Klasse.
~~ modint hat aufgegeben ... ~~
Lösen wir Fenwick Tree Exercises.
ALPC-B.py
cycode = r"""
# distutils: language=c++
# distutils: include_dirs=/opt/ac-library
cdef extern from "<atcoder/fenwicktree>" namespace "atcoder":
cdef cppclass fenwick_tree[T]:
fenwick_tree(int n)
void add(int p, T x)
T sum(int l, int r)
ctypedef long long ll
cdef class FenwickTree:
cdef fenwick_tree[ll] *_thisptr
def __cinit__(self, int n):
self._thisptr = new fenwick_tree[ll](n)
cpdef void add(self, int p, ll x):
self._thisptr.add(p, x)
cpdef ll sum(self, int l, int r):
return self._thisptr.sum(l, r)
"""
import os, sys
if sys.argv[-1] == 'ONLINE_JUDGE':
open('fenwick_tree.pyx', 'w').write(cycode)
os.system('cythonize -i -3 fenwick_tree.pyx')
from fenwick_tree import FenwickTree
n, q = map(int, input().split())
ft = FenwickTree(n)
for i, a in enumerate(map(int, input().split())):
ft.add(i, a)
res = []
for _ in range(q):
t, u, v = map(int, input().split())
if t == 0:
ft.add(u, v)
else:
res.append(ft.sum(u, v))
print('\n'.join(map(str, res)))
Ich [reichte] diesen Code ein (https://atcoder.jp/contests/practice2/submissions/17535413) und er wurde in 1287 ms zu AC. Zum Vergleich: Wenn Sie [Python Ported Fenwick Tree] verwenden (https://github.com/not522/ac-library-python/blob/master/atcoder/fenwicktree.py), In Python einreichen //atcoder.jp/contests/practice2/submissions/17535420) bei 4663 ms, Mit PyPy senden bei 1001 ms tat. ~~ Langsamer als PyPy! Ich bin scharf ... ~~
DSU
| Cython + Python | Python | PyPy |
|---|---|---|
| 424 ms | 635 ms | 551 ms |
Fenwick Tree
| Cython + Python | Python | PyPy |
|---|---|---|
| 1287 ms | 4663 ms | 1001 ms |
Wenn Sie den Teil schreiben, der in Python in Cython erstellt wurde, ist er tatsächlich viel schneller als PyPy. Das Folgende ist der Code, wenn Fenwick Tree Exercises vollständig in Cython geschrieben ist.
ALPC-B.pyx
# distutils: language=c++
# distutils: include_dirs=/opt/ac-library
from libc.stdio cimport scanf, printf
from libcpp.vector cimport vector
cdef extern from "<atcoder/fenwicktree>" namespace "atcoder":
cdef cppclass fenwick_tree[T]:
fenwick_tree(int n)
void add(int p, T x)
T sum(int l, int r)
ctypedef long long ll
cdef int n, q, i, t
cdef ll u, v, a
scanf('%d%d', &n, &q)
cdef fenwick_tree[ll] *ft = new fenwick_tree[ll](n)
for i in range(n):
scanf('%lld', &a)
ft.add(i, a)
for i in range(q):
scanf('%d%lld%lld', &t, &u, &v)
if t == 0:
ft.add(u, v)
else:
printf('%lld\n', ft.sum(u, v))
Diese Einreichung betrug 251 ms.
| Cython | Cython + Python | Python | PyPy |
|---|---|---|---|
| 251 ms | 1287 ms | 4663 ms | 1001 ms |
Super schnell. Warum ist Cython + Python langsamer als PyPy? Ich vermutete, dass die Ursache die Langsamkeit der Python-Schleifenverarbeitung war. Als Experiment senden wir Code in Python und PyPy, der nur die Eingabe für dieses Problem akzeptiert und die Ausführungszeit anzeigt.
ALPC-B-input.py
n, q = map(int, input().split())
for i, a in enumerate(map(int, input().split())):
i, a
for _ in range(q):
t, u, v = map(int, input().split())
Das Ergebnis ist 1012 ms für Python und 687 ms für PyPy. tat. Wenn man dieses Ergebnis von der Ausführungszeit des AC-Codes abzieht, scheint die Verarbeitungszeit des Fenwick-Baums für Cython + Python etwa 275 ms und für PyPy 314 ms zu betragen. ~~ Subtil ~~
Ich denke, Sie sollten PyPy verwenden.