modo più efficace per analizzare ogni quarta riga da un file molto grande

Question

Ho un file con il seguente formato:

1: some_basic_info_in_this_line 
2: LOTS_OF_INFO_IN_THIS_LINE_HUNDREDS_OF_CHARS 
3: some_basic_info_in_this_line 
4: LOTS_OF_INFO_IN_THIS_LINE_HUNDREDS_OF_CHARS 
... 

che il formato si ripete decine di migliaia di volte, rendendo i file fino a 50 GB +. Ho bisogno di un modo efficiente per elaborare l'unica linea 2 di questo formato. Sono aperto all'utilizzo di C, C++ 11 STL o boost. Ho esaminato varie altre domande riguardanti lo streaming di file su SO, ma mi sento come se la mia situazione fosse unica a causa delle grandi dimensioni del file e richiedendone solo una su ogni quattro righe.

La mappatura della memoria del file sembra essere la più efficiente da ciò che ho letto, ma mappare un file di 50+ GB si esaurirà nella maggior parte dei computer RAM (si può presumere che questa applicazione verrà utilizzata da utenti "medi" - dire 4-8 GB RAM). Inoltre ho solo bisogno di elaborare una delle linee alla volta. Ecco come Attualmente sto facendo questo (sì sono consapevole che non è efficiente, è per questo che sto ridisegnare esso):

std::string GL::getRead(ifstream& input) 
{ 
    std::string str; 
    std::string toss; 
    if (input.good()) 
    { 
     getline(input, toss); 
     getline(input, str); 
     getline(input, toss); 
     getline(input, toss); 
    } 
    return str; 
} 

sta rompendo la mmap in blocchi la risposta per la mia situazione? C'è comunque che io possa sfruttare solo il bisogno di 1 su 4 linee? Grazie per l'aiuto.

Answer 1

Questa è la soluzione più efficiente che potrei ottenere che sia indipendente dalla piattaforma. Ho pensato a tutti gli utenti, e per ora sto girando nel presupposto che tutti abbiano una macchina a 64 bit se usano dimensioni di file 4+ GiB. Se questo cambia, dovrò modificare la classe per gestire "blocchi" di dati in regioni separate mmap.

#include <string> 
#include <boost/iostreams/device/mapped_file.hpp> 

////////////////////////////////////////////////////////////////////////////////////////// 
/// @class LineParser 
/// 
/// @brief Class to efficiently parse a file and take the second line out of every 4 lines 
/// 
/// This class uses memory-mapped io to efficiently extract and return sequences from a 
/// file 
////////////////////////////////////////////////////////////////////////////////////////// 
class LineParser 
{ 
private: 
    boost::iostreams::mapped_file mmap; ///< Object for memory mapped file 
    const char* curr;     ///< Current position of the file 
    const char* end;     ///< End position of the file 

public: 
    ////////////////////////////////////////////////////////////////////////////////////// 
    /// @fn valid 
    /// 
    /// Indicates whether the parser is in a valid state or not 
    /// 
    /// @return Boolean indicating if the parser is open and in a valid state 
    /// 
    /// @note Declared inline as it is acceptable in my situation because of being called 
    ///  many times in only a few spots  
    ////////////////////////////////////////////////////////////////////////////////////// 
    inline bool valid(void) 
    { 
     return (curr && end && (curr < end) && (mmap.is_open())); 
    } 

    ////////////////////////////////////////////////////////////////////////////////////// 
    /// @fn peek 
    /// 
    /// Obtains the next sequence string - if it exists - but maintains parsers state 
    /// 
    /// @return Next sequence available in the file. Emptry string returned if none 
    ///   exist 
    /// 
    /// @note Declared inline as it is acceptable in my situation because of being called 
    ///  many times in only a few spots 
    ////////////////////////////////////////////////////////////////////////////////////// 
    inline std::string peek(void) 
    { 
     const char* save = curr; 
     std::string ret; 

     getRead(ret); 

     curr = save; 
     return ret; 
    } 

