c++ - 如何使用 Boost 内存映射在 C++ 中解析 CSV？

Question

我有一个非常大的文件，里面有 1700 万条记录。

这是文件的示例:

Actor Movie
1,2
2,2
3,1
4,3
2,3

我想跳过第一行并从第二行开始解析。我正在尝试创造两件事。
1.电影到 Actor 的映射
vector<uint64_t> *movie_map = new vector<uint64_t>[1200000];
2. Actor 到电影的映射
vector<uint64_t> *actor_movie_map = new vector<uint64_t>[2000000];

我故意不想要 HashMap，因为计算哈希需要一些时间。我尝试使用 Boost 库。它在大约 3 秒内读取文件(~250MB)，但在创建 map 时消耗了大量时间。事实上时间比正常情况更糟getline()读取文件的方式。到目前为止，这是我的实现。

using CsvField = boost::string_ref;
using CsvLine  = std::vector<CsvField>;
using CsvFile  = std::vector<CsvLine>;

namespace qi = boost::spirit::qi;
struct CsvParser : qi::grammar<char const*, CsvFile()> {
    CsvParser() : CsvParser::base_type(lines)
    {
        using boost::phoenix::construct;
        using boost::phoenix::begin;
        using boost::phoenix::size;

        using namespace qi;

        field = raw [*~char_(",\r\n")] [ _val = construct<CsvField>(begin(_1), size(_1)) ];
        line  = field % ',';
        lines = line  % eol;
    }
  private:
    qi::rule<char const*, CsvField()> field;
    qi::rule<char const*, CsvLine()>  line;
    qi::rule<char const*, CsvFile()>  lines;
};

int main()
{
    srand(time(0));
    boost::iostreams::mapped_file_source csv("playedin.csv");

    CsvFile parsed;
    parsed.reserve(18*1000*1000);
    if (qi::parse(csv.data(), csv.data() + csv.size(), CsvParser(), parsed))
    {
        using boost::lexical_cast;
        for(uint64_t i=1; i < parsed.size(); i++){
        auto& line = parsed[i];
        uint64_t sample = lexical_cast<uint64_t>(line[0]);
        movie_map[lexical_cast<uint64_t>(line[1])].push_back(lexical_cast<uint64_t>(line[0]));
        actor_movie_map[lexical_cast<uint64_t>(line[0])].push_back(lexical_cast<uint64_t>(line[1]));

        }
    }
}

由于文件很大，我不想使用正常的方式读取文件。请提出一种实现此方法的方法，以便在不到 2-3 秒的时间内完成读取和准备 1700 万条记录的整个文件。我知道期望有点高，但我相信这是可能的。我真的在寻找最有效的方法。

感谢您的帮助!

Answer 1

• vector *movie_map = new vector[1200000];

  ✍ 永远不要使用 new或 delete在现代 C++ 中

• I purposefully did not want a HashMap since it takes some time for computing hash.

  计算哈希值到底需要多少时间？我的意思是，散列图很可能不是这里的最佳选择，但您的推理是错误的。关于可能的实现 std::hash<> 64 位整数的 是空操作(在 size_t 是 64 位的系统上)¹。

但关键在于:

您...将所有数据读入 CsvFile首先(这是 string_refs 的 vector 的 vector ...)只是为了然后转换为 map ？!

这太荒谬了。简单地跳过中间人，你不需要它!

请注意，spirit 是一个解析器生成器。首先解析文本，只使用 lexical_cast 在各个方面都是荒谬的关于结果。

演示

这里有一个 c++14 演示，它使用 Boost Spirit X3 作为很好的衡量标准，减少了中间人。我选择了flat_multimap有点随机地提出两点:

• 你的数据结构“像一个” multimap ，甚至可能是一个邻接表。您的用例需要它做什么？
• 有(许多)现有的数据结构具有微妙不同的性能特征

Live On Coliru

#include <boost/container/flat_map.hpp>
#include <boost/fusion/adapted/std_pair.hpp>
#include <boost/iostreams/device/mapped_file.hpp>
#include <boost/spirit/home/x3.hpp>

