Come leggere la seconda colonna in un file di grandi dimensioni

Question

Ho un file enorme con milioni di colonne, splited dallo spazio, ma ha solo un numero limitato di righe:

examples.txt:

1 2 3 4 5 ........ 
3 1 2 3 5 ......... 
l 6 3 2 2 ........ 

Ora, voglio solo leggere nella seconda colonna:

2 
1 
6 

Come faccio a fare questo in Java ad alte prestazioni.

Grazie

Aggiornamento: il file è di solito 1.4G contenente centinaia di righe.

Answer 1

Se il file non è strutturato staticamente, l'unica opzione è quella ingenua: leggere la sequenza di byte del file per sequenza di byte alla ricerca di nuove righe e afferrare la seconda colonna dopo ciascuna. Utilizzare FileReader.

Se il file è stato strutturato in modo statico, è possibile calcolare la posizione del file nella seconda colonna per una determinata riga e seek() direttamente.

Answer 2

Ecco una piccola macchina a stati che utilizza un FileInputStream come input e gestisce il proprio buffer. Non ci sono conversioni locali.

Sul mio portatile di 1,4 GHz di 7 anni con 1/2 Gb di memoria ci vogliono 48 secondi per passare 1,28 miliardi di byte di dati. I buffer più grandi di 4Kb sembrano funzionare più lentamente.

Su un nuovo MacBook di 1 anno con 4 GB, viene eseguito in 14 secondi. Dopo che il file è nella cache, viene eseguito in 2,7 secondi. Ancora una volta non c'è differenza con i buffer più grandi di 4Kb. Questo è lo stesso file di dati di 1,2 miliardi di byte.

Prevedo che l'I/O mappato in memoria farebbe meglio, ma probabilmente è più portabile.

Verrà recuperata qualsiasi colonna a cui viene indicata.

import java.io.*; 
import java.util.Random; 

public class Test { 

public static class ColumnReader { 

    private final InputStream is; 
    private final int colIndex; 
    private final byte [] buf; 
    private int nBytes = 0; 
    private int colVal = -1; 
    private int bufPos = 0; 

    public ColumnReader(InputStream is, int colIndex, int bufSize) { 
     this.is = is; 
     this.colIndex = colIndex; 
     this.buf = new byte [bufSize]; 
    } 

    /** 
    * States for a tiny DFA to recognize columns. 
    */ 
    private static final int START = 0; 
    private static final int IN_ANY_COL = 1; 
    private static final int IN_THE_COL = 2; 
    private static final int WASTE_REST = 3; 

    /** 
    * Return value of colIndex'th column or -1 if none is found. 
    * 
    * @return value of column or -1 if none found. 
    */ 
    public int getNext() { 
     colVal = -1; 
     bufPos = parseLine(bufPos); 
     return colVal; 
    } 

    /** 
    * If getNext() returns -1, this can be used to check if 
    * we're at the end of file. 
    * 
    * Otherwise the column did not exist. 
    * 
    * @return end of file indication 
    */ 
    public boolean atEoF() { 
     return nBytes == -1; 
    } 

    /** 
    * Parse a line. 
    * The buffer is automatically refilled if p reaches the end. 
    * This uses a standard DFA pattern. 
    * 
    * @param p position of line start in buffer 
    * @return position of next unread character in buffer 
    */ 
    private int parseLine(int p) { 
     colVal = -1; 
     int iCol = -1; 
     int state = START; 
     for (;;) { 
      if (p == nBytes) { 
       try { 
        nBytes = is.read(buf); 
       } catch (IOException ex) { 
        nBytes = -1; 
       } 
       if (nBytes == -1) { 
        return -1; 
       } 
       p = 0; 
      } 
      byte ch = buf[p++]; 
      if (ch == '\n') { 
       return p; 
      } 
      switch (state) { 
       case START: 
        if ('0' <= ch && ch <= '9') { 
         if (++iCol == colIndex) { 
          state = IN_THE_COL; 
          colVal = ch - '0'; 
         } 
         else { 
          state = IN_ANY_COL; 
         } 
        } 
        break; 

       case IN_THE_COL: 
        if ('0' <= ch && ch <= '9') { 
         colVal = 10 * colVal + (ch - '0'); 
        } 
        else { 
         state = WASTE_REST; 
        } 
        break; 

       case IN_ANY_COL: 
        if (ch < '0' || ch > '9') { 
         state = START; 
        } 
        break; 

       case WASTE_REST: 
        break; 
      } 
     } 
    } 
} 

public static void main(String[] args) { 
    final String fn = "data.txt"; 
    if (args.length > 0 && args[0].equals("--create-data")) { 
     PrintWriter pw; 
     try { 
      pw = new PrintWriter(fn); 
     } catch (FileNotFoundException ex) { 
      System.err.println(ex.getMessage()); 
      return; 
     } 
     Random gen = new Random(); 
     for (int row = 0; row < 100; row++) { 
      int rowLen = 4 * 1024 * 1024 + gen.nextInt(10000); 
      for (int col = 0; col < rowLen; col++) { 
       pw.print(gen.nextInt(32)); 
       pw.print((col < rowLen - 1) ? ' ' : '\n'); 
      } 
     } 
     pw.close(); 
    } 

    FileInputStream fis; 
    try { 
     fis = new FileInputStream(fn); 
    } catch (FileNotFoundException ex) { 
     System.err.println(ex.getMessage()); 
     return; 
    } 
    ColumnReader cr = new ColumnReader(fis, 1, 4 * 1024); 
    int val; 
    long start = System.currentTimeMillis(); 
    while ((val = cr.getNext()) != -1) { 
     System.out.print('.'); 
    } 
    long stop = System.currentTimeMillis(); 
    System.out.println("\nelapsed = " + (stop - start)/1000.0); 
} 
} 

Answer 3

devo concordare con @gene, provare con un BufferedReader e GetLine primo luogo, è semplice e facile da codice. Basta fare attenzione a non creare alias l'array di supporto tra il risultato di getLine e qualsiasi operazione di sottostringa che si utilizza. String.substring() è un colpevole particolarmente comune, e ho avuto array di byte multi-MB bloccati in memoria perché una sottostringa a 3 caratteri stava facendo riferimento a esso.

Assumendo ASCII, la mia preferenza quando si esegue questa operazione è di scendere al livello di byte. Utilizzare mmap per visualizzare il file come ByteBuffer e quindi eseguire una scansione lineare per 0x20 e 0x0A (presupponendo separatori di riga in stile unix). Quindi converti i byte rilevanti in una stringa. Se si utilizza un set di caratteri a 8 bit è estremamente difficile essere più veloce di questo.

Se si utilizza Unicode, il problema è sufficientemente più complicato che consiglio vivamente di utilizzare BufferedReader a meno che le prestazioni non siano effettivamente accettabili. Se getLine() non funziona, prendi in considerazione semplicemente il loop su una chiamata a read().

Indipendentemente da quando si inizializza una stringa da un puntatore esterno, è necessario specificare sempre il set di caratteri. Questo documenta esplicitamente la tua assunzione di caratteri.Quindi raccomando una piccola modifica al suggerimento del gene, quindi uno di:

int i = Integer.parseInt(new String(buffer, start, length, "US-ASCII")); 

int i = Integer.parseInt(new String(buffer, start, length, "ISO-8859-1")); 

int i = Integer.parseInt(new String(buffer, start, length, "UTF-8")); 

come appropriato.