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⋅105 lignes ça prend 60 fois moins de temps que ta solution.
[^] # Re: et avec 'egrep' ça donne quoi?
Posté par jben . En réponse au message optimisation d'une commande shell en python (ou en shell). É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 -n1par| 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 enO(1)mais la lecture des lignes est par construction enO(n).Sur un exemple de 6⋅105 lignes ça prend 60 fois moins de temps que ta solution.