c++ - parsear - División rápida de cadenas con múltiples delimitadores
substring from a string c++ (3)
Dos cosas vienen a la mente:
- Use vistas de cadena en lugar de cadenas como el resultado de división, guarda muchas asignaciones.
- 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.
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 ?
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.