Cet article provient de AtCoder Library, DSU Et Fenwick Tree sera rendu disponible depuis Python en utilisant Cython. Je n'ai pas confirmé s'il existe autre chose que DSU et Fenwick Tree qui peut être utilisé de la même manière, mais par exemple, [Segtree](https://atcoder.github.io/ac-library/production/document_ja/segtree. Je pense que c'est difficile car html) utilise des modèles non typés et Cython ne prend pas en charge les modèles non typés (probablement).
La bibliothèque AtCoder est écrite en C ++, c'est donc plus rapide que d'implémenter la même chose en Python. Cependant, comme je l'expliquerai plus tard, le résultat n'est pas rapide par rapport à PyPy.
Cet article aborde rarement la grammaire de Cython, donc si vous êtes intéressé par Cython dans cet article, veuillez également vous référer à d'autres articles. (Cython fonctionne même si vous écrivez le code Python tel quel.)
C'est un langage pour créer des modules d'extension Python en utilisant C / C ++, et peut appeler des classes et des fonctions C / C ++. C'est un langage pour faire exactement cela. (vraiment?)
Cython et la bibliothèque AtCoder sont nécessaires, nous allons donc les installer. Notez que les utilisateurs de Windows peuvent être bloqués dans la compilation de Cython, nous vous recommandons donc d'utiliser Linux ou WSL si possible.
terminal
$ pip3 install cython
Je vais le faire à. Voyons si Cython peut être utilisé.
hello.pyx
print("Hello, World!")
Un programme qui génère Hello, World!. Notez que l'extension est «.pyx». Compilons et exécutons ceci.
terminal
$ cythonize -i -3 hello.pyx
$ python3 -c "import hello"
Je compile avec la commande cythonize sur la première ligne.
L'option -i le convertit d'abord en code C et le compile dans un format qui peut être importé par Python ( .so sous Linux, .pyd sous Windows).
L'option -3 est utilisée lorsque Python est une série 3.
Comme dans la deuxième ligne, si vous exécutez le code qui importe hello dans Python et Hello, World! Is en sortie, la construction de l'environnement Cython réussit.
AtCoder Library
Créez un dossier / opt / ac-library /. (Cela correspond à l'environnement de juge d'AtCoder.)
Copiez le dossier atcoder dans https://img.atcoder.jp/practice2/ac-library.zip directement en dessous.
DSU Tout d'abord, activez DSU. Afin d'utiliser la bibliothèque AtCoder de Python, Cython nécessite les deux étapes suivantes:
# 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) #constructeur
int merge(int a, int b) #Côté(a, b)Ajouter
bool same(int a, int b) #Apex a,Si b est concaténé
int leader(int a) #Élément représentatif du composant de connexion auquel appartient le sommet a
int size(int a) #La taille du composant de connexion auquel appartient le sommet a
vector[vector[int]] groups() #Liste de "liste des numéros de sommets d'un composant concaténé"
C'est le code qui a rendu DSU disponible en Cython.
La première ligne spécifie que C ++ est utilisé et la deuxième ligne spécifie l'emplacement de la bibliothèque AtCoder.
Les lignes 3 et 4 sont importées pour tirer parti des valeurs booléennes et vectorielles C ++.
À partir de la 5ème ligne, les méthodes de la classe dsu dans l'espace de noms atcoder de atcoder / dsu.hpp (honnêtement, je ne suis pas sûr de C ++, donc je ne suis pas sûr de cela, donc je vais l'implémenter en interne et documentation DSU. Veuillez lire (: //atcoder.github.io/ac-library/production/document_ja/dsu.html) …….), Qui est utilisé en Cython.
Vous avez maintenant un DSU en Cython
cdef dsu *u = new dsu(3)
u.merge(0, 1)
print(u.same(0, 1)) # True
print(u.same(0, 2)) # False
Il est maintenant disponible en tant que.
cdef class DSU:
cdef dsu *_thisptr
#constructeur
def __cinit__(self, int n):
self._thisptr = new dsu(n)
#Côté(a, b)Ajouter
cpdef int merge(self, int a, int b):
return self._thisptr.merge(a, b)
#Apex a,Si b est concaténé
cpdef bool same(self, int a, int b):
return self._thisptr.same(a, b)
#Élément représentatif du composant de connexion auquel appartient le sommet a
cpdef int leader(self, int a):
return self._thisptr.leader(a)
#La taille du composant de connexion auquel appartient le sommet a
cpdef int size(self, int a):
return self._thisptr.size(a)
#Liste de "liste des numéros de sommets d'un composant concaténé"
cpdef vector[vector[int]] groups(self):
return self._thisptr.groups()
Les fonctions et méthodes définies dans cpdef peuvent également être appelées depuis Python. En créant une classe DSU et en appelant la méthode de la classe dsu en interne, cela signifie que l'utilisation de DSU à partir de Python est réalisée.
Ceci termine le code Cython.
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()
Compilons-le pour qu'il puisse être importé en Python.
terminal
$ cythonize -i -3 dsu.pyx
Écrivons le code pour résoudre DSU Exercise en 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)))
Si vous essayez de saisir un échantillon de l'exercice et d'obtenir le résultat correct, c'est un succès pour le moment.
Je voudrais en fait le soumettre à DSU Exercises et confirmer que ce sera AC, mais du côté du juge du Coder dsu. Il n'y a pas de pyx ou de module qui le compile, donc si vous le soumettez tel quel, ce sera RE.
Vous devez donc intégrer dsu.pyx dans votre code de soumission.
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)))
Le Python d'AtCoder est en phase de compilation pour l'AOT de Numba (lisez cet article pour plus d'informations). N'est pas inclus dans le temps d'exécution), et ONLINE_JUDGE est donné comme argument de ligne de commande pendant la phase de compilation.
En utilisant ceci, if sys.argv [-1] == 'ONLINE_JUDGE': sur la 30ème ligne détermine s'il est en phase de compilation, et s'il est en phase de compilation, il écrit le fichier dans dsu.pyx. , Commande Cythonize à compiler.
J'ai [soumis] ce code (https://atcoder.jp/contests/practice2/submissions/17535199) et il est devenu AC en toute sécurité en 424 ms.
À titre de comparaison, les volontaires ont DSU dans la bibliothèque AtCoder Python Port. Lors de l'utilisation de python / blob / master / atcoder / dsu.py), lorsque Soumettre en Python, 635 ms, [Soumettre dans PyPy] ](Https://atcoder.jp/contests/practice2/submissions/17535461) C'était 551 ms.
~~ Eh bien, malgré le travail acharné, ça ne va pas aussi vite ~~
Fenwick Tree
De même, rendez Fenwick Tree disponible en Python.
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)
C'est fondamentalement le même que DSU, mais Fenwick Tree utilise des modèles.
D'après Document, int / uint (unsigned int) / ll (long long) / ull (unsigned long long) Il semble que / modint puisse être spécifié comme type.
Ici, le type est ll. (Parce que je pense que int et uint peuvent être remplacés par ll)
Si vous voulez un ull Fenwick Tree, réécrivez-le ou créez une autre classe.
~~ modint a abandonné ... ~~
Résolvons les Exercices sur l'arbre Fenwick.
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)))
J'ai [soumis] ce code (https://atcoder.jp/contests/practice2/submissions/17535413) et il est devenu AC en 1287 ms. À titre de comparaison, lors de l'utilisation de Python Ported Fenwick Tree, Submit in Python //atcoder.jp/contests/practice2/submissions/17535420) à 4663 ms, Soumettre avec PyPy à 1001 ms fait. ~~ Plus lent que PyPy! Je suis vif ... ~~
DSU
| Cython + Python | Python | PyPy |
|---|---|---|
| 424 ms | 635 ms | 551 ms |
Fenwick Tree
| Cython + Python | Python | PyPy |
|---|---|---|
| 1287 ms | 4663 ms | 1001 ms |
En fait, si vous écrivez la partie qui a été faite en Python en Cython, ce sera beaucoup plus rapide que PyPy. Ce qui suit est le code lorsque Fenwick Tree Exercises est entièrement écrit en Cython.
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))
Cette soumission était de 251 ms.
| Cython | Cython + Python | Python | PyPy |
|---|---|---|---|
| 251 ms | 1287 ms | 4663 ms | 1001 ms |
Super rapide. Alors, pourquoi Cython + Python est-il plus lent que PyPy? Je soupçonnais que la cause était la lenteur du traitement des boucles de Python. À titre expérimental, soumettons du code en Python et PyPy qui accepte simplement l'entrée pour ce problème et voyons le temps d'exécution.
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())
Le résultat est de 1012 ms pour Python et de 687 ms pour PyPy. fait. En soustrayant ce résultat du temps d'exécution du code AC, il semble que le temps de traitement de Fenwick Tree prenne environ 275ms pour Cython + Python et 314ms pour PyPy. ~~ Subtil ~~
Je pense que vous devriez utiliser PyPy.
Recommended Posts