Forum Programmation.python optimisation d'une commande shell en python (ou en shell)

Posté par (page perso) . Licence CC by-sa
Tags : aucun
1
26
août
2013

Bonjour,
j'ai un script python qui récupère le résultat d'une commande shell :

ack-grep $1 /home/user/dico | sort -R | head -1

$1 étant un pattern du style '^..$|^..a$|^..a.b$'

Cette commande dure à peu près 1 seconde avec mon fichier, en utilisation réelle le pattern contient plus de possibilités et on s'approche des 2 secondes, répété des dizaines de fois ça devient gênant. Une idée sur comment améliorer la chose ?

Merci.

  • # et avec 'egrep' ça donne quoi?

    Posté par . Évalué à 2.

    Bonjour,

    Je n'ai pas les conditions pour reproduire ton cas, mais chez moi:

    egrep '^..$|^..a$|^..a.b$' /usr/share/dict/* | sort -R | head -1
    

    répond en moins de la demi seconde (au total, 501k lignes dans la somme des fichiers sources)

    • [^] # Re: et avec 'egrep' ça donne quoi?

      Posté par (page perso) . Évalué à 2.

      Effectivement c'est beaucoup plus rapide (0.02 sec pour la même commande)

      ack-grep était censé être plus rapide mais faut croire que pour un fichier connu c'est beaucoup plus lent.

      • [^] # Re: et avec 'egrep' ça donne quoi?

        Posté par . Évalué à 1.

        Sur le site, la première ligne c'est:

        Designed for programmers with large heterogeneous trees of source code

        La valeur ajoutée, c'était sa capacité à chercher en récursif dans une arborescence de fichier (ce que, si je me souviens bien, grep ne faisait pas à l'époque), et en faisant le tri pour éviter les fichier inintéressants (binaires, …).

        Dans ton cas, t'as pas besoin de tout ça, donc tu paies la surcouche Perl pour rien…

    • [^] # Re: et avec 'egrep' ça donne quoi?

      Posté par . Évalué à 3.

      +1 pour ack-grep qui rame :) le perl ça peut pas gagner en vitesse face au C

      Sinon, je ne comprend pas le sort -R | head -1 si tu veux juste une ligne au hasard peut être que tu devrais le faire en python non ? Parce que sort travaille en O(n log(n)), alors que le calcul que tu veut faire est en O(1) (si tu as déjà tes lignes, donc O(n) au pire, mais c'est déjà la complexité de grep…).

      Please do not feed the trolls

      • [^] # Re: et avec 'egrep' ça donne quoi?

        Posté par (page perso) . Évalué à 2.

        Oui je veux juste une ligne au hasard, le problème de passer par python c'est que je vais devoir instancier une très grosse liste donc le pipe me semblait moins coûteux et j'ai pas trouvé de solution simple pour choisir une ligne au hasard.

        • [^] # Re: et avec 'egrep' ça donne quoi?

          Posté par . Évalué à 4.

          En python je ne sais pas (enfin si, mais pas de tête) mais en perl je sais (et je l'ai même sous la main.

          Tu remplace ton | sort -R | head -n1 par | perl -e 'my ($k,$l)=(1,"");while(<>){my $p=rand();if($p<$k){($k,$l)=($p,$_);}}print $l;'

          Ça se comporte comme un tri selon une variable aléatoire, mais ça ne trie qu'au niveau de la première ligne. C'est donc en O(n). Tu ne peux pas faire mieux. Le choix est en O(1) mais la lecture des lignes est par construction en O(n).

          Sur un exemple de 6⋅10⁵ lignes ça prend 60 fois moins de temps que ta solution.

Suivre le flux des commentaires

Note : les commentaires appartiennent à ceux qui les ont postés. Nous n'en sommes pas responsables.