Twitter iPhone pliant OnePlus 11 PS5 Disney+ Orange Livebox Windows 11

Rechercher une ligne dans un gros fichier trié

25 réponses
Avatar
J.Pierre Pourrez
Bonjour,

J'utilise grep pour rechercher une ligne dans un fichier trié de 14000
lignes.
Je suppose que la recherche se fait ligne par ligne dans le fichier et
cela me semble un peu bourrin quand la recherche s'effectue plusieurs
centaines de fois.

Existe-t-il un remplaçant pour grep qui effectue une recherche plus
rapide genre recherche par dichotomie ?

Je souhaite utiliser cela dans un script shell.

D'avance merci
Jean-Pierre



--
Pensez à lire la FAQ de la liste avant de poser une question :
http://wiki.debian.net/?DebianFrench

Pensez à rajouter le mot ``spam'' dans vos champs "From" et "Reply-To:"

To UNSUBSCRIBE, email to debian-user-french-REQUEST@lists.debian.org
with a subject of "unsubscribe". Trouble? Contact listmaster@lists.debian.org

10 réponses

1 2 3
Avatar
Lehmann Guillaume
J.Pierre Pourrez wrote:
Bonjour,

J'utilise grep pour rechercher une ligne dans un fichier trié de 14000
lignes.


Une seule et unique ligne ?

Je suppose que la recherche se fait ligne par ligne dans le fichier et
cela me semble un peu bourrin quand la recherche s'effectue plusieurs
centaines de fois.

Existe-t-il un remplaçant pour grep qui effectue une recherche plus
rapide genre recherche par dichotomie ?

Je souhaite utiliser cela dans un script shell.


L'option -m de grep permet d'arrêter la recherche une fois
trouvée N fois la ligne. Donc si tu prends 1 comme valeur, dès
que la ligne est trouvée, il s'arrêtera. Au pire c'est comme si
tu parcourais les 14000 lignes (la ligne recherchée se trouve à
la fin), au mieux, tu ne parcoureras que quelques centaines de
ligne (la ligne recherchée est vers le début). Suivant la
fréquence à laquelle tu fais tes recherches et la puissance de ta
machine, ca pourra aller ou pas.

Je ne connais pas d'outil sinon pour faire une recherche par
dichotomie et je pense que si j'en avais besoin, avec une boucle
'for' et la commande 'nl' j'arriverai à trouver mon bonheur :)

Bon we.
Guillaume


--
Pensez à lire la FAQ de la liste avant de poser une question :
http://wiki.debian.net/?DebianFrench

Pensez à rajouter le mot ``spam'' dans vos champs "From" et "Reply-To:"

To UNSUBSCRIBE, email to
with a subject of "unsubscribe". Trouble? Contact
Avatar
Basile STARYNKEVITCH
Le Sun, Nov 14, 2004 at 04:43:21PM +0100, Lehmann Guillaume écrivait/wrote:
J.Pierre Pourrez wrote:
>Bonjour,
>
>J'utilise grep pour rechercher une ligne dans un fichier trié de 14000
>lignes.
Une seule et unique ligne ?

>Je suppose que la recherche se fait ligne par ligne dans le fichier et
>cela me semble un peu bourrin quand la recherche s'effectue plusieurs
>centaines de fois.
>
>Existe-t-il un remplaçant pour grep qui effectue une recherche plus
>rapide genre recherche par dichotomie ?



Non, parce que les fichiers ne sont pas organisés en lignes. Une ligne
est une suite de caractère terminée par le caractère newline.

>
>Je souhaite utiliser cela dans un script shell.
L'option -m de grep permet d'arrêter la recherche une fois
trouvée N fois la ligne [...]




Ceci étant dit, une solution pourrait être d'utiliser un fichier
indexé NDBM ou DBM ou DB pour ça.

On peut ecrire un petit script en Ruby ou Ocaml ou Perl ou Python pour
ça.

Une solution plus lourde (trop usine à gaz pour ça) serait de passer
par un SGBDR comme MySQL ou PostgreSQL.