    ////////////////////////////////////////////////////////////////////////////////////// 
    /// @fn getRead 
    /// 
    /// Sets container to the current read being processed 
    /// 
    /// @param container String container to place current sequence into 
    /// 
    /// @return Boolean indicating if getting a new read was successful 
    /// 
    /// @note Declared inline as it is acceptable in my situation because of being called 
    ///  many times in only a few spots 
    ////////////////////////////////////////////////////////////////////////////////////// 
    inline bool getRead(std::string& container) 
    { 
     if (valid() == false) 
     { 
      return false; 
     } 

     curr = static_cast<const char*>(memchr(curr, '\n', end-curr)) + 1; 
     const char* index = static_cast<const char*>(memchr(curr, '\n', end-curr)); 
     container = std::string(curr, index - curr); 
     curr = index + 1; 
     curr = static_cast<const char*>(memchr(curr, '\n', end-curr)) + 1; 
     curr = static_cast<const char*>(memchr(curr, '\n', end-curr)) + 1; 

     return true; 
    } 

    ////////////////////////////////////////////////////////////////////////////////////// 
    /// @fn LineParser 
    /// 
    /// Constructor to initialize memory mapped file and set index values 
    ////////////////////////////////////////////////////////////////////////////////////// 
    LineParser(const std::string& filepath) 
     : mmap(filepath, boost::iostreams::mapped_file::readonly) 
    { 
     if (mmap.is_open()) 
     { 
      curr = mmap.const_data(); 
      end = curr + mmap.size(); 
     } 
    } 

    ////////////////////////////////////////////////////////////////////////////////////// 
    /// @fn ~LineParser 
    /// 
    /// Default destructor 
    ////////////////////////////////////////////////////////////////////////////////////// 
    ~LineParser(void) = default; 
}; 

Si prega di notare che questa classe non è perfetto e non potrebbe gestire le deviazioni in formato di file molto bene, ma sotto l'ipotesi di formato di file perfetto funziona bene.

Answer 2

Uso ignore invece di getline:

std::string GL::getRead(ifstream& input) 
{ 
    std::string str; 
    if (!input.fail()) 
    { 
     input.ignore(LARGE_NUMBER, '\n'); 
     getline(input, str); 
     input.ignore(LARGE_NUMBER, '\n'); 
     input.ignore(LARGE_NUMBER, '\n'); 
    } 
    return str; 
} 

LARGE_NUMBER potrebbe essere std::numeric_limits<std::streamsize>::max() se non si dispone di una buona ragione per avere un numero minore (si pensi attacchi DOS)

TIP Considerare il passaggio str come riferimento. Leggendo nella stessa stringa ogni volta, è possibile evitare molte allocazioni, che sono in genere il numero 1 del motivo per cui il programma viene eseguito lentamente.

TIP è consigliabile utilizzare un file di memoery mappato (Boost iostreams, Boost Interpocess, o mmap(1))

Answer 3

Memory-mapping di un file non viene caricato in RAM. Occupa lo spazio degli indirizzi virtuali per il processo, ma non la RAM fisica. La chiamata di sistema mmap fallirà semplicemente su un sistema a 32 bit, perché 4GiB di spazio di indirizzamento virtuale non è sufficiente per un file 50GiB. Su un sistema a 64 bit, ci vorranno microsecondi. (Nessun disco letto, perché il file è già aperto quindi i metadati del file sono già caricati.)

Solo le pagine effettivamente lette vengono caricate dal disco e le pagine possono essere nuovamente non mappate ogni volta che il sistema operativo desidera recuperare memoria . (Perché se li leggi di nuovo più tardi, il sistema operativo può ricaricare dal disco. È come scambiarli per scambiare spazio/pagefile, ma senza dover scrivere perché c'è già una copia pulita sul disco.)

Una mappatura della memoria lascia il tuo processo legge le pagine della cache della pagina del SO, invece di farne una copia con una chiamata di sistema read.

Have a look at wikipedia per ulteriori informazioni.