Un peu d'histoire sur Python
Python est un excellent langage. J'ai essayé plusieurs langues avant: Pascal à l'école; C, C avec cours, C ++ à l'université. Les deux (trois) derniers ont instillé une forte aversion pour la programmation: au lieu de résoudre le problème, vous vous trompez d'allocations et de destructeurs (mots effrayants du passé), vous pensez en termes de primitives de bas niveau. Mon opinion est que C ne convient pas pour résoudre des problèmes éducatifs et scientifiques (en tout cas, dans le domaine des mathématiques). Je suis sûr qu'ils s'opposeront à moi, mais je n'essaie d'imposer quoi que ce soit à personne, j'exprime simplement mon opinion.
Python était autrefois une révélation. Pour la première fois de ma vie, j'ai écrit plusieurs niveaux d'abstraction supérieurs à ce qui est habituel en C. La distance entre la tâche et le code a été réduite comme jamais auparavant.
J'aurais probablement fait ça toute ma vie en Python si je n'avais pas eu à mettre en place subitement des tests statistiques NIST. Il semblerait que la tâche soit très simple: il y a un tableau de longueur plusieurs (> = 10) mégaoctets, il y a un ensemble de tests qui doivent être appliqués à ce tableau.
À quoi sert bon numpy?
En python, il existe un bon paquet numpy pour travailler avec des tableaux, qui est essentiellement une interface de haut niveau pour des bibliothèques rapides comme LAPACK. Il semblerait que l'ensemble complet de gentleman pour le calcul scientifique soit disponible (Sympy, Numpy, Scipy, Matplotlib), que demander de plus?
Tous ceux qui ont traité avec numpy savent qu'il est bon, mais pas en tout. Nous devons également essayer de nous assurer que les opérations sont vectorisées (comme dans R), c'est-à-dire en un sens, uniforme pour l'ensemble du réseau. Si tout à coup votre problème pour une raison quelconque ne rentre pas dans ce paradigme, alors vous avez des problèmes.
De quel type de tâches non vectorisées est-ce que je parle? Oui, prenez au moins le même NIST: calculez la longueur du registre à décalage linéaire en utilisant l'algorithme Berlekamp-Messi; calculer la longueur de la sous-séquence la plus longue d'unités consécutives et ainsi de suite. Je n'exclus pas la possibilité qu'il existe une sorte de solution ingénieuse qui réduira le problème à une solution vectorisée.
Rusé?A titre d'exemple du même NIST: il a fallu calculer le nombre de «switchs» de la séquence, où par «switch» je veux dire changer les unités consécutives (... 1111 ...) en zéros consécutifs (... 000 ... ), et vice versa. Pour ce faire, vous pouvez prendre la séquence d'origine sans le dernier élément (x [: -1]) et en soustraire la séquence décalée de 1 (x [2:]), puis calculer le nombre d'éléments non nuls dans la nouvelle séquence résultante. Tous ensemble ressembleront à:
np.count_nonzero(x[:-1] - x[1:])
Cela peut ressembler à une séance d'entraînement divertissante pour l'esprit, mais essentiellement quelque chose de non naturel se produit ici, une astuce qui ne sera pas évidente pour le lecteur après un court laps de temps. Sans oublier que c'est encore lent - personne n'a annulé l'allocation de mémoire.
Les opérations non vectorisées en Python sont longues. Comment y faire face si numpy ne suffit pas? Ils proposent généralement plusieurs solutions:
- Numba JIT. Si elle a travaillé comme décrit sur la page de titre de Numba, alors je pense que cela vaudrait la peine de terminer l'histoire. J'avais un peu oublié par le passé ce qui avait mal tourné avec elle; l'essentiel est que l'accélération n'a pas été aussi impressionnante que je m'y attendais, hélas.
- Cython. OK, levez la main ceux qui croient que le cython est une solution vraiment belle et élégante qui ne détruit pas le sens et l'esprit même de Python? Je ne le pense pas; si vous arrivez à Cython, vous pouvez déjà arrêter de vous tromper et passer à quelque chose de moins sophistiqué comme C ++ et C.
- Réécrivez les goulots d'étranglement en C et retirez-les de votre bien-aimé Python. D'accord, mais que se passe-t-il si j'ai tout le programme - tout est question de calculs et de goulots d'étranglement? Xi n'offre pas! Je ne parle pas du fait que dans cette solution, vous devez connaître non pas un, mais deux langages - Python et C.
Voici le JULIA!
Ayant envisagé les solutions existantes et n'ayant rien trouvé (incapable de programmer), j'ai décidé de le réécrire avec quelque chose de «plus rapide». En fait, si vous écrivez «batteur de nombres» au 21e siècle avec un support normal pour les tableaux, les opérations vectorisées «prêtes à l'emploi», etc. etc., alors votre choix n'est pas très dense:
- Fortran . Et ne riez pas, lequel d'entre nous n'a pas tiré BLAS / LAPACK de nos langues préférées? Fortran est un très bon (meilleur SI!) Langage pour l'informatique SCIENTIFIQUE. Je ne l'ai pas pris pour la raison que depuis l'époque de Fortran beaucoup de choses ont été inventées et ajoutées aux langages de programmation; J'espérais quelque chose de plus moderne.
- R souffre des mêmes problèmes que Python (vectorisation).
- Matlab - probablement oui, je n'ai malheureusement pas d'argent pour vérifier.
- Julia - le cheval est sombre, décollera, ne décollera pas (et c'était naturel jusqu'à la version stable 1.0)
Quelques avantages évidents de Julia
- Il ressemble à Python, au moins le même "de haut niveau", avec la possibilité, si nécessaire, de descendre en bits en nombre.
- Pas de problème avec les allocations de mémoire et autres.
- Système de type puissant. Les types sont prescrits en option et très dosés. Un programme peut être écrit sans spécifier un seul type - et si vous le faites, ils pourront le faire rapidement. Mais il y a des nuances.
- Il est facile d'écrire des types personnalisés qui seront aussi rapides que les types intégrés.
- Envoi multiple. Vous pouvez en parler pendant des heures, mais à mon avis - c'est le meilleur que Julia a, c'est la base de la conception de tous les programmes et, en général, la base de la philosophie de la langue.
Grâce à l'envoi multiple, beaucoup de choses sont écrites de manière très uniforme.
Exemples d'envois multiples rand() # 0 1 rand(10) # 10 0 1 rand(3,5) # 3 5 .... using Distributions d = Normal() # 0, 1 rand(d) # rand(d, 10) # 10 ...
Autrement dit, le premier argument peut être n'importe quelle distribution (unidimensionnelle) de Distributions, mais l'appel de fonction restera littéralement le même. Et pas seulement la distribution (il est possible de transmettre le RNG lui-même en tant qu'objet MersenneTwister et bien plus). Un autre exemple (à mon avis, illustratif) est la navigation dans les DataFrames sans loc / iloc.
- 6. Les tableaux sont natifs et intégrés. Vectorisation prête à l'emploi.
Inconvénients de garder le silence sur ce qui serait un crime!
- Nouvelle langue. D'un côté, bien sûr, un moins. Dans quelque chose, peut-être immature. D'autre part, il a pris en compte le rake de nombreuses langues passées, se tient «sur les épaules de géants», a absorbé beaucoup de choses intéressantes et nouvelles.
- Il est peu probable que des programmes immédiatement rapides écrivent. Il y a des choses non évidentes qui sont très faciles à gérer: vous montez sur le râteau, demandez de l'aide à la communauté, recommencez ... etc. Il s'agit principalement de l'instabilité de type, de l'instabilité de type et des variables globales. En général, pour autant que je sache par moi-même, un programmeur qui veut écrire rapidement en Julia passe par plusieurs étapes: a) écrit en Python. C'est très bien, et c'est le cas, mais parfois il y aura des problèmes de performances. b) écrit comme dans C: prescrire les types de façon maniaque dans la mesure du possible. c) comprend progressivement où il est nécessaire (très mesuré) de prescrire des types et où ils interfèrent.
- Écosystème Certains paquets sont bruts, dans le sens où quelque part en permanence quelque chose tombe; certains sont matures, mais incohérents (une conversion vers d'autres types est nécessaire, par exemple). D'une part, c'est évidemment mauvais; d'un autre côté, Julia a beaucoup d'idées intéressantes et audacieuses simplement parce que "nous sommes sur les épaules des géants" - nous avons accumulé une énorme expérience de marcher sur un râteau et "comment ne pas le faire", et cela est pris en compte (partiellement) par les développeurs de packages.
- Numéroter des tableaux à partir de 1. Ha, en plaisantant, c'est bien sûr un plus! Non, eh bien, sérieusement, quel est le problème, avec quel index commence la numérotation? On s'y habitue en 5 minutes. Personne ne se plaint que les entiers soient appelés entiers, pas entiers. Ce sont toutes des questions de goût. Et oui, prenez au moins le même Cormen selon les algorithmes - tout est numéroté à partir d'un là, et il est parfois gênant de le refaire en Python au contraire.
Eh bien, pourquoi la vitesse?
Il est temps de se rappeler pourquoi tout a commencé.
Remarque: j'ai oublié Python en toute sécurité, alors écrivez vos améliorations dans les commentaires, je vais essayer de les exécuter sur mon ordinateur portable et voir le temps d'exécution.
Donc, deux petits exemples avec des repères microbiens.
Quelque chose vectoriséProblème: un vecteur X de 0 et 1 est alimenté en entrée de la fonction. Il faut le convertir en vecteur de 1 et (-1) (1 -> 1, 0 -> -1) et calculer combien de coefficients de la transformée de Fourier de ce vecteur sont la valeur absolue dépasse la limite limite.
def process_fft(x, boundary): return np.count_nonzero(np.abs(np.fft.fft(2*x-1)) > boundary) %timeit process_fft(x, 2000) 84.1 ms ± 335 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)
function process_fft(x, boundary) count(t -> t > boundary, abs.(fft(2*x.-1))) end @benchmark process_fft(x, 2000) BenchmarkTools.Trial: memory estimate: 106.81 MiB allocs estimate: 61 -------------- minimum time: 80.233 ms (4.75% GC) median time: 80.746 ms (4.70% GC) mean time: 85.000 ms (8.67% GC) maximum time: 205.831 ms (52.27% GC) -------------- samples: 59 evals/sample: 1
Nous ne verrons rien de surprenant ici - tout de même, ils ne le considèrent pas eux-mêmes, mais le transmettent à des programmes fortran bien optimisés.
Quelque chose de non vectorisableUn tableau de 0 et 1 est appliqué à l'entrée. Trouvez la longueur de la sous-séquence la plus longue d'unités consécutives.
def longest(x): maxLen = 0 currLen = 0
function longest(x) maxLen = 0 currLen = 0 # This will count the number of ones in the block for bit in x if bit == 1 currLen += 1 maxLen = max(maxLen, currLen) else maxLen = max(maxLen, currLen) currLen = 0 end end return max(maxLen, currLen) end @benchmark longest(x) BenchmarkTools.Trial: memory estimate: 0 bytes allocs estimate: 0 -------------- minimum time: 9.094 ms (0.00% GC) median time: 9.248 ms (0.00% GC) mean time: 9.319 ms (0.00% GC) maximum time: 12.177 ms (0.00% GC) -------------- samples: 536 evals/sample: 1
La différence est évidente à l'œil nu. Des conseils pour "terminer" et / ou vectoriser la version numpy sont les bienvenus. Je veux également noter que les programmes sont presque identiques. Par exemple, je n'ai pas enregistré un seul type dans Julia (comparer avec le précédent) - tout de même, tout fonctionne rapidement.
Je tiens également à noter que les versions présentées n'ont pas été incluses dans le programme final, mais ont été encore optimisées; ici, ils sont donnés à titre d'exemple et sans complications inutiles (transmission de mémoire supplémentaire dans Julia pour faire rfft en place, etc.).
Qu'est-ce qui est finalement sorti?
Je ne montrerai pas le code final pour Python et pour Julia: c'est un secret (au moins pour l'instant). Au moment où je me suis arrêté pour terminer la version python, il a travaillé tous les tests NIST sur un tableau de 16 mégaoctets de caractères binaires en ~ 50 secondes. Sur Julia en ce moment, tous les tests s'exécutent sur le même volume ~ 20 secondes. Il se pourrait bien que je sois un idiot, et qu'il y avait place pour des optimisations, etc. etc. Mais c'est moi, comme je suis, avec tous ses avantages et ses inconvénients, et à mon avis, ce n'est pas la vitesse sphérique des programmes en vase clos dans les langages de programmation qui doit être prise en compte, mais comment je peux personnellement le programmer (sans erreurs vraiment grossières).
Pourquoi ai-je écrit tout ça?
Les gens
ici sont devenus intéressés; J'ai décidé d'écrire quand l'heure apparaît. À l'avenir, je pense passer en revue Julia de manière plus approfondie, avec un exemple de résolution de certains problèmes typiques. Pourquoi? Plus de langues, bonnes et différentes, et laissez tous ceux qui veulent trouver quelque chose qui lui convient personnellement.