P.S. C'est dommage que l'automate de cette liste ne positionne pas
automatiquement le reply-to vers cette liste...

--
Basile STARYNKEVITCH http://starynkevitch.net/Basile/
email: basile<at>starynkevitch<dot>net
aliases: basile<at>tunes<dot>org = bstarynk<at>nerim<dot>net
8, rue de la Faïencerie, 92340 Bourg La Reine, France


--
Pensez à lire la FAQ de la liste avant de poser une question :
http://wiki.debian.net/?DebianFrench

Pensez à rajouter le mot ``spam'' dans vos champs "From" et "Reply-To:"

To UNSUBSCRIBE, email to
with a subject of "unsubscribe". Trouble? Contact
Avatar
Jean-Michel OLTRA
bonjour,


Le dimanche 14 novembre 2004, Basile STARYNKEVITCH a écrit...


Ceci étant dit, une solution pourrait être d'utiliser un fichier
indexé NDBM ou DBM ou DB pour ça.



Une autre serait d'utiliser le C. Tu mmap() le fichier en mémoire et tu
y accèdes comme un pointeur. Avec les fonctions de recherche en mémoire
ou sur chaine tu devrais être efficace.

--
jm


--
Pensez à lire la FAQ de la liste avant de poser une question :
http://wiki.debian.net/?DebianFrench

Pensez à rajouter le mot ``spam'' dans vos champs "From" et "Reply-To:"

To UNSUBSCRIBE, email to
with a subject of "unsubscribe". Trouble? Contact
Avatar
Francois
Le Sun, Nov 14, 2004 à 04:43:21PM +0100, Lehmann Guillaume a écrit
J.Pierre Pourrez wrote:
>Bonjour,
>
>J'utilise grep pour rechercher une ligne dans un fichier trié de 14000
>lignes.
Une seule et unique ligne ?

>Je suppose que la recherche se fait ligne par ligne dans le fichier et
>cela me semble un peu bourrin quand la recherche s'effectue plusieurs
>centaines de fois.



Si chaque fois est suite à une action d'un opérateur humain les délais de grep
sont raisonnables. je viens de faire un test (portable PIII 500Mhz, 512 Mo) :
$ time grep -e 'zzzzzzzz' *

real 0m0.071s
user 0m0.030s
sys 0m0.040s
$ pwd
/usr/share/doc/postgresql-doc/html
$ wc -l *|grep total
329529 total
$ du -hs
6,4M .

Si entre les modifications du fichier les mêmes motifs de grep sont utilisés
plusieurs fois il peut être intérressant de stocker les résultats positifs de
grep dans un fichier accélérateur.

Maintenant si le fichier est modifié souvent que les recherches sont toutes
différentes et exécutées dans le cadre d'un traitement automatique qui montre
des problèmes de performance alors la ces méthodes seront insuffisantes surtout
si la mémoire de la machine est insuffisante pour tout garder en mémoire
fichier compris.

>
>Existe-t-il un remplaçant pour grep qui effectue une recherche plus
>rapide genre recherche par dichotomie ?
>
>Je souhaite utiliser cela dans un script shell.
L'option -m de grep permet d'arrêter la recherche une fois
trouvée N fois la ligne. Donc si tu prends 1 comme valeur, dès
que la ligne est trouvée, il s'arrêtera. Au pire c'est comme si
tu parcourais les 14000 lignes (la ligne recherchée se trouve à
la fin), au mieux, tu ne parcoureras que quelques centaines de
ligne (la ligne recherchée est vers le début). Suivant la
fréquence à laquelle tu fais tes recherches et la puissance de ta
machine, ca pourra aller ou pas.

Je ne connais pas d'outil sinon pour faire une recherche par
dichotomie et je pense que si j'en avais besoin, avec une boucle
'for' et la commande 'nl' j'arriverai à trouver mon bonheur :)

Bon we.
Guillaume


--
Pensez à lire la FAQ de la liste avant de poser une question :
http://wiki.debian.net/?DebianFrench

