Наиболее эффективный способ разобрать каждую четвертую строку из очень большого файла

Question

У меня есть файл в следующем формате:

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 
... 

Этот формат повторяется десятки тысяч раз, что делает файлы до 50 GiB +. Мне нужен эффективный способ обработки только строки 2 этого формата. Я открыт для использования C, C++ 11 STL или boost. Я рассмотрел различные другие вопросы, касающиеся потоковой передачи файлов на SO, но я чувствую, что моя ситуация уникальна из-за большого размера файла и только одна из каждых четырех строк.

Память, сопоставляющая файл, кажется наиболее эффективной из того, что я читал, но отображение файла с более чем 50 ГБ будет потреблять большую часть ОЗУ компьютера (вы можете предположить, что это приложение будет использоваться «средними» пользователями - скажем, 4-8 ГБ ОЗУ). Также мне нужно будет только обрабатывать одну из строк за раз. Вот как я сейчас делаю это (да я знаю, что это не эффективно, поэтому я перепроектирование его):

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; 
} 

ломает ММАП в блоки ответа для моей ситуации? В любом случае, я могу использовать только 1 из 4 строк? Спасибо за помощь.

Answer 1

Это наиболее эффективное решение, которое я мог бы придумать, это независимая от платформы. Я подумал обо всех пользователях, и теперь я убежден, что каждый имеет 64-битную машину, если они используют размер файла 4+ GiB. Если это изменится, мне придется модифицировать класс для обработки «блоков» данных в отдельные области 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; 
}; 

Пожалуйста, обратите внимание, что этот класс не является совершенным и не может справиться с отклонениями в файловом формате очень хорошо, но в предположении идеального формата файла он работает хорошо.

Answer 2

Использование ignore вместо 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 может быть std::numeric_limits<std::streamsize>::max(), если у вас нет уважительной причины, чтобы иметь меньшее число (думаю атак DOS)

TIP Рассмотрите возможность передачи str по ссылке. Читая в одну строку каждый раз, вы можете избежать множества распределений, которые, как правило, являются причиной № 1, ваша программа работает медленно.

TIP Рассмотрите возможность использования memoery файла, отображенного (увеличить Iostreams, увеличить Interpocess или mmap(1))

Answer 3

отображения памяти файл не загружать его в оперативную память. Он занимает виртуальное адресное пространство для процесса, но не физическое ОЗУ. Системный вызов mmap просто завершится неудачей в 32-битной системе, потому что 4GiB виртуального адресного пространства недостаточно для файла 50GiB. В 64-битной системе это займет микросекунды. (Нет чтения диска, потому что файл уже открыт, так что метаданные файла уже загружены.)

Загружаются с диска только те страницы, на которых вы действительно читаете, и страницы могут быть снова отключены, когда ОС хочет восстановить некоторую память , (Потому что, если вы прочтете их позже, ОС может перезагрузиться с диска. Это походит на их замену для замены пространства/файла подкачки, но без необходимости писать, потому что на диске уже есть чистая копия.)

Отображение памяти позволяет ваш процесс читает страницы страницы-кеша ОС, а не делает их копии с системным вызовом read.

Have a look at wikipedia для получения дополнительной информации.