Aumente el rendimiento de la sustitución de expresiones regulares de C ++

Soy un progtwigdor principiante de C ++ que trabaja en un pequeño proyecto de C ++ para el que tengo que procesar una cantidad de archivos XML relativamente grandes y eliminar las tags XML de ellos. He tenido éxito al hacerlo utilizando la biblioteca de expresiones regulares de C ++ 0x. Sin embargo, estoy teniendo algunos problemas de rendimiento. Solo leer en los archivos y ejecutar la función regex_replace sobre su contenido toma alrededor de 6 segundos en mi PC. Puedo reducir esto a 2 agregando algunos indicadores de optimización del comstackdor. Sin embargo, al utilizar Python, puedo hacerlo en menos de 100 milisegundos. Obviamente, estoy haciendo algo muy ineficiente en mi código C ++. ¿Qué puedo hacer para acelerar esto un poco?

Mi código C ++:

std::regex xml_tags_regex("]*>"); for (std::vector::iterator it = _files.begin(); it != _files.end(); it++) { std::ifstream file(*it); file.seekg(0, std::ios::end); size_t size = file.tellg(); std::string buffer(size, ' '); file.seekg(0); file.read(&buffer[0], size); buffer = regex_replace(buffer, xml_tags_regex, ""); file.close(); } 

Mi código de Python:

 regex = re.compile(']*>') for filename in filenames: with open(filename) as f: content = f.read() content = regex.sub('', content) 

PD: realmente no me importa procesar el archivo completo a la vez. Acabo de encontrar que la lectura de un archivo línea por línea, palabra por palabra o carácter por carácter lo redujo considerablemente.

No creo que esté haciendo nada “incorrecto”, la biblioteca de expresiones regulares de C ++ simplemente no es tan rápida como la de Python (para este caso de uso al menos en este momento). Esto no es demasiado sorprendente, teniendo en cuenta que el código de expresión regular de python también está incluido en C / C ++ bajo el capó, y ha sido sintonizado a lo largo de los años para que sea bastante rápido, ya que es una característica bastante importante de python. ser bastante rapido

