Newsgroup: it.comp.os.linux.development
Titolo: processare file di 500 MB per linea...

Devo estrarre da un file di log piuttosto grosso dei numeri per dei calcoli! 
Il file è organizzato per linea, e per pura semplicità viene processato con
uno script, ma il buon vecchio grep | tail | head è a dir poco LUMACHEVOLE.
Mi son fatto dei microprogrammini in c per accellerare le operazioni più
lente, e al momento il collo di bottiglia è il posizionarsi sulla riga che
serve!   
Ho adottato il seguente prog:
[..]
 while (fgets(linea,sizeof(linea),file_di_log) != NULL) {
   if (n_riga == n_riga_da_estrarre) {
      printf("%s",linea);
      exit(0);
   }
   n_riga++;
 }
ma dato che viene eseguito per ogni riga del file, porta via comunque molto
tempo specialmente se siamo verso righe a 4 cifre! 
Non c'è un modo per potersi posizionare direttamente alla riga i-esima senza
doversi scorrere tutto il file? 
______________________________
Per scrivermi Togli l'anno
(^_^) Simone

 senza doversi scorrere tutto il file?
fseek , guarda la manpage.
ciao.
-- 
-------------------------------------------------------------------------------
Quando hai un nemico, siediti sulla riva del fiume e aspetta.  Prima o
poi vedrai il suo cadavere passare.
                -- Antico proverbio cinese
-------------------------------------------------------------------------------

 
fseek va bene se le righe sono tutte lunghe uguali, altrimenti ... non 
c'e' verso, devi scorrere tutto il file, oppure te lo indicizzi in 
qualche modo.
Ciao.
Stefano.

 qualche modo.
Infatti le righe non sono tutte uguali! Ho dato un'occhiata a fseek e ftell,
si scorre a suon di byte, però potrei sfruttare in qualche modo la macro
SEEK_CUR, magari passandola alla funzione per posizionarsi subito al posto
giusto, bho... continuo a scervellarmi! 
Per indicizzare cosa intendi, una specie di struttura fast-recover stile DB?
Il prob è che non posso cambiale la struttura del file in nessun modo,
tanto tanto potrei aggiungerci una chiave ad ogni riga, il numero riga per
esempio, ma cosa cambierebbe?
Simone
-- 


 esempio, ma cosa cambierebbe?
Cambierebbe tantissimo, perche` potresti fare una ricerca binaria
per la riga che vuoi -- O(log N), mentre la ricerca sequenziale che
devi fare non avendo il numero di riga e` O(N).
CON numero di riga: vai a circa a 1/2 file (o euristicamente a un
posto funzione del #riga che cerchi / il totale, non cambia l'O(log N)
ma puo` accelerare di un fattore costante), leggi un blocco che sai
grande abbastanza da contenere almeno una fine-riga e successivo
numero di riga, vi cerchi il primo fine-riga, controlli se e` < o >
(o == e allora hai vinto la lotteria:-) di quello che cerchi.  Se <
ripeti nella 2a meta` del file, se > nella 1a.  Cosi` dimezzi ogni
volta l'area in cui cercare, quindi leggendo ad es blocchi di 8K,
con massimo 10 letture trovi la riga di certo un un file di 8M.
Attenzione che l'algoritmo di ricerca binaria SEMBRA semplice ma e`
facile sbagliare.  Se puoi programmarlo in linguaggi piu` ad alto
livello, meglio (tanto sei I/O bound, il tempo di CPU conta poco!).
Alex

Il prob è che non posso cambiale la struttura del file in nessun modo,
Gli indici puoi tenerli separati dal file, su un file di appoggio o in memoria.
Alessandro.


Se poi riuscisse a costruire un vettore il cui i-esimo elemento contiene la 
posizione nel file dell'inizio dell'i-esima riga avrebbe un tempo di
accesso costante.
Alessandro.

test wrote:

Supponendo che il tempo di accesso al file-indice (immagino alcune
decine di megabyte) sia costante, si`; per la costruzione del file-indice
pero` un tempo O(N) e` inevitabile (come lo e` per l'aggiunta dei
numeri di linea al file esistente).  Ricostruire il file-indice da
capo ogni volta e` presumibilmente improponibile (a meno che il
programma non abbia poi MOLTI accessi su cui ammortizzare questo
grosso costo di start-up).  Costruirlo una tantum e` possibile, ma
quanto al tenerlo aggiornato, bisogna vedere (se il programma che
prepara il "filone" aggiungendovi righe, come puo` 'tanto tanto'
essere modificato per aggiungere il numero di line alle righe che
aggiunge, puo` esserlo anche per scrivere su di un altro file?  E`
in un linguaggio in cui scoprire un offset in byte nel file e`
ragionevolmente facile?  ci sono parecchie cose che non sappiamo
sull'architettura complessiva dell'applicazione e suoi vincoli).
Alex

aggiunge, puo` esserlo anche per scrivere su di un altro file?
Un indice esterno gestito dal programma che deve analizzare il file
stesso non richiederebbe alcuna modifica del programma che produce il file.
Quanto all'eventale aggiornameto degli indici, nell'ipotesi di un file gestito
in "append", basterebbe partire dall'indice dell'ultima riga conosciuta senza
dover scorrrere tutto il file.
Alessandro.

test wrote:

Si`, facendo varie diverse ipotesi (non chiarite dall'autore del post
originale) si possono ipotizzare diverse soluzioni.  Quindi, come appunto
dicevo (in parti del mio post che hai snippato), e` inutile continuare
ad affastellare ipotesi senza saperne di piu` sull'architettura complessiva
del sistema.  Se ogni linea comprende il suo numero, e che questo sia
possibile e` una delle poche cose che l'autore del post originale si e`
degnato di dirci;-), la ricerca binaria e` sicuramente fattibile e O(log N).
Essa non richiede neppure che i numeri di linea siano consecutivi, solo
che siano crescenti.
Varie possibili soluzioni O(1) richiedono ulteriori informazioni -- se
nulla viene mai cancellato o inserito, ma solo 'appeso', al filone da
mezzo giga, la situazione e` ben diversa, ad esempio, come fai notare
[il lavoro di aggiornamento del file ausiliario e` allora O(N-N1) dove N1
era la dimensione del filone al tempo dell'ultimo aggiornamento, e non
abbiamo nessuna informazione per confrontare questo con ricerche O(log N)].
Oppure, come facevo notare io, se il programma che cambia il filone
puo` anche scrivere un altro file di supporto, allora si possono gestire
le cose in modo diverso.  Ecc, ecc.
Alex

del sistema.
Si, senza il feedbeck dell'autore si tratta solo di "esecizi accademici"... :-)
Alessandro.