Newsgroup: it.comp.os.linux.iniziare
Titolo: confrontare una lista con stringa

Ho una stringa, diciamo
# STR="ciaoatuttida.pippo"
e una lista
# cat LISTA
ciao
pippo
pluto
tutto
pippo2
ciao.tutti
io voglio determinare quali occorrenze di LISTA machano nella stringa
STR
nel mio caso, uno script
# mioscript $STR LISTA
dovrebbe restituirmi
ciao
pippo
io ho pensato a
# for a in `cat LISTA`;do echo $STR|grep $a;done
tralasciando il fatto che mi prende anche "ciao.tutti" (che in parte mi
sta bene e comunque facilmente risolvibile), il sistema funziona.
Il problema sorge quando lista è di 500.000 elementi.
Già con 1000 elementi ci mette una decina e passa di secondi (e mi
sembra logico... deve caricare 1000 volte il comando grep).
Anche
# for a in `cat LISTA`;do echo $STR|sed -n /$a/p;done
non migliora la situazione.
Qualcuno conosce qualche sistema migliore?, magari con l'aggiunta di un
perl o awk, (che conosco appena appena).
l'ideale sarebbe quello di raggiungere i tempi della ricerca al
contrario:
# grep tutti LISTA
impiega un attimo. Su 1000 elementi 7 millisecondi; su 500000 elementi
15 millisecondi.
oh, male che vada mi posso fare un piccolo programmino in C, però
vorrei evitare.
Matteo

 ... machano nella stringa...
Che cavolo vuol dire?
Parlare italiano e' troppo complicato?
Dire "quali occorrenze della stringa 
corrispondono" e' al di fuori delle 
capacita` umane?

 echo $STR | fgrep -o -f FILE
ottimo, grazie.
ero riuscito a trovare la soluzione di awk, ma mi si fermava a 327678
righe.
E' possibile che awk non ne gestisca di più?
Matteo

 E' possibile che awk non ne gestisca di più?
Si'

 ... awk... si fermava a 327678 righe.
Ma stai usando busybox?

 Ma stai usando busybox?
no. uso slackware
# awk --version
GNU Awk 3.1.5
Copyright (C) 1989, 1991-2005 Free Software Foundation.
Il numero 327678 è strano, sembra 2^15*10
Matteo

 Il numero 327678 è strano, sembra 2^15*10
Al massimo 5*2^16-2


considerando che la lista è di circa 1.5milioni di righe per un totale
di 29Mb, mi impiega anche fino a 15-20 secondi in caso la ricerca
tocchi l'ultima riga o non tiri fuori nessun risultato.
ordinando FILE è in ordine alfabetico, posso velocizzare la ricerca? o
magari lo posso indicizzare in qualche modo, magari creando un nuovo
file fatto con una struttura ben definita ed indicizzata.
Posso sfruttare il mio biprocessore, magari spezzando in più parti
FILE e lanciandone più di uno in parallelo
In pratica devo ottenere le massime prestazioni in quanto l'output deve
andare in una pagina web e non voglio far aspettare troppo l'utente.
Matteo

 per un totale di 29Mb...
WOW, fgrep e` usato per le ricerche bibliografiche 
ma il caso da te descritto e` simile ad un'altra
operazione molto comune: il controllo ortografico 
di un testo.
Io darei una occhiata ad ispell

> Io darei una occhiata ad ispell
Gli sto dando una occhiata ma non riesco a racapezzarmici (almeno nel
man che è in inglese).
Appena ho un po' di tempo vedo di trovare qualche tutorial in italiano
su internet.
Voi ne conoscete già qualcuno?
Matteo

 ...
ispell (o aspell) e` un correttore ortografico molto
potente, integrabile e portabile; purtroppo agisce
esattamente nella maniera opposta a quanto voluto
cioe` produce le parole che non corrispondono.
Io pensavo che si potesse facilmente adattare ma 
questo richiede uno studio approfondito e del tempo.
Non conoscendo lo scopo e la complessita` del progetto 
a cui stai lavorando penso che forse il mio suggerimento 
sia stato avventato.
A questo punto penso faresti meglio a porre la questione 
ad un gruppo sulla programmazione mettendo in evidenza
cosa vuoi fare, il perche', lo scopo e le specifiche
non tralasciando di far notare che la soluzione trovata 
con fgrep e` risultata inefficiente.

ok, grazie.
Nel frattempo forse è meglio che specifico effettivamente a cosa mi
serve (magari ci sono soluzioni migliori usando tutt'altra strada)
Ho un proxy con squidGuard configurato.
Ho scaricato la bigblacklist che mi procura diverse liste di domini e
url bloccati per un totale di 1.5 milioni di occorrenze pari a 29Mb
squidGuard è velocissimo a confrontare l'url con la lista e decidere
quindi sul passaggio o meno.
squidGuard è configurato che se blocca il sito, restituisce all'utente
una mia password personalizzata in cui informo l'utente che la sua
richiesta è stata bloccata.
Il mio problema è informare l'utente sul motivo preciso per cui è
stato bloccato, specificando quindi con quale blacklist è stato
bannato il link, ed evidenziando in rosso la parte dell'url che ha
provocato il blocco.
Al momento funziona se non fosse per la lentezza con cui all'utente gli
viene proposta la pagina informativa in caso il link non sia sulle
prime liste.
Ma forse, proprio ora mentre scrivo, mi è venuta in mente una ideuzza.
Appena ho un pizzichetto di tempo la provo, poi vi faccio sapere.
Matteo


Da DOVE CACCHIO mi è venuta fuori la parola 'password'!!!!!!!!!!
Forse stavo pensado a chissacchè!!
La parola giusta era 'PAGINA' personalizzata. Cioè la pagina web che
squidGuard invia al posto di quella richiesta per informare l'utente
che è stato bloccato, e all'interno devo scriverci quale sia la
blacklist interessata.
Comunque il sistema che sto facendo è questo:
non mi ero accorto che tra i vari parametri squidGuard può passare
destinationgroup al webserver che mi consente di sapere quale gruppo ha
bloccato l'url.
A questo punto ho fatto un gruppo per ogni blacklist; ogni blacklist
l'ho limitata a 100.000 elementi.
Al momento del test, quindi, conosco quale su blacklist devo fgreppare.
Da una prova command-line questo mi da un risultato di meno di un
secondo (ho provato a cercare l'ultimo elemento della lista e mi ha
dato 600ms), il che è il risultato che speravo.
La pagina la devo ancora terminare.
Matteo

 ...
Scusami, mi e` partita per errore una 
lettera; in realta` volevo salvarla nelle 
bozze per rispondere in un secondo momento;
avevo un paio di idee che volevo approfondire.
Ho anche inviato un messaggio di cancellazione 
ma purtroppo non e' stato propagato atraverso 
i server; mi scuso di nuovo.
Comunque la mia prima idea era di controllare 
se squidGuard potesse produrre il risultato 
che desideri; vedo che comunque ci sei arrivato 
da solo.
La seconda idea si e` rivelata una stupidata; te 
la risparmio.


adesso mi hai messo la curiosità... o evitavi di dirmelo o, ormai,
dimmelo (almeno l'idea).
Matteo