Newsgroup: it.comp.os.linux.iniziare
Titolo: time % find

salve. Devo ordinare file grandi con sort.
Come faccio a conoscere la stima dei tempi che impiegherà il processo 
a terminare, o a controllare a che punto sia arrivato?
Matteo

 a terminare, o a controllare a che punto sia arrivato?
Se man sort non ti aiuta, prendi i sorgenti di sort, studi l'algoritmo
usato, e ci metti l'indicatore di progresso.
In alcuni mesi dovresti riuscire a capire statisticamente quanto ci sta
impiegando.
-- 
           |Save our planet!
    Ciao   |Save wildlife!
   roberto |For your E-MAIL use ONLY recycled Bytes  !!
           |roberto poggi   
rpo...@softhome.net


mmm,
man sort non mi aiuta né info sort
Però a questo punto mi hai fatto venire una curiosità sul tipo di 
algoritmo usato.
Se tengo in considerazione un gzip, questo in modo sequenziale elabora 
e scrive, elabora e scrive a blocchettini, indipendentemente di quanto 
sia lungo il file, e così ti avrebbe saputo dire pure quanto ha 
impiegato i dati elaborati fino al quel momento; l'utente, che sa 
quanto è lungo è il file, saprà quindi indicativamente quanto mancherà 
al termine.
Che algoritmo utilizza invece sort? so che il miglior algoritmo, 
qualunque esso sia, sarà sicuramente maggiore al lineare; solitamente 
è (N)log(N), dipendente quindi da una "ripassata" parziale (almeno 
logaritmo della dim del file). La vedo dura quindi cominciare 
l'elaborazione, o almeno la "ripassata" (termine altamente improprio 
per _supersemplificare_ il procedimento) finchè il file non è tutto 
caricato. Ma sort saprà che e quanto è grande il file solamente dopo 
che gli è stato passato TUTTO in memoria.
Quindi credo che pur volendo scompattare i sorgenti non so quanto sia 
possibile metterci l'indicatore di progresso, né in percentuale né, 
come gzip, in quantità di dati elaborati... nemmeno se mi scrivo da 
zero un 'sort' tutto mio.
Ho detto un macello di stupidaggini?
Matteo

 zero un 'sort' tutto mio.
Bravo, hai colto esattamente nel segno.
L'algoritmo di sort non e' lineare, oltretutto dipende anche dalla
composizione del file di input.
Percio' una barra di avanzamento e' praticamente impossibile da
realizzare.



Come da tuo consiglio, mi sono andato a vedere il codice sorgente di 
sort (non sono molte, solamente 8000 tra cui molti commenti, #define e 
sciocchezze varie), ma non ho ancora terminato. In contemporanea sto 
facendo qualche esperimento.
Non modificherò il codice perchè non ne sono in grado, ma una ideuzza 
sulla teoria mi sta venendo in mente, ma non anticipo niente. E' ovvio 
che non ci sarà mai qualcosa di perfetto, però...
Matteo

 >
Non è completamente corretto.
L'algoritmo non è lineare, ma sufficientemente strutturato da leggerlo 
tale, e non dipende dalla composizione del file di input, bensì 
solamente dalla sua lunghezza che DEVE essere conosciuta, anche se 
l'input non viene da un file ma da una pipe. In quest'ultimo caso 
l'input viene messo in un buffer di dimensione prestabilita, ordinato 
quando si riempie e poi appoggiato in /tmp, 1 file 1 buffer. Al 
termine dell'input (quando ormai tutti i buffer sono stati riempiti ed 
ordinati) viene effettuato un merge la cui complessità computazionale 
è lineare.
Quindi in teoria si può inserire una barra di progresso indicante la 
velocità di elaborazione, nel caso in cui i dati vengano dallo 
standard input, e ciò sarebbe già sufficiente all'utente che potrebbe 
vedere da sè quindi quanto manca (si suppone che lui conosca la 
dimensione del file), magari sort potrebbe indicare quanti dati ha 
correntemente elaborato. Nel caso in cui l'input provenga da un file è 
possibile anche aggiungere la barra di progresso con statistiche dei 
tempi di fine.
Questo è quello che viene dalla mia analisi.
HINT: è possibile controllare le performance/consumo della memoria 
gestendo la dimensione del buffer (e quì man e info aiutano), giocando 
con il parametro -S <dim del buffer>. Nel caso dell'input da pipe, 
sort alloca un buffer di dimensione prestabilita; se questo è più 
piccolo della mole di dati, verranno creati tanti file temporanei 
rallentando il procedimento; riservare un buffer a sort con -S di 
dimensioni elevate (superiori alla mole dei dati, se la si conosce, ma 
okkio alla ram della macchina; mi sembra ce sort ne usi esattamente il 
doppio della dimensione del file e/o buffer che si sta ordinando); 
sort farà un solo passaggio e non scriverà nessun file temporaneo o 
almeno non più di 1 e non ci sarà bisogno di fare alcun merge finale; 
da prove effettuate la velocità aumenta e di non poco. Nel caso 
dell'input da file non viene effettuato nessun file temporaneo. Il 
buffer non viene allocato tutto allo start ma durante l'elaborazione 
(mi sembra), fino ad arrivare al doppio della dim del file. Con -S si 
può specificare di allocarne di più o tutto subito (tanto alla fine 
comunque lo allocherà). Finchè possibile ordinare sempre con 'sort 
nomefile' e non con 'cat nomefile|sort'
Matteo