c++ - 使用 boost::spirit 解析任意精度整数

Question

我想为任意整数创建 boost::spirit::qi::grammar 。将整数存储到字符串只是感觉非常浪费内存，尤其是当整数以二进制格式表示时。如何在结构中使用任意精度整数类（例如 GMP 或 llvm::APInt）？

Answer 1

如果你有一个包含一系列任意长整数的文本文件，那么 Qi 肯定可以用来非常有效地将该文件解析为单独的数字，以文本标记的形式呈现。如何将这些标记转换为 GMP 数字取决于您，但我建议库提供的通过文本输入数字的机制比您可能想出的任何东西都更优化。

如果您问 Qi 是否可以适应读取包含任意长数字的二进制文件，那么答案是肯定的 - 已经支持二进制解析器，请参见此处： http: //www.boost.org/doc/libs/ 1_48_0/libs/spirit/doc/html/spirit/qi/reference/binary.html。我不确定您的目标数学库整数的格式，我的猜测是您可以将这些原语链接在一起以直接读取数字的二进制表示。或者，您可以基于其中之一设计自己的解析器原语。

Answer 2

看起来彼得在这里提出了错误的问题。

从那以后，我回答了他自己的问题Parse absolute precision numbers with Boost spirit，它确实专注于 LLVM 的 APInt 类型。

然而，在这个过程中，我——当然——展示了如何使用 Boost 多精度类型。

我将添加以下注释以更公正地解决这个问题的重点：

1. 从文件中读取时，使用文件映射和 rawchar*而不是istream和流迭代器。我碰巧刚刚在这里的另一个答案线程中证明了它的速度：评论链接：

   所以这里是如何优化阅读：coliru.stacked-crooked.com/a/0dcb8a05f12a08a5。现在一切都在 ~1.28s 看起来疯狂优化

   

   [...] 从解析它 s/double_/float_/g 中减少几毫秒的唯一方法，但我不会，因为它从 Graph 模型中删除了通用性。–嘿 3 小时前

2. 通常在使用 boost 多精度类型时，您会发现必须禁用表达式模板。另外，我认为真正的任意精度类型往往不能很好地与. 一起使用int_parser<>，但是当我尝试时，固定精度类型都可以。

3. 如果不需要，请考虑根本不解析所有数字。您可以“懒惰地”解析一些文件，只检测例如行边界或其他结构元素。然后在需要时，您可以详细解析感兴趣的片段。

   我有一个非常详细的答案，在内存映射的文本文件中显示了这一点（使用 boost::iostreams::mapped_file_source 和 std::multimap），您可以在没有任何内存开销的情况下对多千兆字节文件进行二进制搜索，并且然后只解析相关区域：

   Live On Coliru（包括生成测试数据）

   #define NDEBUG
   #undef DEBUG
   #include <boost/iostreams/device/mapped_file.hpp>
   #include <boost/utility/string_ref.hpp>
   #include <boost/optional.hpp>
   #include <boost/spirit/include/qi.hpp>
   #include <thread>
   #include <iomanip>
   
   namespace io = boost::iostreams;
   namespace qi = boost::spirit::qi;
   
   template <typename Key, typename Value> 
   struct text_multi_lookup {
       text_multi_lookup(char const* begin, char const* end)
           : _map_begin(begin), 
             _map_end(end)
       {
       }
   
     private:
       friend struct iterator;
       enum : char { nl = '\n' };
   
       using rawit = char const*;
       rawit _map_begin, _map_end;
   
       rawit start_of_line(rawit it) const {
           while (it > _map_begin) if (*--it == nl) return it+1;
           assert(it == _map_begin);
           return it;
       }
   
       rawit end_of_line(rawit it) const {
           while (it < _map_end) if (*it++ == nl) return it;
           assert(it == _map_end);
           return it;
       }
   
     public:
       struct value_type final {
           rawit beg, end;
           Key   key;
           Value value;
   
           boost::string_ref str() const { return { beg, size_t(end-beg) }; }
       };
   
       struct iterator : boost::iterator_facade<iterator, boost::string_ref, boost::bidirectional_traversal_tag, value_type> {
   
           iterator(text_multi_lookup const& d, rawit it) : _region(&d), _data { it, nullptr, Key{}, Value{} } { 
               assert(_data.beg == _region->start_of_line(_data.beg));
           }
   
         private:
           friend text_multi_lookup;
   
           text_multi_lookup const* _region;
           value_type mutable _data;
   
           void ensure_parsed() const {
               if (!_data.end) 
               {
                   assert(_data.beg == _region->start_of_line(_data.beg));
                   auto b = _data.beg;
                   _data.end = _region->end_of_line(_data.beg);
   
                   if (!qi::phrase_parse(
                               b, _data.end,
                               qi::auto_ >> qi::auto_ >> qi::eoi,
                               qi::space,
                               _data.key, _data.value)) 
                   {
                       std::cerr << "Problem in: " << std::string(_data.beg, _data.end) 
                                 << "at:         " << std::setw(_data.end-_data.beg) << std::right << std::string(_data.beg,_data.end);
                       assert(false);
                   }
               }
           }
   
           static iterator mid_point(iterator const& a, iterator const& b) {
               assert(a._region == b._region);
               return { *a._region, a._region->start_of_line(a._data.beg + (b._data.beg -a._data.beg)/2) };
           }
   
         public:
           value_type const& dereference() const {
               ensure_parsed();
               return _data;
           }
   
           bool equal(iterator const& o) const {
               return (_region == o._region) && (_data.beg == o._data.beg);
           }
   
           void increment() {
               _data = { _region->end_of_line(_data.beg), nullptr, Key{}, Value{} };
               assert(_data.beg == _region->start_of_line(_data.beg));
           }
       };
   
       using const_iterator = iterator;
   
       const_iterator begin()  const { return { *this, _map_begin }; }
       const_iterator end()    const { return { *this, _map_end   }; }
       const_iterator cbegin() const { return { *this, _map_begin }; }
       const_iterator cend()   const { return { *this, _map_end   }; }
   
       template <typename CompatibleKey>
       const_iterator lower_bound(CompatibleKey const& key) const {
           auto f(begin()), l(end());
           while (f!=l) {
               auto m = iterator::mid_point(f,l);
   
               if (m->key < key) {
                   f = m;
                   ++f;
               }
               else {
                   l = m;
               }
           }
           return f;
       }
   
       template <typename CompatibleKey>
       const_iterator upper_bound(CompatibleKey const& key) const {
           return upper_bound(key, begin());
       }
   
     private:
       template <typename CompatibleKey>
       const_iterator upper_bound(CompatibleKey const& key, const_iterator f) const {
           auto l(end());
           while (f!=l) {
               auto m = iterator::mid_point(f,l);
   
               if (key < m->key) {
                   l = m;
               }
               else {
                   f = m;
                   ++f;
               }
           }
           return f;
       }
   
     public:
       template <typename CompatibleKey>
       std::pair<const_iterator, const_iterator> equal_range(CompatibleKey const& key) const {
           auto lb = lower_bound(key);
           return { lb, upper_bound(key, lb) };
       }
   
   };
   
   #include <iostream>
   
   int main() {
       io::mapped_file_source map("input.txt");
       text_multi_lookup<double, unsigned int> tml(map.data(), map.data() + map.size());
   
       auto const e = tml.end();
   
       for(auto&& line : tml)
       {
           std::cout << line.str();
   
           auto er = tml.equal_range(line.key);
   
           if (er.first  != e) std::cout << " lower: " << er.first->str();
           if (er.second != e) std::cout << " upper: " << er.second->str();
       }
   }