Reduce time to read files and analyze datas

angeloulivieri

Utente Attivo
8 Set 2009
71
0
0
Hi all,
as I write in the title I want to change the code of an application I built in Java.
The software consists in reading some files organized in table and
for each row
for each column
if you find A(row,col)==1 then
find if in this column there are other 1

If the matrix is NxM the complexity is O(Nx(M^2)). The problem is that M=some thousand and N=400 elements.
When I wrote this in java I used a TextFile Reader to get the text:

for (int index=0;index<files.size();index++){
TextFileReader reader=new TextFileReader(files.get(index).getAbsolutePath());
reader.read();
fullText[index]=reader.getText();
}

Then I split all file in lines and all lines in tokens, like this:
String[] lines = fullText[indFile].split("\n"); // split whole file into lines
String[] tokens = lines[2].split("\t");
The I visit all the tokens once a time.

Maybe I don't know so well Java language but it seems that using this code the process is very very slow and I would that the execution is approximately real time.
Is there someone that can tell me what approach is better to use....?
How can I do it with threads? Is this better?
Thanks to all
Angelo
 

angeloulivieri

Utente Attivo
8 Set 2009
71
0
0
ahah! hai ragione..
talmente abituato a scrivere sui forum in inglese che non ci ho fatto proprio caso.
Comunque il problema è la lettura file da excel e la memorizzazione. Cioé che tipo di strutture permette di usare Java?
Queste che ho usato sono troppo lente per l'accesso...
 

programmatore

Utente Attivo
21 Ago 2009
111
0
0
programmatore.altervista.org
Codice:
for (int index=0;index<files.size();index++){
TextFileReader reader=new TextFileReader(files.get(index).getAbsolutePath()) ;
reader.read();
fullText[index]=reader.getText();
}

Then I split all file in lines and all lines in tokens, like this:
String[] lines = fullText[indFile].split("\n"); // split whole file into lines 
String[] tokens = lines[2].split("\t"); 
The I visit all the tokens once a time.
Primo ciclo N*M accessi, molto meglio leggere in un vettore di char l'intero contenuto del file con una sola istruzione senza fidarsi troppo dell'uso della cache.
Con la seconda coppia di istruzioni esamini il contenuto del file per 2 volte.

Dopo aver un vettore con tutto il contenuto del file, man mano che lo leggi tutto, ti aggiorni le coordinate row e col se trovi 1,0,\n o \t. Ti conviene creare un array dove per indice hai la colonna e il numero di 1 trovati, inizialmente tutto a 0.
Es. trovo il primo 1 in posizione A(row,col), quindi faccio colonna[col]++; (partono tutte da 0)
trovo un altro 1 in posizione A(row2,col2) => colonna[col2]++;

Quando hai finito l'esame di A hai in un vettore la risposta: le colonne con più di un 1 sono quelle tali che colonna[col2]>1.
Complessità O(N*M+M), pari anche al numero di confronti.
Se il file fosse stato binario si poteva fare un po' meglio anche più di un fattore 64, se proprio fosse stato qualcosa di importante da velocizzare ^_^
 

angeloulivieri

Utente Attivo
8 Set 2009
71
0
0
Primo ciclo N*M accessi, molto meglio leggere in un vettore di char l'intero contenuto del file con una sola istruzione senza fidarsi troppo dell'uso della cache.
Con la seconda coppia di istruzioni esamini il contenuto del file per 2 volte.

Intendi quando faccio lo split?

Dopo aver un vettore con tutto il contenuto del file, man mano che lo leggi tutto, ti aggiorni le coordinate row e col se trovi 1,0,\n o \t. Ti conviene creare un array dove per indice hai la colonna e il numero di 1 trovati, inizialmente tutto a 0.
Es. trovo il primo 1 in posizione A(row,col), quindi faccio colonna[col]++; (partono tutte da 0)
trovo un altro 1 in posizione A(row2,col2) => colonna[col2]++;

Quando hai finito l'esame di A hai in un vettore la risposta: le colonne con più di un 1 sono quelle tali che colonna[col2]>1.

