将一串数字字符串快速解析为整数向量的最快方法

Question

我想知道将数字字符串快速解析为整数向量的最佳方法。我的情况是，我将有数百万行的数据，格式如下：

>Header-name
ID1    1    1   12
ID2    3    6   234
.
.
.
>Header-name
ID1    1    1   12
ID2    3    6   234
.
.
.

我希望放弃“Header-name”字段（或者以后可能用它进行排序），然后忽略ID字段，将剩下的三个整数放入一个向量中。 我意识到我可以使用boost split，然后在一些for循环中使用lexical cast来忽略某些数据，但我不确定这是否会给我最快的解决方案。我看过boost spirit，但我不太明白如何使用它。Boost或STL都可以。

- zeus_masta_funk

---

你可以在这里阅读灵感，https://dev59.com/pWQm5IYBdhLWcg3wowIF#17479702。我猜只需要将float替换为int即可。 - sehe

Answer 1

您是否必须使用boost？ 我已经使用了这个函数一段时间。我相信我是从Accelerated C++中得到的，并且一直在使用它。您的分隔符似乎是一个制表符或多个空格。如果您将分隔符传递给“ ”，它可能会起作用。不过我认为这将取决于实际情况。

std::vector<std::string> split( const std::string& line, const std::string& del )
{
        std::vector<std::string> ret;
        size_t i = 0;

        while ( i != line.size() ) {

                while ( ( i != line.size() ) && ( line.substr(i, 1) == del ) ) {
                        ++i;
                }

                size_t j = i;

                while ( ( j != line.size() ) && ( line.substr(j, 1) != del ) ) {
                        ++j;
                }

                if ( i != j ) {
                        ret.push_back( line.substr( i, j - i ) );
                        i = j;
                }
        }

        return ret;
}

你可以用以下代码获取每一行：

int main() {
    std::string line;
    std::vector<std::string> lines; 
    while ( std::getline( std::cin, line ) ) {
        lines.push_back( line );
    }

    for ( auto it = lines.begin(); it != lines.end(); it++ ) {
        std::vector<string> vec = split( (*it) );
        // Do something
    }
}

你可以通过快速修改来获取返回 std::vector。 使用 atoi( myString.c_str() ) 将每个字符串转换为 int。 另外，你需要添加一个检查以跳过标题。 这应该很简单。

请注意，我以上内容尚未进行编译。 ;)

- kiss-o-matic

Answer 2

在这个特定的问题上，如果您想要最快的解决方案，我建议手动逐个字符解析。Boost Spirit可能是次优的选择，并且可以节省大量丑陋的代码。

手动逐个字符解析是实现高速的关键，因为即使像atoi和strtol这样经过优化的转换器也必须处理许多不同的数字表示，而您的示例似乎暗示您只对纯无符号整数感兴趣。格式化IO（scanf、operator<<等）非常缓慢。将行读入中间字符串可能会有明显的代价。

假设标题行不包含任何'\t'（并且假设没有任何IO或格式错误），您的问题足够简单，可以手动解析。

#include <iostream>
#include <sstream>
#include <vector>
#include <string>

std::vector<unsigned> parse(std::istream &is)
{
    bool skipField = true;
    char c;
    unsigned value = 0;
    std::vector<unsigned> result;
    while (is.get(c))
    {
        if (('\t' == c) || ('\n' == c))
        {
            if (!skipField)
            {
                result.push_back(value);
            }
            skipField = ('\n' == c);
            value = 0;
        }
        else if (!skipField)
        {
            value *= 10;
            value += (c - '0');
        }
    }
    return result;
}

int main()
{
    const std::string data = ">Header-name\nID1\t1\t1\t12\nID2\t3\t6\t234\n";
    std::istringstream is(data);
    const std::vector<unsigned> v = parse(is);
    for (unsigned u: v)
    {
        std::cerr << u << std::endl;
    }
}

- Come Raczy

Answer 3

作为一道令人愉悦的问题，像这样没有明确规定的问题，除了展示“一种”做“一件事”的方法外，没有太多其他东西。在这种情况下，我使用了Boost Spirit（因为您提到了它）：

解析为平面容器

#include <boost/spirit/include/qi.hpp>
#include <boost/fusion/adapted.hpp>
#include <map>