Pensez à rajouter le mot ``spam'' dans vos champs "From" et "Reply-To:"

To UNSUBSCRIBE, email to
with a subject of "unsubscribe". Trouble? Contact




--
Francois Mescam



--
Pensez à lire la FAQ de la liste avant de poser une question :
http://wiki.debian.net/?DebianFrench

Pensez à rajouter le mot ``spam'' dans vos champs "From" et "Reply-To:"

To UNSUBSCRIBE, email to
with a subject of "unsubscribe". Trouble? Contact
Avatar
J.Pierre Pourrez
Le 14/11/04 à 16:43, Lehmann Guillaume écrivait:

>J'utilise grep pour rechercher une ligne dans un fichier trié de 14000
>lignes.
Une seule et unique ligne ?


oui

L'option -m de grep permet d'arrêter la recherche une fois
trouvée N fois la ligne. Donc si tu prends 1 comme valeur, dès
que la ligne est trouvée, il s'arrêtera. Au pire c'est comme si
tu parcourais les 14000 lignes (la ligne recherchée se trouve à
la fin), au mieux, tu ne parcoureras que quelques centaines de
ligne (la ligne recherchée est vers le début). Suivant la
fréquence à laquelle tu fais tes recherches et la puissance de ta
machine, ca pourra aller ou pas.



L'option -m m'a échappé dans la lecture du man

Merci pour le coup de pouce
Jean-Pierre


--
Pensez à lire la FAQ de la liste avant de poser une question :
http://wiki.debian.net/?DebianFrench

Pensez à rajouter le mot ``spam'' dans vos champs "From" et "Reply-To:"

To UNSUBSCRIBE, email to
with a subject of "unsubscribe". Trouble? Contact
Avatar
J.Pierre Pourrez
Le 14/11/04 à 16:59, Basile STARYNKEVITCH écrivait:

Ceci étant dit, une solution pourrait être d'utiliser un fichier
indexé NDBM ou DBM ou DB pour ça.



Je ne trouve un outil simple pour rechercher une clé dans une base DBM à
partir d'un script shell

Bye
Jean-Pierre


--
Pensez à lire la FAQ de la liste avant de poser une question :
http://wiki.debian.net/?DebianFrench

Pensez à rajouter le mot ``spam'' dans vos champs "From" et "Reply-To:"

To UNSUBSCRIBE, email to
with a subject of "unsubscribe". Trouble? Contact
Avatar
J.Pierre Pourrez
Le 14/11/04 à 19:03, écrivait:

Si chaque fois est suite à une action d'un opérateur humain les délais de grep
sont raisonnables. je viens de faire un test (portable PIII 500Mhz, 512 Mo) :
$ time grep -e 'zzzzzzzz' *

real 0m0.071s
user 0m0.030s
sys 0m0.040s
$ pwd
/usr/share/doc/postgresql-doc/html
$ wc -l *|grep total
329529 total
$ du -hs
6,4M .



Le script est executé une fois par semaine, le fichier de 14000 lignes
est créé à chaque fois et correspond aux 14000 paquets de la Sarge.

Le but est de suuprimer les paquets obsolètes dans le cache de
apt-proxy. Voici où j'en suis arrivé

=========== cut here ============================== #!/bin/sh

# supprime tous les packages obsolètes (non référencés dans les fichiers
# Packages) dans le cache d'Apt-proxy

TMPFILE=`mktemp -t purge.XXXXXX`
trap "rm -f $TMPFILE" 0 1 2 5 15

MOTIF="^Filename: "

# récupère la valeur de APT_PROXY_CACHE
APT_PROXY_CACHE=`grep "^APT_PROXY_CACHE=" /etc/apt-proxy/apt-proxy.conf |
cut -d = -f 2`

COUNT=0