Io purtroppo il file lo leggo solo una volta... dunque tenere il conto degli 1 non mi serve a tanto. L'obiettivo finale non è quello di sapere quanti uno ci sono ma conservare il nome della riga in cui si trova l'uno. (Questo non l'ho detto prima in inglese!)

Complessità O(N*M+M), pari anche al numero di confronti.
Se il file fosse stato binario si poteva fare un po' meglio anche più di un fattore 64, se proprio fosse stato qualcosa di importante da velocizzare ^_^

Il file è fatto che la prima riga ci sono scritti i nomi delle colonne e la prima colonna i nomi delle righe.
Tutto il resto è binario (0 oppure 1)


Il punto è... esiste un metodo alternativo a questo usato da me per conservare i dati presi da un file tabellare e che consenta di velocizzare il tutto? Gli array multidimensionali forse? Magari memorizzando prima tutto in un array di interi (int[][])?
 

programmatore

Utente Attivo
21 Ago 2009
111
0
0
programmatore.altervista.org
Primo ciclo N*M accessi, molto meglio leggere in un vettore di char l'intero contenuto del file con una sola istruzione senza fidarsi troppo dell'uso della cache.
Con la seconda coppia di istruzioni esamini il contenuto del file per 2 volte.

Intendi quando faccio lo split?
Sì: la prima lettura è con TextFileReader, la seconda è con lo split.
[...]
Io purtroppo il file lo leggo solo una volta... dunque tenere il conto degli 1 non mi serve a tanto. L'obiettivo finale non è quello di sapere quanti uno ci sono ma conservare il nome della riga in cui si trova l'uno. (Questo non l'ho detto prima in inglese!)
Se vuoi sapere il nome delle righe, userai il vettore riga[row] anziché colonna[col]. Anche se non ti serve sapere quanti sono gli 1, con questo metodo sai che avendo più di 1 uno nella riga (chiedevi di trovare un 1 e poi sapere se ce ne sono altri), hai automaticamente identificato la riga. Infatti se riga[10]=5, sai che ci sono cinque '1' nella riga 10. Quindi '10' fa parte del tuo risultato. Se riga[11]=0 e riga[12]=1 sai che rispettivamente hanno nessun '1' e un '1' quindi non fanno parte del tuo risultato.
Il file è fatto che la prima riga ci sono scritti i nomi delle colonne e la prima colonna i nomi delle righe.
Tutto il resto è binario (0 oppure 1)
Intendevo file binario nel senso che i codici ascii sono 0..255. Nel tuo caso hai un file di testo. Dovrai ovviamente saltare la prima riga e magari salvare il nome della riga per visualizzarla nel risultato (così anziché '10' come indice della riga, mostri 'nome_riga_10'). La complessità non cambia comunque con questa variazione.
Il punto è... esiste un metodo alternativo a questo usato da me per conservare i dati presi da un file tabellare e che consenta di velocizzare il tutto? Gli array multidimensionali forse? Magari memorizzando prima tutto in un array di interi (int[][])?
Se usi una matrice va bene lo stesso... probabilmente dovrai fare delle assunzioni sulle dimensioni delle matrici (a meno che Java non ti consenta di creare matrici dinamiche in entrambe le dimensioni).
Se però in un vettore conservi in ram il contenuto del file non hai bisogno di questa matrice che sarebbe una cosa in più e richiede del tempo (ok poco, ma > 0) per essere costruita, poi per essere analizzata. Ad ogni modo anche così avrai un notevole miglioramento delle prestazioni.

P.S.- Se ti serve sapere quali colonne hanno l'1 in ogni riga, si può fare una piccola aggiunta di costo O(1), quindi ininfluente in termini di complessità computazionale.
 

angeloulivieri

Utente Attivo
8 Set 2009
71
0
0
Se usi una matrice va bene lo stesso... probabilmente dovrai fare delle assunzioni sulle dimensioni delle matrici (a meno che Java non ti consenta di creare matrici dinamiche in entrambe le dimensioni).
Se però in un vettore conservi in ram il contenuto del file non hai bisogno di questa matrice che sarebbe una cosa in più e richiede del tempo (ok poco, ma > 0) per essere costruita, poi per essere analizzata. Ad ogni modo anche così avrai un notevole miglioramento delle prestazioni.
Ciao Programmatore... io penso che la tua soluzione sull'usare l'array che mi dice se nella colonna ci sono 1 o meno è abbastanza importante. Mi evita di scorrere le colonne "inutili" e questa cosa mi garba. :-D

Senti... ho tolto tutti gli split e ho fatto un gigantesco array tridimensionale per contenere questo marasma di dati. L'array statico l'ho inizializzato come:
String[] arrayF=new String[3][500][5000];
...ma mi da un pò troppi problemi...
Il mio caso semplice è costituito da 2 file (200x700) e fin qui il processo è velocizzato con gli array. Ma
nel caso più complesso ho 6 file 200x4000 e non mi apre proprio nulla. Mi da errore sull'allocazione dell'Heap (java.lang.OutOfMemoryError: Java heap space)
Ho anche cambiato la dimensione della memoria da usare con -Xmx512m ma in quel caso non mi da nemmeno l'errore e si blocca senza darmi nessuna spiegazione! Diamine!
 

programmatore

Utente Attivo
21 Ago 2009
111
0
0
programmatore.altervista.org
Ciao Programmatore... io penso che la tua soluzione sull'usare l'array che mi dice se nella colonna ci sono 1 o meno è abbastanza importante. Mi evita di scorrere le colonne "inutili" e questa cosa mi garba. :-D
E' per quello che insistevo anche se non ti serviva il conteggio ^_^
Senti... ho tolto tutti gli split e ho fatto un gigantesco array tridimensionale
Tridimensionale?! Poi di stringhe? Perché?
Io avrei usato una stringa sola (o array di byte) in maniera tale da avere il contenuto del file in ram e poter leggere un byte alla volta per sapere in che riga sei e di che colonna e cosa stai leggendo.
Se proprio vuoi puoi usare 2 dimensioni, in maniera tale che dai le coordinate di riga e colonna e sai il valore (ma non ti serve, al massimo ti può semplificare il sorgente, ma abbastanza poco e ti abbassa un po' le prestazioni).
In entrambi i casi, comunque se hai 500 righe e 1000 colonne avrai un array da 500x1000 byte (supponiamo che i nomi delle colonne e delle righe li salti o li metti in un vettore come dicevo sopra, per dare un nome di riga/colonna anziché un indice di vettore che potrebbe essere un po' criptico) oppure un array da 500.000 byte (sempre mezzo mega di ram usato).
Ovviamente gestendo un solo file per volta usi un vettore per tutti i file (eventualmente ridimensionato o, meglio, inizializzato una volta sola e dimensionato alla dim massima dei file che leggi per risparmiare tempo anche nell'allocazione/deallocazione per ogni file).