std::string const input(
    ">Header - name1\n"
    "ID1    1    1   12\n"
    "ID2    3    6   234\n"
    ">Header - name2\n"
    "ID3    3    3   14\n"
    "ID4    5    8   345\n"
);

using Header    = std::string;
using Container = std::vector<int>;
using Data      = std::map<Header, Container>;

int main()
{
    namespace qi = boost::spirit::qi;

    auto f(input.begin()), l(input.end());

    Data data;
    bool ok = qi::phrase_parse(f, l,
        *(
            '>' >> qi::raw[*(qi::char_ - qi::eol)] >> qi::eol
           >> *(!qi::char_('>') >> qi::omit[qi::lexeme[+qi::graph]] >> *qi::int_ >> qi::eol)
        ), qi::blank, data);

    if (ok)
    {
        std::cout << "Parse success\n";
        for (auto const& entry : data)
        {
            std::cout << "Integers read with header '" << entry.first << "':\n";
            for (auto i : entry.second)
                std::cout << i << " ";
            std::cout << "\n";
        }
    }
    else
    {
        std::cout << "Parse failed\n";
    }

    if (f != l)
        std::cout << "Remaining input: '" << std::string(f, l) << "'\n";
}

打印

Parse success
Integers read with header 'Header - name1':
1 1 12 3 6 234
Integers read with header 'Header - name2':
3 3 14 5 8 345

解析为嵌套容器

当然，如果你想为每行创建单独的向量（不要期望效率），那么你只需要替换typedef即可：

using Container = std::list<std::vector<int> >; // or any other nested container

// to make printing work without further change:
std::ostream& operator<<(std::ostream& os, std::vector<int> const& v)
{
    os << "[";
    std::copy(v.begin(), v.end(), std::ostream_iterator<int>(os, " "));
    return os << "]";
}

打印

Parse success
Integers read with header 'Header - name1':
[1 1 12 ] [3 6 234 ]
Integers read with header 'Header - name2':
[3 3 14 ] [5 8 345 ]

- sehe

---

我认为这是一个很好的答案，但是当我编译时出现了一些错误： /usr/include/boost/spirit/home/support/algorithm/any_if.hpp:204:72: [跳过5个实例化上下文] && /usr/include/boost/spirit/home/support/container.hpp:110:12: 错误：‘int’不是类、结构体或联合类型 && /usr/include/boost/spirit/home/qi/operator/sequence_base.hpp:86:13: [跳过4个实例化上下文] && /usr/include/boost/spirit/home/qi/operator/kleene.hpp:68:17: 错误：在‘struct boost::spirit::traits::container_value<int, void>’中没有名为‘type’的类型 我正在使用boost1.46，这会导致错误吗？ - zeus_masta_funk

可能是。我正在使用boost 1_55。 - sehe

Answer 4

你可以使用类似以下的代码，只不过你需要从文件中获取字符串而不是使用字符串数组：

#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <iterator>

int main() 
{
    std::string s[] = { "ID1    1    1   12", "ID2    3    6   234" };
    std::vector<int> v;

    for ( const std::string &t : s )
    {
        std::istringstream is( t );
        std::string tmp;

        is >> tmp;

        v.insert( v.end(), std::istream_iterator<int>( is ), 
                           std::istream_iterator<int>() );
    }                         

    for ( int x : v ) std::cout << x << ' ';
    std::cout << std::endl;

    return 0;
}

输出结果为

1 1 12 3 6 234 

关于标题，您可以检查 tmp 是否为标题，如果是，则跳过此记录。

这是一个简化版本。

#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <iterator>

int main() 
{
    std::string s[] = 
    { 
        "ID1    1    1   12", 
        ">Header-name", 
        "ID2    3    6   234" 
    };

    std::vector<int> v;

    for ( const std::string &t : s )
    {
        std::istringstream is( t );
        std::string tmp;

        is >> tmp;

        if ( tmp[0] == '>' ) continue;

        v.insert( v.end(), std::istream_iterator<int>( is ), 
                           std::istream_iterator<int>() );
    }                         

    for ( int x : v ) std::cout << x << ' ';
    std::cout << std::endl;

    return 0;
}

输出将与上述相同。

- Vlad from Moscow