using Table  = boost::container::flat_multimap<uint64_t, uint64_t>;
using Record = Table::value_type;

namespace Parsing {
    using namespace boost::spirit::x3;

    auto const ignore_header_row 
        = !uint_ >> *(char_ - eol) >> eol;

    auto const record 
        = rule<struct _rl, Record> {"record"}
        = uint_ >> ',' >> uint_ >> eol;

    auto const file 
     // = rule<struct _file, Table> {"file"}
        = omit [*ignore_header_row] >> *record >> eoi;
}

#include <iostream>

int main() {
    boost::iostreams::mapped_file_source mfs("playedin.csv");

    Table table;
    table.reserve(18*1000*1000);
    if (parse(mfs.begin(), mfs.end(), Parsing::file, table)) {
        std::cout << "Parsed " << table.size() << " records\n";
    } else {
        std::cout << "Parse failed\n";
    }
}

打印

Parsed 5 records

Caveat In latest boost versions there is a regression in X3 attribute handling, you will want to use the fix from this answer: https://stackoverflow.com/a/48393573/85371

基准测试+查询

基准测试可预见地表明，插入 17+ 百万未排序的行并不是最优的 using the flat-map approach :

• 在 ~4 分钟 39 秒内读取了 1,000,000 个未排序的行，
• 输入排序后，读取相同的行只需要 0.113 秒 output screenshot

明显的瓶颈是解析时的排序。这很容易解决:我们不需要在解析时进行排序。就sort it after parsing :

• 所有 1740 万行现在都在 1.922 秒内解析和排序，如果预排序则为 1.284 秒(再次为 output screenshot)

基准代码 list

最终版本 Live On Coliru

#include <boost/container/flat_map.hpp>
#include <boost/fusion/adapted/std_pair.hpp>
#include <boost/iostreams/device/mapped_file.hpp>
#include <boost/spirit/home/qi.hpp>

using Table  = boost::container::vector<std::pair<uint64_t, uint64_t> >;
using Record = Table::value_type;

namespace Parsing {
    using namespace boost::spirit::qi;
    using Iterator = char const*;

    static const rule<Iterator> ignore_header_row
        = !uint_ >> *(char_ - eol) >> eol;
    static const rule<Iterator, Record()> record 
        = uint_ >> ',' >> uint_ >> eol;

    static const rule<Iterator, Table()> file 
        = omit [*ignore_header_row] >> *record >> eoi;
}

Table parse_data(std::string const& fname) {
    boost::iostreams::mapped_file_source mfs(fname);

    Table table;
    table.reserve(18*1000*1000);
    if (!parse(mfs.begin(), mfs.end(), Parsing::file, table))
        throw std::runtime_error("Parse failed");

    sort(table.begin(), table.end());
    return table;
}

template <typename It> struct iterator_range {
    It b, e;
    iterator_range() = default;
    iterator_range(std::pair<It, It> p) : b(p.first), e(p.second) {}
    It begin() const { return b; }
    It end() const   { return e; }
};

struct by_actor {
    template <typename T, typename U>
    bool operator()(T const& a, U const& b) const { return actor(a) < actor(b); }
  private:
    static uint64_t actor(Record const& r) { return r.first; }
    static uint64_t actor(uint64_t i) { return i; }
};

#include <iostream>

int main(int argc, char** argv) {
    Table const& table = parse_data("playedin.csv");

    auto query = [&table](uint64_t actor) { 
        return iterator_range<Table::const_iterator>(equal_range(table.begin(), table.end(), actor, by_actor{}));
    };

    for (auto actor : std::vector<std::string>{argv+1, argv+argc}) {
        std::cout << "Actor " << actor << " played in:";
        for (auto movie : query(std::stoull(actor)))
            std::cout << " " << movie.second;
        std::cout << "\n";
    }
}

---

¹ 同样，boost 的 boost::hash<>遵从 boost::hash_value(unsigned long long)据记录返回 val when abs(val) <= std::numeric_limits<std::size_t>::max() .