[Python] split di file di grandi dimensioni

[Daniele Varrazzo]

On Fri, 04 Dec 2009 20:16:05 +0100, Pietro Battiston <toobaz a email.it>
wrote:
> Il giorno ven, 04/12/2009 alle 19.33 +0100, Daniele Varrazzo ha scritto:
>> On Fri, 04 Dec 2009 19:05:12 +0100, Pietro Battiston <toobaz a email.it>
>> wrote:
>> > Il giorno ven, 04/12/2009 alle 13.39 +0100, Daniele Varrazzo ha
>> > scritto:
>> 
>> >> Io infatti avrei salvato tutti i dizionari dopo un numero prefissato
>> >> di
>> >> righe lette dal file di input. In questo modo l'occupazione di
memoria
>> è
>> >> controllata e le prestazioni credo siano in linea (qualche file
>> potrebbe
>> >> avere poche righe, ma se su 1000 file aperti si scrivono 1M di righe
>> >> statisticamente siamo lì). Credo sia anche molto più semplice da
>> >> scrivere e
>> >> meno soggetto ad errori.
>> >> 
>> > 
>> > A me sembrerebbe più efficiente una via di mezzo: si scrive su file
>> > ogni
>> > volta che si è raggiunta l'occupazione massima di memoria, ma si
>> > scrive
>> > solo il file con più righe (da scrivere).
>> > 
>> > Significa semplicemente ogni volta che c'è da scrivere fare un max su
>> > una lista di 1000 elementi (quella delle lunghezze, che può essere
>> > tranquillamente creata al volo - len ha costo costante, giusto?), e
non
>> > mi sembra che possa avere un gran impatto, anche nel caso pessimo in
>> > cui
>> > le righe destinate ai diversi file ricorrano con frequenze molto
>> > simili.
>> 
>> Questo non occupa una quantità di memoria costante: potrebbe essere
>> difficile da controllare (metti se per esempio molti dei file si
>> "gonfiano"
>> ma poi restanto a lungo non chiamati in causa: questi resterebbero in
ram
>> per non far niente). 
> 
> Può essere meglio tenerli in RAM che fare 1000 "microscritture" su
> disco.

In che senso "può essere"? A parte che è un'affermazione un po' arbitraria
(come tutto questo discorso peraltro, ma si fa per giocare) stai
confrontando due algoritmi paragonando l'occupazione di memoria di uno col
numero di accessi al disco di un altro: non è comparare le stesse cose.

Il mio algoritmo (non testato) è

def split_file(file_name):
    parts = defaultdict(list)

    input = iter(open(input_file))
    try:
        while 1:
            # leggi un blocco di record
            for i in xrange(RECORDS_TO_READ):
                record = input.next()
                parts[get_filename(record)].append(record)

            # Scrivi i file letti
            write_files(parts)

    # Fine file: scrivi i record che restano
    except StopIteration:
        write_files(parts)

def write_files(parts)
    # questo consuma il dizionario
    for filename in parts.keys():
        open(filename, 'a').write(
            ''.join(parts.pop(k)))
    
Ipotizziamo che ci sono n record ed m file in cui scrivere. Diciamo per
mettere dei numeri che n=1e9 e m=1e3. In queste condizioni setterei
RECORDS_TO_READ = 1e6 (= k). Io dico che questo algoritmo ha occupazione di
memoria limitata ed effettua il minimo numero di scritture in presenza di
dati normali (ovvero circa n / k * m ~= 1e6). L'occupazione di memoria
costante è la prima preoccupazione a fronte di un input di grande
dimensioni.


>> Ha anche alcune quadraticità (il singolo len è o(1) ma
>> il max è o(n)).
> 
> 'spe, 'spe
> 
> Poniamo che in memoria ci stiano anche solo un milione di righe, e che i
> file siano mille: significa che al caso pessimo, ogni scrittura implica
> almeno 1000 righe: ovvero, ogni 1000 righe lette/scritte farò 1000
> chiamate a len ed una chiamata a max.
> 
> Certamente non aumenta l'ordine di grandezza, e penso che anzi in
> termini quantitativi il tempo necessario in più sia trascurabile, perché
> non c'è paragone tra una chiamata a len e la lettura+scrittura di una
> riga (e questo è il caso pessimo).

Potresti scrivere un accenno del tuo algoritmo? Non ho capito esattamente
quando vuoi chiamare il max. Ovvero: quando aggiungi un record ad una
lista, se questo record ha superato una cera soglia (es. 1000) tu scrivi
questi record nel file e svuoti la lista? oppure ogni k record che leggi in
input cerchi la lista più lunga e scrivi il file corrispondente (ma in
questo modo ogni k record ne scrivi solo k / m in media, quindi
l'occupazione di memoria continua a crescere)...

Probabilmente hai ragione dicendo che il max abbia un peso trascurabile
visto che il tutto è i/o bound, ma l'occupazione di memoria mi sembra poco
controllata. Se puoi accennarmi in codice quello che vuoi fare forse
capisco meglio.


>> Come caso pessimo la tua ricetta ha quello delle frequenze simili, La
mia
>> ha il caso in cui in ogni blocco di record letti (es. 1 milione) ogni
>> record vada in un file distinto (es. 999 record in 999 file, tutti gli
>> altri in uno solo). Il mio caso pessimo mi sembra più improbabile :)
> 
> Il mio caso pessimo l'ho descritto sopra, e mi sembra si comporti molto
> meglio del tuo.
> 
> Parlare di probabilità dei casi pessimi non ha molto senso, se non la si
> mette in rapporto con il costo degli stessi. Più in generale: posso
> giustificare i ragionamenti al caso pessimo e quelli sulla media, ma a
> parte questi due tipi di analisi non mi sembra si possa concludere
> granché di sensato senza sapere qualcosa della struttura dei dati veri e
> propri.

Il caso pessimo di quest'algoritmo è un caso patologico, in cui ogni 1e6
record ce ne sono 999 appartenenti ad altrettanti classi distinte e 999001
appartenenti ad una singola. Il fatto che questa distribuzione sia
estremamente improbabile non è un fatto trascurabile ma una considerazione
che può essere sfruttata, come considerare che è così improbabile trovare
due stringhe con lo stesso sha1 che si può considerare questo hash univoco
(considerazione ad esempio sulla quale si basa git). Tra l'altro nota che
anche nel caso pessimo verrebbero effettuate lo stesso numero di scritture
(1000 ogni milione di record).

Ora che ho scritto il mio algoritmo, vedo che non è neanche difficile dire
"se ci sono pochi record in un file, aspetta prima di scrivere": è
sufficiente modificare write_files() con:

def write_files(parts, nmin)
    # questo consuma il dizionario
    for filename, records in parts.items():
        if len(records) >= nmin:
            open(filename, 'a').write(
                ''.join(records))
            del parts[filename]

e richiamare qualcosa come write_files(parts, 10) nel loop e
write_files(parts, 0) alla fine. Questa potrebbe essere una guardia contro
casi patologici, ma non credo sia qualcosa di significativo su input
normali.


-- 
Daniele Varrazzo - Develer S.r.l. 
http://www.develer.com