Быстрое разделение строк с несколькими разделителями - PullRequest
Новая
       9

Быстрое разделение строк с несколькими разделителями

27 голосов
/ 01 апреля 2011

Я некоторое время исследовал здесь, в StackOverflow, чтобы найти хорошие алгоритмы для разделения строк с несколькими разделителями на vector< string >.Я также нашел несколько методов:

Способ Boost: 

boost::split(vector, string, boost::is_any_of(" \t"));

Метод getline: 

std::stringstream ss(string);
std::string item;
while(std::getline(ss, item, ' ')) {
    vector.push_back(item);
}

токенизированный способ Boost: 

char_separator<char> sep(" \t");
tokenizer<char_separator<char>> tokens(string, sep);
BOOST_FOREACH(string t, tokens)
{
   vector.push_back(t);
}

и классный способ STL: 

     istringstream iss(string);
     copy(istream_iterator<string>(iss),
     istream_iterator<string>(),
     back_inserter<vector<string> >(vector));

и метод Shadow2531 (см. Связанную тему).

Большинство из них пришли из из этой темы .Но они, к сожалению, не решают мою проблему:

  • Сплит Boost прост в использовании, но с большими данными (около 1,5 * 10 ^ 6 отдельных элементов в лучших случаях) и около 10 разделителейЯ использую это ужасно медленно.

  • Метод getline, STL и Shadow2531 имеет проблему, заключающуюся в том, что я могу использовать только один символ в качестве разделителя.Мне нужно еще немного.

  • Токенизация Boost еще более ужасна в аспекте скорости.Чтобы разделить строку на 1,5 * 10 ^ 6 элементов, потребовалось 11 секунд с 10 разделителями.

Так что я не знаю, что делать: я хочу сделать действительно быстрое разбиение строкиалгоритм с несколькими разделителями.

Максимальное разделение Boost или есть способ сделать это быстрее ?

Ответы [ 3 ]

33 голосов
/ 01 апреля 2011

На ум приходят две вещи:

  1. Использование строк вместо строк как результат разделения, экономит много распределение.
  2. Если ты знаешь, что ты только будет работать с символами (в диапазон [0,255]), попробуйте использовать битсет для проверки членства вместо find вход в разделитель символы.

Вот быстрая попытка применить эти идеи: 

#include <vector>
#include <bitset>
#include <iostream>
#include <boost/algorithm/string/split.hpp>
#include <boost/algorithm/string/classification.hpp>
#include <boost/timer.hpp>

using namespace std;
size_t const N = 10000000;

template<typename C>
void test_custom(string const& s, char const* d, C& ret)
{
  C output;

  bitset<255> delims;
  while( *d )
  {
    unsigned char code = *d++;
    delims[code] = true;
  }
  typedef string::const_iterator iter;
  iter beg;
  bool in_token = false;
  for( string::const_iterator it = s.begin(), end = s.end();
    it != end; ++it )
  {
    if( delims[*it] )
    {
      if( in_token )
      {
        output.push_back(typename C::value_type(beg, it));
        in_token = false;
      }
    }
    else if( !in_token )
    {
      beg = it;
      in_token = true;
    }
  }
  if( in_token )
    output.push_back(typename C::value_type(beg, s.end()));
  output.swap(ret);
}

template<typename C>
void test_strpbrk(string const& s, char const* delims, C& ret)
{
  C output;

  char const* p = s.c_str();
  char const* q = strpbrk(p+1, delims);
  for( ; q != NULL; q = strpbrk(p, delims) )
  {
    output.push_back(typename C::value_type(p, q));
    p = q + 1;
  }

  output.swap(ret);
}

template<typename C>
void test_boost(string const& s, char const* delims)
{
  C output;
  boost::split(output, s, boost::is_any_of(delims));
}

int main()
{
  // Generate random text
  string text(N, ' ');
  for( size_t i = 0; i != N; ++i )
    text[i] = (i % 2 == 0)?('a'+(i/2)%26):((i/2)%2?' ':'\t');

  char const* delims = " \t[],-'/\\!\"§$%&=()<>?";

  // Output strings
  boost::timer timer;
  test_boost<vector<string> >(text, delims);
  cout << "Time: " << timer.elapsed() << endl;

  // Output string views
  typedef string::const_iterator iter;
  typedef boost::iterator_range<iter> string_view;
  timer.restart();
  test_boost<vector<string_view> >(text, delims);
  cout << "Time: " << timer.elapsed() << endl;

  // Custom split
  timer.restart();
  vector<string> vs;
  test_custom(text, delims, vs);
  cout << "Time: " << timer.elapsed() << endl;

  // Custom split
  timer.restart();
  vector<string_view> vsv;
  test_custom(text, delims, vsv);
  cout << "Time: " << timer.elapsed() << endl;

  // Custom split
  timer.restart();
  vector<string> vsp;
  test_strpbrk(text, delims, vsp);
  cout << "Time: " << timer.elapsed() << endl;

  // Custom split
  timer.restart();
  vector<string_view> vsvp;
  test_strpbrk(text, delims, vsvp);
  cout << "Time: " << timer.elapsed() << endl;

  return 0;
}

Компиляция с Boost 1.46.1 с использованием GCC 4.5.1 с включенным флагом -O4 Я получаю:

  • Время: 5.951 (Boost.Split + vector)
  • Время: 3.728 (Boost.Split + vector
  • Время: 1.662 (Пользовательский сплит + вектор)
  • Время: 0,144 (пользовательский сплит + вектор)
  • Время: 2,13 (Штрбрк + вектор)
  • Время: 0,527 (Штрбрк + вектор)

ПРИМЕЧАНИЕ: есть небольшая разница в выводе, поскольку мои пользовательские функции отбрасывают пустые токены. Но вы можете адаптировать этот код к вашим потребностям, если решите его использовать.

2 голосов
/ 01 апреля 2011

Чтобы объединить лучшие части ответов Пабло и Ларсмана, используйте пару (offset, size) для хранения подстрок и strcspn для получения экстентов каждой записи.

1 голос
/ 01 апреля 2011

На таких больших струнах может быть полезно использовать веревки .Или используйте строковые представления, поскольку Пабло рекомендует: (char const*, size_t) пары.Трюк bitset не нужен, если у вас есть хорошая реализация strpbrk.

...