Python3.3: optimisation racine carrée

Question

Voici le code sur Python3.3:

import sys, re, math 
str1 = str(sys.stdin.readlines()) 
Data = re.findall('\\b\\d+\\b', str1) 

for i in reversed (Data): 
    print('%.4f' % math.sqrt(float(i))) 

comme vous pouvez le voir, ce programme grappins données (chaîne multi-ligne au hasard) d'entrée, et rechercher tous les chiffres cette chaîne contient. Après cela renvoie juste la racine carrée de chaque chiffre qu'il trouve.

Eh bien, l'algorithme fonctionne, mais pas assez vite, et je ne sais pas comment l'optimiser. S'il vous plaît aidez-moi avec ça. Ce que je dois faire pour optimiser le code ci-dessus?

Answer 1

Ceci est un résultat négatif. J'ai essayé d'utiliser quelques astuces pour le rendre plus rapide, mais c'est un peu plus rapide.

import sys, re, math 

def find_numbers(f): 
    for line in f: 
     for word in line.split(): 
      if word.isdigit(): 
       yield float(word) 

lst = list(find_numbers(sys.stdin)) 
lst.reverse() 
for x in lst: 
    print('%.4f' % math.sqrt(x)) 

Je pensais que l'inversion de la liste pourrait être fait lent, mais il n'a pas fait vraiment beaucoup de différence quand je viens d'imprimer les chiffres sans marche arrière.

La solution la plus rapide pour Python serait de simplement exécuter le code ci-dessus dans PyPy.

Ce n'est pas un problème très difficile, et si vous avez besoin de vitesse, vous pouvez écrire une solution en code C. Le code C sera à peu près aussi rapide que possible pour ce problème.

Answer 2

Vous pouvez essayer de charger et de traiter le fichier avec Numpy:

import numpy as np 
for i in reversed(np.fromfile(sys.stdin, sep=' ')**0.5): 
    print i 

En tant que bibliothèque numérique de haute performance pour Python, je pense que ce soit la solution la plus rapide pour vous.

Answer 3

import sys, re, math 
str1 = str(sys.stdin.readlines()) 
Data = re.findall('\\b\\d+\\b', str1) 

d2 = [round(math.sqrt(float(i)),4) for i in reversed (Data)] 

for i in d2: 
    print(i) 

Answer 4

Vous avez demandé Python, mais cela peut être fait assez bien en C. Ce programme C ne renverse pas les chiffres, mais vous pouvez simplement redirigez la sortie vers le programme tac, qui est comme cat mais inverse la lignes. Dans mes tests, il s'agit d'environ 3 fois la vitesse de la solution NumPy et environ 6 fois la vitesse de ma solution Python ou de la solution d'origine.

#include <ctype.h> 
#include <math.h> 
#include <stdio.h> 

int 
main() 
{ 
    char buf[1024]; 
    char ch; 
    float f; 
    int i, n; 

    for (i = 0;;) 
    { 
     ch = getchar(); 

     if (i > sizeof(buf)) 
     { 
      fprintf(stderr, "number too long!\n"); 
      return 1; 
     } 

     if (isspace(ch) || EOF == ch) 
     { 
      if (i > 0) 
      { 
       buf[i] = '\0'; 
       n = atoi(buf); 
       f = sqrtf(n); 
       printf("%0.4f\n", f); 
       i = 0; 
      } 

      if (EOF == ch) 
       return 0; 

      continue; 
     } 

     buf[i++] = ch; 
    } 
} 

Answer 5

Mise à jour: Toutes mes excuses pour l'affichage d'un double de steveha's much earlier answer. Parle de volumes sur mes compétences en lecture. Toujours en laissant cette réponse en ligne pour l'instant, juste à cause de mes réflexions sur les effets d'E/S/Buffering/Runtime.

Original post:

Je ne peux pas croire qu'il faut Python plus d'appliquer une expression régulière, et de calculer une racine carrée, qu'il ne faut pour lire une ligne d'entrée et la sortie standard d'un résultat sur la norme sortie (ou toute E/S d'ailleurs).

Comme les E/S à un moment donné proviendront d'un disque dur et iront soit à un autre disque dur, soit à l'œil d'un utilisateur, cela devrait être le facteur limitant.

Les E/S sont généralement tamponnées pour l'accélération. Habituellement, un tampon est rempli en rafales, puis le processeur reste inactif en attendant que le périphérique fournisse plus de données.

Cela conduit à un générateur pour votre application.Ecrire un générateur qui lit l'entrée ligne par ligne et fournit immédiatement un numéro de carré à la demande. Je doute que ce sera plus lent que la vitesse globale d'E/S sur tout matériel moderne raisonnable. Si vous êtes sur un périphérique spécial (comme embedded, uController, Raspberry Pi, etc, faites-le nous savoir)

La seule optimisation que vous pouvez faire est de précompiler l'expression régulière. Comme vous utilisez la même expression rationnelle pour chaque test, faisons l'analyse de l'expression rationnelle une seule fois. Votre exemple dans la question est bon parce que vous faites un re.findall(). Je suis en train d'élaborer pour d'autres lecteurs.

import sys, re, math 

pattern = re.compile(r'\b\d+\b') 

def fh_numbers_to_sqrt(fh): 
    for line in fh: 
     for i in re.findall(pattern, line): 
      yield math.sqrt(float(i)) 

numbers_g = fh_numbers_to_sqrt(sys.stdin) 
for num in numbers_g: 
    print('%.4f' % num) 

Cela permet à toutes les opérations mathématiques et expressions rationnelles d'être entrelacées avec les temps d'E/S.

Maintenant, la seule chose que nous ne pouvons pas vraiment optimiser et intégrer est le reverse. L'algorithme doit attendre jusqu'au dernier élément pour pouvoir inverser.

On pourrait donc changer le code appelant à:

numbers_g = fh_numbers_to_sqrt(sys.stdin) 
for num in reverse(list(numbers_g)): 
    print('%.4f' % num) 

et nous espérons que c'est plus rapide ce que vous aviez à l'origine. Encore une fois, la seule raison pour laquelle cela devrait être plus rapide est parce que nous avons caché l'exécution de l'analyse et du calcul de l'expression rationnelle dans l'horloge murale nécessaire pour lire les données de l'entrée standard. Cela devrait toujours être limité aux E/S. En fait, il se peut que le reverse ne soit pas réellement ajouté à l'exécution globale, car il peut simplement s'intercaler avec l'E/S qui se produit sur la sortie standard. En regardant une horloge murale, cet algorithme pourrait ne pas utiliser de temps du tout. :-)

Pour prouver ou annuler l'ensemble de mon article, vous pouvez mesurer avec time.time() combien de temps il faut entre le début de votre script et juste avant la ligne Data = re.findall, et à partir de là jusqu'à la fin. Si j'ai raison, la lecture des données prendra le plus de temps. Si ce n'est pas le cas, il est utile de mesurer également le temps requis pour toutes les recherches d'expressions régulières. Laissez nous savoir. Je suis curieux ...