c++ - parsear - División rápida de cadenas con múltiples delimitadores

substring from a string c++

Question

Investigué algún tiempo aquí en StackOverflow para encontrar buenos algoritmos para dividir cadenas con múltiples delimitadores en un vector< string > . También encontré algunos métodos:

La forma de Boost:

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

el método getline :

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

la forma tokenize de Boost:

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

y la genial forma de STL:

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

y el método de Shadow2531 (ver el tema relacionado).

La mayoría de ellos vino de este tema . Pero lamentablemente no resuelven mi problema:

• La división de Boost es fácil de usar, pero con los grandes datos (alrededor de 1.5 * 10 ^ 6 elementos individuales en el mejor de los casos) y cerca de 10 delimitadores que estoy usando es terriblemente lento.

• Los métodos getline , STL y Shadow2531 tienen el problema de que solo puedo usar un único carácter como delimitador. Necesito algunos más.

• La tokenización de Boost es aún más horrible en el aspecto de la velocidad. Pasaron 11 segundos con 10 delimitadores para dividir una cadena en 1.5 * 10 ^ 6 elementos.

Así que no sé qué hacer: quiero tener un algoritmo de división de cadenas realmente rápido con múltiples delimitadores.

¿Boost se divide al máximo o hay una forma de hacerlo más rápido ?

Answer 1

Dos cosas vienen a la mente:

1. Use vistas de cadena en lugar de cadenas como el resultado de división, guarda muchas asignaciones.
2. Si sabe que solo va a trabajar con caracteres (en el rango [0,255]), intente utilizar un conjunto de bits para probar la pertenencia en lugar de find los caracteres del delimitador.

Aquí hay un intento rápido de aplicar estas ideas:

#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;
}

Al compilar esto con Boost 1.46.1 usando GCC 4.5.1 con el indicador -O4 habilitado, obtengo:

• Tiempo: 5.951 (Boost.Split + vector)
• Tiempo: 3.728 (Boost.Split + vector
• Tiempo: 1.662 (división personalizada + vector)
• Tiempo: 0.144 (división personalizada + vector)
• Tiempo: 2.13 (Strpbrk + vector)
• Tiempo: 0.527 (Strpbrk + vector)

NOTA: Hay una ligera diferencia en la salida ya que mi función personalizada elimina los tokens vacíos. Pero puede adaptar este código a sus necesidades si decide usarlo.

Answer 2

En tales cadenas grandes, puede ser útil utilizar ropes . O use las vistas de cadena como Pablo recomienda: pares ( char const* , size_t ). El truco de bitset no es necesario si tienes una buena implementación de strpbrk .

Answer 3

Para combinar las mejores partes de las respuestas de Pablo y Larsman, use un par (offset, size) para almacenar subcadenas y strcspn para obtener las extensiones de cada entrada.