[Python] split di file di grandi dimensioni

[Pietro Battiston]

Il giorno ven, 04/12/2009 alle 23.49 +0100, Daniele Varrazzo ha scritto:
> 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?

Prima di sprecare (potenzialmente) parole, lo faccio. Poi se c'è
qualcosa che non è chiaro, chiarirò:


def estrai_target(linea):
    # deduci dalla linea in che file deve andare
    ...

def estrai_contenuto(linea):
    # deduci dalla linea cosa va scritto nel file
    ...


class Lettore():
    def __init__(self):
        self.contatore_linee = 0
        self.diz = {}

        file_in = open(file_in)

        while True:
            linea = file_in.readline()
            if linea:
                self.processa_linea(linea)
            else:
                break

        # Finito di parsare il file, facciamo un flush
        for target in self.diz:
            self.scrivi_su_file_e_svuota_lista(target)

        # Finito

    def processa_linea(linea):
       contenuto = estrai_contenuto(linea)
       target = estrai_target(linea)

       if not target in self.diz:
           self.diz[target] = []

       self.diz[target].append(contenuto)
       
       self.contatore_linee += 1

       if self.contatore_linee > MEMORIA_MAX:
           # Si arriva qui al più N_RIGHE * (N_FILE/MEMORIA_MAX) volte
           # (dignitoso purché N_FILE**2 <= MEMORIA_MAX, dato che
           #  le righe seguenti hanno costo grosso modo N_FILE)
           popolarità_massima = 0
           for un_target, sua_lista in zip(self.diz, self.diz.values):
               popolarità = len(sua_lista)
               if popolarità > popolarità_massima:
                   il_più_popolare = un_target
                   popolarità_massima = popolarità

           self.scrivi_su_file_e_svuota_lista(il_più_popolare)       

           self.contatore_linee -= popolarità_massima


# Ovviamente la parte dopo il test con MEMORIA_MAX si può un po'
ottimizzare.

> 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":

Probabilmente con questa aggiunta i nostri metodi si somigliano molto.

ciao

Pietro