for H in `ls $APT_PROXY_CACHE`; do
HOST="$APT_PROXY_CACHE/$H"
echo "============== Host: $HOST ========================="
if [ -d "$HOST" ]; then
rm $TMPFILE
touch $TMPFILE
# certains sites n'ont pas de répertoire dists (E.G.: http://z42.de)
DISTS_DIR="$HOST/dists"
if [ ! -d "$DISTS_DIR" ]; then DISTS_DIR="$HOST"; fi
# recenser tous les noms de fichiers des paquets dans Packages
for PACKAGE in `find $DISTS_DIR -name Packages`; do
grep $MOTIF $PACKAGE | sed "s!$MOTIF!$HOST/!" >> $TMPFILE
done
# on trie tous les noms de fichiers récupérés
mv $TMPFILE $TMPFILE.orig
cat $TMPFILE.orig | sort > $TMPFILE
rm $TMPFILE.orig
# on supprime les paquets non recensés
# éventuellement utiliser l'option -m de grep pour arrêter
# la recherche à la première occurence
for FICHIER in `find $HOST -name "*.deb"`; do
if [ `grep -c $FICHIER $TMPFILE` = "0" ]; then
echo "Remove $FICHIER"
rm -f $FICHIER
COUNT=$(($COUNT+1))
fi
done
fi
done
N=`wc -l $TMPFILE`
echo -e "nSweeping apt-proxy cache...n$COUNT packets deleted / $N known packetsn"

======================= cut here ======================================
C'est vrai que le temps d'execution est acceptable
Si quelqu'un a une suggestion pour améliorer le script, je suis preneur

Merci pour votre aide à tous
Jean-Pierre



--
Pensez à lire la FAQ de la liste avant de poser une question :
http://wiki.debian.net/?DebianFrench

Pensez à rajouter le mot ``spam'' dans vos champs "From" et "Reply-To:"

To UNSUBSCRIBE, email to
with a subject of "unsubscribe". Trouble? Contact
Avatar
Yves Rutschle
On Sun, Nov 14, 2004 at 07:42:38PM +0100, J.Pierre Pourrez wrote:
Le but est de suuprimer les paquets obsolètes dans le cache de
apt-proxy. Voici où j'en suis arrivé



N'est pas ce à quoi sert la variable CLEANUP_DAYS dans
/etc/apt-proxy/apt-proxy.conf?

Y.


--
Pensez à lire la FAQ de la liste avant de poser une question :
http://wiki.debian.net/?DebianFrench

Pensez à rajouter le mot ``spam'' dans vos champs "From" et "Reply-To:"

To UNSUBSCRIBE, email to
with a subject of "unsubscribe". Trouble? Contact
Avatar
J.Pierre Pourrez
Le 14/11/04 à 23:26, Yves Rutschle écrivait:

N'est pas ce à quoi sert la variable CLEANUP_DAYS dans
/etc/apt-proxy/apt-proxy.conf?



Pas vraiment
Pour supprimer un paquet, il faut télécharger une nouvelle version du
paquet, et que le paquet soit plus vieux que CLEANUP_DAYS jours.

Ma méthode est plus radicale: si le paquet ne figure pas dans le fichier
Packages, il est supprimé.

Bye
Jean-Pierre


--
Pensez à lire la FAQ de la liste avant de poser une question :
http://wiki.debian.net/?DebianFrench

Pensez à rajouter le mot ``spam'' dans vos champs "From" et "Reply-To:"

To UNSUBSCRIBE, email to
with a subject of "unsubscribe". Trouble? Contact
Avatar
Sébastien GALLET
J.Pierre Pourrez a écrit :
..
Bye
Jean-Pierre




Si j'ai bien compris, tu utilises apt-proxy pour faire un mirroir de sarge.
As-tu essayé apt-mirror : http://apt-mirror.sourceforge.net/ ?
Seb


--
Pensez à lire la FAQ de la liste avant de poser une question :
http://wiki.debian.net/?DebianFrench

Pensez à rajouter le mot ``spam'' dans vos champs "From" et "Reply-To:"

To UNSUBSCRIBE, email to
with a subject of "unsubscribe". Trouble? Contact
1 2 3