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 <too...@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 <too...@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 _______________________________________________ Python mailing list Python@lists.python.it http://lists.python.it/mailman/listinfo/python