Pero hay otras opciones en C ++ para obtener las cosas más rápido si lo necesita. He usado PCRE ( http://pcre.org/ ) en el pasado con excelentes resultados, aunque estoy seguro de que también hay otros buenos en estos días.

Sin embargo, para este caso en particular, también puede lograr lo que está buscando sin expresiones regulares, lo que en mis pruebas rápidas produjo una mejora de rendimiento 10x. Por ejemplo, el siguiente código escanea su cadena de entrada copiando todo a un nuevo búfer, cuando golpea un < comienza a saltarse los caracteres hasta que ve el cierre >

 std::string buffer(size, ' '); std::string outbuffer(size, ' '); ... read in buffer from your file size_t outbuffer_len = 0; for (size_t i=0; i < buffer.size(); ++i) { if (buffer[i] == '<') { while (buffer[i] != '>' && i < buffer.size()) { ++i; } } else { outbuffer[outbuffer_len] = buffer[i]; ++outbuffer_len; } } outbuffer.resize(outbuffer_len); 

La sustitución de expresiones regulares de C ++ 11 es bastante lenta, al menos hasta el momento. PCRE se desempeña mucho mejor en términos de velocidad de coincidencia de patrones, sin embargo, PCRECPP proporciona medios muy limitados para la sustitución basada en expresiones regulares, citando la página del manual:

Puede reemplazar la primera coincidencia de “patrón” en “str” ​​con “reescribir”. Dentro de “reescribir”, se pueden usar los dígitos con escape de barra invertida (\ 1 a \ 9) para insertar texto que coincida con el grupo correspondiente entre paréntesis del patrón. \ 0 en “reescribir” se refiere a todo el texto coincidente.

Esto es realmente pobre, comparado con el comando de Perl. Es por eso que escribí mi propio envoltorio de C ++ alrededor de PCRE que maneja la sustitución basada en expresiones regulares de manera similar a la de Perl, y también admite cadenas de caracteres de 16 y 32 bits: PCRSCPP :

Sintaxis de la cadena de comandos

La syntax del comando sigue la convención de Perl s/pattern/substitute/[options] . Cualquier carácter (excepto la barra invertida \ ) se puede usar como delimitador, no solo / , pero asegúrese de que el delimitador se escape con una barra diagonal invertida ( \ ) si se usa en las subcadenas de pattern , substitute o options , por ejemplo:

  • s/\\/\//g para reemplazar todas las barras diagonales inversas con las anteriores

Recuerde doblar las barras diagonales inversas en el código C ++, a menos que use un literal de cadena sin formato (vea el literal de cadena ):

pcrscpp::replace rx("s/\\\\/\\//g");

Sintaxis de cadena de patrones

La cadena de patrón se pasa directamente a pcre*_compile y, por lo tanto, tiene que seguir la syntax de PCRE como se describe en la documentación de PCRE .

Sintaxis de cadena de sustitución

La syntax sustitutiva de las cadenas de referencia es similar a la de Perl:

  • $1$n : nth n captura de subpatrón emparejado.
  • $& y $0 : todo el partido
  • ${label} : subpattern etiquetado. label es de hasta 32 caracteres alfanuméricos + de subrayado ( 'A'-'Z' , 'a'-'z' , '0'-'9' , '_' ), el primer carácter debe ser alfabético
  • $` y $' (comilla y marca) se refieren a las áreas del sujeto antes y después del partido, respectivamente. Al igual que en Perl, se utiliza el sujeto no modificado, incluso si una sustitución global coincidía previamente.

Además, las siguientes secuencias de escape son reconocidas:

  • \n : nueva línea
  • \r : retorno de carro
  • \t : pestaña horizontal
  • \f : form feed
  • \b : retroceso
  • \a : alarma, campana
  • \e : escapar
  • \0 : cero binario

Cualquier otra secuencia de escape \ , se interpreta como , lo que significa que también tiene que escapar barras invertidas

Opciones de syntax de cadenas

De manera similar a Perl, la cadena de opciones es una secuencia de letras modificadoras permitidas. PCRSCPP reconoce los siguientes modificadores:

  1. Banderas compatibles con Perl
    • g : reemplazo global, no solo la primera coincidencia
    • i : emparejamiento insensible a mayúsculas
      (PCRE_CASELESS)
    • m : modo multilínea: ^ y $ adicionalmente coinciden las posiciones antes y después de las nuevas líneas, respectivamente
      (PCRE_MULTILINE)
    • s : deja el scope de la . metacarácter incluye nuevas líneas (tratar las nuevas líneas como caracteres comunes)
      (PCRE_DOTALL)
    • x : permite syntax extendida de expresiones regulares, habilitando espacios en blanco y comentarios en patrones complejos
      (PCRE_EXTENDED)
  2. Banderas compatibles con PHP
    • A : patrón “ancla”: busque solo coincidencias “ancladas”: las que comienzan con cero desplazamiento. En el modo de una sola línea, es idéntico al prefijo de todas las twigs alternativas de patrón con ^
      (PCRE_ANCHORED)
    • D : trata a dólar $ como una afirmación final del asunto solamente, anulando el valor predeterminado: fin o inmediatamente antes de una nueva línea al final. Ignorado en modo multilínea
      (PCRE_DOLLAR_ENDONLY)
    • U : Invertir * y + Lógica de codicia: crear ungreedy por defecto,? Cambia de nuevo a codicioso. (?U) y (?-U) los interruptores en el patrón no se ven afectados
      (PCRE_UNGREEDY)
    • u : modo Unicode. Trate el patrón y el tema como una cadena UTF8 / UTF16 / UTF32. A diferencia de PHP, también afecta a las nuevas líneas, \R , \d , \w , etc.
      ((PCRE_UTF8 / PCRE_UTF16 / PCRE_UTF32) | PCRE_NEWLINE_ANY | PCRE_BSR_UNICODE | PCRE_UCP)
  3. Banderas propias de PCRSCPP:
    • N : omitir partidos vacíos
      (PCRE_NOTEMPTY)
    • T : tratar el sustituto como una cadena trivial, es decir, no hacer una referencia inversa y la interpretación de secuencias de escape
    • n : descartar las partes no coincidentes de la cadena para reemplazar
      Nota: PCRSCPP no agrega automáticamente nuevas líneas, el resultado del reemplazo es una concatenación simple de coincidencias, tenga esto en cuenta en el modo multilínea

Escribí un código de prueba de velocidad simple, que almacena una copia 10x del archivo “move.sh” y prueba el rendimiento de expresiones regulares en la cadena resultante:

 #include  #include  #include  #include  #include  #include  int main (int argc, char *argv[]) { const std::string file_name("move.sh"); pcrscpp::replace pcrscpp_rx(R"del(s/(?:^|\n)mv[ \t]+(?:-f)?[ \t]+"([^\n]+)"[ \t]+"([^\n]+)"(?:$|\n)/$1\n$2\n/Dgn)del"); std::regex std_rx (R"del((?:^|\n)mv[ \t]+(?:-f)?[ \t]+"([^\n]+)"[ \t]+"([^\n]+)"(?:$|\n))del"); std::ifstream file (file_name); if (!file.is_open ()) { std::cerr << "Unable to open file " << file_name << std::endl; return 1; } std::string buffer; { file.seekg(0, std::ios::end); size_t size = file.tellg(); file.seekg(0); if (size > 0) { buffer.resize(size); file.read(&buffer[0], size); buffer.resize(size - 1); // strip '\0' } } file.close(); std::string bigstring; bigstring.reserve(10*buffer.size()); for (std::string::size_type i = 0; i < 10; i++) bigstring.append(buffer); int n = 10; std::cout << "Running tests " << n << " times: be patient..." << std::endl; std::chrono::high_resolution_clock::duration std_regex_duration, pcrscpp_duration; std::chrono::high_resolution_clock::time_point t1, t2; std::string result1, result2; for (int i = 0; i < n; i++) { // clear result std::string().swap(result1); t1 = std::chrono::high_resolution_clock::now(); result1 = std::regex_replace (bigstring, std_rx, "$1\\n$2", std::regex_constants::format_no_copy); t2 = std::chrono::high_resolution_clock::now(); std_regex_duration = (std_regex_duration*i + (t2 - t1)) / (i + 1); // clear result std::string().swap(result2); t1 = std::chrono::high_resolution_clock::now(); result2 = pcrscpp_rx.replace_copy (bigstring); t2 = std::chrono::high_resolution_clock::now(); pcrscpp_duration = (pcrscpp_duration*i + (t2 - t1)) / (i + 1); } std::cout << "Time taken by std::regex_replace: " << std_regex_duration.count() << " ms" << std::endl << "Result size: " << result1.size() << std::endl; std::cout << "Time taken by pcrscpp::replace: " << pcrscpp_duration.count() << " ms" << std::endl << "Result size: " << result2.size() << std::endl; return 0; } 

(tenga en cuenta que las expresiones regulares de std y pcrscpp hacen lo mismo aquí, la nueva línea final en la expresión de pcrscpp se debe a std::regex_replace no se eliminan las nuevas líneas a pesar de std::regex_constants::format_no_copy )

y lo lanzó en un script de movimiento de shell grande (20.9 MB):

 Running tests 10 times: be patient... Time taken by std::regex_replace: 12090771487 ms Result size: 101087330 Time taken by pcrscpp::replace: 5910315642 ms Result size: 101087330 

Como puede ver, PCRSCPP es más de 2 veces más rápido. Y espero que esta brecha crezca a medida que aumenta la complejidad de los patrones, ya que PCRE maneja los patrones complicados mucho mejor. Originalmente escribí un envoltorio para mí mismo, pero creo que también puede ser útil para otros.

Saludos, Alex