boost :: tokenizer 대 boost :: split

Question

모든 '^'문자의 C++ 문자열을 벡터 토큰으로 구문 분석하려고합니다. boost :: split 메서드를 항상 사용했지만 성능이 중요한 코드를 작성하고 어느 것이 더 나은 성능을 제공하는지 알고 싶습니다. 하나가 더 나은 성능과 이유를 줄 것이다

string message = "A^B^C^D"; 
vector<string> tokens; 
boost::split(tokens, message, boost::is_any_of("^")); 

대

boost::char_separator<char> sep("^"); 
boost::tokenizer<boost::char_separator<char> > tokens(text, sep); 

: 예를 들어

?

감사합니다.

Answer 1

최상의 선택은 몇 가지 요인에 따라 다릅니다. 일단 토큰을 스캔 할 필요가 있다면 boost :: tokenizer는 런타임 성능과 공간 성능 모두에서 좋은 선택입니다 (입력 데이터에 따라 토큰 벡터가 많은 공간을 차지할 수 있습니다).

토큰을 자주 스캔하거나 효율적인 무작위 액세스가 필요한 벡터가 필요한 경우 boost :: split를 벡터로 사용하는 것이 더 좋은 옵션 일 수 있습니다.

예를 들어,에 "A^B^C^...^Z"토큰의 길이는 1 바이트의 입력 스트링은 boost::split/vector<string> 방법 적어도 2 * N-1 바이트를 소모 할 것이다. 문자열이 대부분의 STL 구현에 저장되는 방식으로 계산하면 8 배 이상을 차지합니다. 이러한 문자열을 벡터에 저장하는 것은 메모리와 시간면에서 비용이 많이 든다. = 2.5s 및 ~ 620메가바이트

부스트 ::

• 부스트 :: 분할 :
  나는이처럼 보였다 내 컴퓨터 및 1000 만 토큰과 유사한 패턴에 대한 빠른 테스트를 실행 토크 나이 = 0.9s 및 0메가바이트

그냥하고 있다면 한 번의 토큰의 수 있습니다, 그럼 분명 tokenizer 더 낫다. 그러나 응용 프로그램의 수명 동안 다시 사용하려는 구조로 파쇄하는 경우 토큰 벡터를 사용하는 것이 좋습니다.

벡터 경로를 가고 싶다면 vector<string>을 사용하지 말고 string :: iterators의 벡터를 사용하는 것이 좋습니다. 반복기 쌍으로 파쇄하고 큰 토큰 문자열을 참조 용으로 보관하십시오. 예를 들어 :

는

using namespace std; 
vector<pair<string::const_iterator,string::const_iterator> > tokens; 
boost::split(tokens, s, boost::is_any_of("^")); 
for(auto beg=tokens.begin(); beg!=tokens.end();++beg){ 
    cout << string(beg->first,beg->second) << endl; 
} 

이 개선 된 버전은 동일한 서버 및 테스트에 1.6s 및 3백90메가바이트 걸립니다. 그리고이 벡터의 모든 메모리 오버 헤드 중 가장 좋은 것은 토큰의 수에 따라 선형입니다. 어떤 식 으로든 토큰의 길이에 의존하지 않지만 std::vector<string>은 각 토큰을 저장합니다.

Answer 2

clang++ -O3 -std=c++11 -stdlib=libc++을 사용하면 약간 다른 결과가 나타납니다.

먼저 그래서 같은 거대한 문자열로 아니 바꿈과 쉼표로 구분 ~ 470k 워드 텍스트 파일을 추출 :

path const inputPath("input.txt"); 

filebuf buf; 
buf.open(inputPath.string(),ios::in); 
if (!buf.is_open()) 
    return cerr << "can't open" << endl, 1; 

string str(filesystem::file_size(inputPath),'\0'); 
buf.sgetn(&str[0], str.size()); 
buf.close(); 

그럼 I 클리어 미리 크기 벡터에 결과를 저장하는 다양한 타이밍 된 테스트를 실행

struct timed 
{ 
    ~timed() 
    { 
     auto duration = chrono::duration_cast<chrono::duration<double, ratio<1,1000>>>(chrono::high_resolution_clock::now() - start_); 

     cout << setw(40) << right << name_ << ": " << duration.count() << " ms" << endl; 
    } 

    timed(std::string name="") : 
     name_(name) 
    {} 


    chrono::high_resolution_clock::time_point const start_ = chrono::high_resolution_clock::now(); 
    string const name_; 
}; 

,691,363 : 실행 사이에, 예를 들어, 참고로

void vectorStorage(string const& str) 
{ 
    static size_t const expectedSize = 471785; 

    vector<string> contents; 
    contents.reserve(expectedSize+1); 

    ... 

    { 
     timed _("split is_any_of"); 
     split(contents, str, is_any_of(",")); 
    } 
    if (expectedSize != contents.size()) throw runtime_error("bad size"); 
    contents.clear(); 

    ... 
} 

는 타이머가 바로 이것이다210

나는 하나의 반복 (벡터 없음)도 기록했다. 다음은 결과입니다 :

{ 
    string word; 
    word.reserve(128); 

    timed _("tokenizer"); 
    boost::char_separator<char> sep(","); 
    boost::tokenizer<boost::char_separator<char> > tokens(str, sep); 

    for (auto range : tokens) 
    {} 
} 

{ 
    string word; 

    timed _("split iterator"); 
    for (auto it = make_split_iterator(str, token_finder(is_from_range(',', ','))); 
     it != decltype(it)(); ++it) 
    { 
     word = move(copy_range<string>(*it)); 
    } 
} 

이 명확한 결론 : split를 사용

Vector: 
           hand-coded: 54.8777 ms 
         split is_any_of: 67.7232 ms 
        split is_from_range: 49.0215 ms 
           tokenizer: 119.37 ms 
One iteration: 
           tokenizer: 97.2867 ms 
          split iterator: 26.5444 ms 
      split iterator back_inserter: 57.7194 ms 
       split iterator char copy: 34.8381 ms 

토크 나이split보다 느린 너무 많이가, 한 - 반복 그림은 심지어 문자열 사본을 포함하지 않습니다.

Answer 3

부스트 버전 및 기능에 따라 다를 수 있습니다.

boost :: split 1.41.0을 사용하여 수천 또는 수십만 개의 작은 문자열 (10 개 미만의 토큰이 예상 됨)을 처리하는 일부 논리에서 성능 문제가있었습니다. 성능 분석기를 통해 코드를 실행했을 때 예상치 못한 39 %의 시간이 boost :: split에 소비된다는 것을 알았습니다.

우리는 "각 패스마다 10 개 이상의 항목이 없으므로 벡터를 10 개 항목으로 사전 설정"과 같이 성능에 크게 영향을 미치지 않는 간단한 "수정"을 시도했습니다.

벡터가 실제로 필요하지 않았기 때문에 토큰을 반복하고 동일한 작업을 수행 할 수 있으므로 코드를 boost :: tokenize로 변경했으며 코드의 동일한 섹션이 < 1 %의 런타임으로 떨어졌습니다.