C++: быстрый способ чтения сопоставленного файла в матрицу

Question

Я пытаюсь прочитать сопоставленный файл в матрицу. Файл примерно такой:

name;phone;city\n
Luigi Rossi;02341567;Milan\n
Mario Bianchi;06567890;Rome\n
.... 

и это тихо большой. Код, который я написал, работает правильно, но не так быстро:

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

using namespace std;

int main() {

    int i;
    int j=0;
    int k=0;

    vector< vector<char> > M(10000000, vector<string>(3));

    mapped_file_source file("file.csv");

    // Check if file was successfully opened
    if(file.is_open()) {

      // Get pointer to the data
      const char * c = (const char *)file.data();

      int size=file.size();

      for(i = 0; i < (size+1); i++){

       if(c[i]=='\n' || i==size){
        j=j+1;
        k=0;
       }else if(c[i]==';'){
        k=k+1;
       }else{
        M[j][k]+=c[i];
       }    
     }//end for


   }//end if    

 return(0)


}

Есть ли более быстрый способ? Я читал кое-что о memcyp, но я не знаю, как использовать его для ускорения моего кода.

Answer 1

У меня есть множество примеров, делающих это / подобное написанное на SO.

Позвольте мне перечислить наиболее актуальные:

• Я сделал довольно много из этих тестов. Да, для последовательного фрединга read/scanf имеют крошечную грань (см., Например, scanf / iostreams и файлы по сравнению с сопоставлениями и синтаксическим анализом, или чтение немного быстрее для последовательного чтения в 1 проход).

• Интересный подход состоит в том, чтобы выполнять ленивый анализ (зачем копировать весь ввод в память? Тогда какой смысл отображать память). Ответ здесь показывает этот подход (эмуляция мультикарты там):

  • Использование boost::iostreams::mapped_file_source с std:: multimap (подход #2)

Во всех других случаях подумайте над тем, чтобы выполнить на нем задание Spirit Qi, потенциально используя boost::string_ref вместо vector<char> (конечно, если сопоставленный файл не является "const").

string_ref также отображается в последнем ответе, связанном ранее. Другой интересный пример этого (с ленивым преобразованием в неэкранированные строковые значения) приведен здесь. Как правильно проанализировать усы с Boost.Xpressive?

DEMO

Вот та работа Ци, на которую обрушились:

• он разбирает файл размером 994 МБ с ~32 миллионами строк за 2,9 с в вектор

  struct Line {
      boost::string_ref name, city;
      long id;
  };
  

• обратите внимание, что мы анализируем число и сохраняем строки, ссылаясь на их расположение в карте памяти + длина (string_ref)

• он красиво печатает данные из 10 случайных строк
• он может работать со скоростью 2,5 с, если вы резервируете 32 м элементов в векторе одновременно; в этом случае программа выполняет только одно выделение памяти.
• ПРИМЕЧАНИЕ: в 64-битной системе представление памяти увеличивается больше, чем размер ввода, если средняя длина строки составляет менее 40 байтов. Это потому что string_ref 16 байтов.

Жить на Колиру

#include <boost/fusion/adapted/struct.hpp>
#include <boost/spirit/include/qi.hpp>
#include <boost/iostreams/device/mapped_file.hpp>
#include <boost/utility/string_ref.hpp>

namespace qi = boost::spirit::qi;
using sref   = boost::string_ref;

namespace boost { namespace spirit { namespace traits {
    template <typename It>
    struct assign_to_attribute_from_iterators<sref, It, void> {
        static void call(It f, It l, sref& attr) { attr = { f, size_t(std::distance(f,l)) }; }
    };
} } }

struct Line {
    sref name, city;
    long id;
};

BOOST_FUSION_ADAPT_STRUCT(Line, (sref,name)(long,id)(sref,city))

int main() {
    boost::iostreams::mapped_file_source mmap("input.txt");

    using namespace qi;

    std::vector<Line> parsed;
    parsed.reserve(32000000);
    if (phrase_parse(mmap.begin(), mmap.end(), 
                omit[+graph] >> eol >>
                (raw[*~char_(";\r\n")] >> ';' >> long_ >> ';' >> raw[*~char_(";\r\n")]) % eol,
                qi::blank, parsed))
    {
        std::cout << "Parsed " << parsed.size() << " lines\n";
    } else {
        std::cout << "Failed after " << parsed.size() << " lines\n";
    }

    std::cout << "Printing 10 random items:\n";
    for(int i=0; i<10; ++i) {
        auto& line = parsed[rand() % parsed.size()];
        std::cout << "city: '" << line.city << "', id: " << line.id << ", name: '" << line.name << "'\n";
    }
}

С входом генерируется как

do grep -v "'" /etc/dictionaries-common/words | sort -R | xargs -d\\n -n 3 | while read a b c; do echo "$a $b;$RANDOM;$c"; done

Выход, например,

Parsed 31609499 lines
Printing 10 random items:
city: 'opted', id: 14614, name: 'baronets theosophy'
city: 'denominated', id: 24260, name: 'insignia ophthalmic'
city: 'mademoiselles', id: 10791, name: 'smelter orienting'
city: 'ducked', id: 32155, name: 'encircled flippantly'
city: 'garotte', id: 3080, name: 'keeling South'
city: 'emirs', id: 14511, name: 'Aztecs vindicators'
city: 'characteristically', id: 5473, name: 'constancy Troy'
city: 'savvy', id: 3921, name: 'deafer terrifically'
city: 'misfitted', id: 14617, name: 'Eliot chambray'
city: 'faceless', id: 24481, name: 'shade forwent'