¿La forma más rápida de realizar una búsqueda de subcadenas que no distinga mayúsculas y minúsculas en C / C ++?
https://stackoverflow.com/questions/211535
-
03-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPregunta
Nota
La pregunta a continuación se formuló en 2008 acerca de un código de 2003. Como se muestra en la actualización del OP, esta publicación completa ha sido obsoleta por los algoritmos de la vendimia 2008 y persiste aquí solo como curiosidad histórica.
Necesito hacer una búsqueda rápida de subcadenas que no distinga mayúsculas y minúsculas en C / C ++. Mis requisitos son los siguientes:
- Debería comportarse como strstr () (es decir, devolver un puntero al punto de coincidencia).
- Debe distinguir entre mayúsculas y minúsculas (doh).
- Debe admitir la configuración regional actual.
- Debe estar disponible en Windows (MSVC ++ 8.0) o fácilmente portátil a Windows (es decir, desde una biblioteca de código abierto).
Aquí está la implementación actual que estoy usando (tomada de la Biblioteca GNU C):
/* Return the offset of one string within another.
Copyright (C) 1994,1996,1997,1998,1999,2000 Free Software Foundation, Inc.
This file is part of the GNU C Library.
The GNU C Library is free software; you can redistribute it and/or
modify it under the terms of the GNU Lesser General Public
License as published by the Free Software Foundation; either
version 2.1 of the License, or (at your option) any later version.
The GNU C Library is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
Lesser General Public License for more details.
You should have received a copy of the GNU Lesser General Public
License along with the GNU C Library; if not, write to the Free
Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
02111-1307 USA. */
/*
* My personal strstr() implementation that beats most other algorithms.
* Until someone tells me otherwise, I assume that this is the
* fastest implementation of strstr() in C.
* I deliberately chose not to comment it. You should have at least
* as much fun trying to understand it, as I had to write it :-).
*
* Stephen R. van den Berg, berg@pool.informatik.rwth-aachen.de */
/*
* Modified to use table lookup instead of tolower(), since tolower() isn't
* worth s*** on Windows.
*
* -- Anders Sandvig (anders@wincue.org)
*/
#if HAVE_CONFIG_H
# include <config.h>
#endif
#include <ctype.h>
#include <string.h>
typedef unsigned chartype;
char char_table[256];
void init_stristr(void)
{
int i;
char string[2];
string[1] = '\0';
for (i = 0; i < 256; i++)
{
string[0] = i;
_strlwr(string);
char_table[i] = string[0];
}
}
#define my_tolower(a) ((chartype) char_table[a])
char *
my_stristr (phaystack, pneedle)
const char *phaystack;
const char *pneedle;
{
register const unsigned char *haystack, *needle;
register chartype b, c;
haystack = (const unsigned char *) phaystack;
needle = (const unsigned char *) pneedle;
b = my_tolower (*needle);
if (b != '\0')
{
haystack--; /* possible ANSI violation */
do
{
c = *++haystack;
if (c == '\0')
goto ret0;
}
while (my_tolower (c) != (int) b);
c = my_tolower (*++needle);
if (c == '\0')
goto foundneedle;
++needle;
goto jin;
for (;;)
{
register chartype a;
register const unsigned char *rhaystack, *rneedle;
do
{
a = *++haystack;
if (a == '\0')
goto ret0;
if (my_tolower (a) == (int) b)
break;
a = *++haystack;
if (a == '\0')
goto ret0;
shloop:
;
}
while (my_tolower (a) != (int) b);
jin:
a = *++haystack;
if (a == '\0')
goto ret0;
if (my_tolower (a) != (int) c)
goto shloop;
rhaystack = haystack-- + 1;
rneedle = needle;
a = my_tolower (*rneedle);
if (my_tolower (*rhaystack) == (int) a)
do
{
if (a == '\0')
goto foundneedle;
++rhaystack;
a = my_tolower (*++needle);
if (my_tolower (*rhaystack) != (int) a)
break;
if (a == '\0')
goto foundneedle;
++rhaystack;
a = my_tolower (*++needle);
}
while (my_tolower (*rhaystack) == (int) a);
needle = rneedle; /* took the register-poor approach */
if (a == '\0')
break;
}
}
foundneedle:
return (char*) haystack;
ret0:
return 0;
}¿Puede hacer este código más rápido, o sabe de una mejor implementación?
Nota: noté que la biblioteca GNU C ahora tiene una nueva implementación de strstr () , pero no estoy seguro la facilidad con la que se puede modificar para que no distinga mayúsculas de minúsculas, o si de hecho es más rápido que el anterior (en mi caso). También observé que la implementación anterior todavía se usa para cadenas de caracteres amplias , así que si alguien sabe por qué, compártala.
Actualizar
Solo para aclarar las cosas, en caso de que no lo estuviera ya, no escribí esta función, es parte de la Biblioteca C de GNU. Solo lo modifiqué para que no distinga mayúsculas y minúsculas.
También, gracias por la sugerencia sobre strcasestr () y por ver otras implementaciones de otras fuentes (como OpenBSD, FreeBSD, etc.). Parece ser el camino a seguir. El código anterior es de 2003, por lo que lo publiqué aquí con la esperanza de que haya una mejor versión disponible, lo que aparentemente lo es. :)
Solución
El código que publicaste es aproximadamente la mitad de rápido que strcasestr .
$ gcc -Wall -o my_stristr my_stristr.c
steve@solaris:~/code/tmp
$ gcc -Wall -o strcasestr strcasestr.c
steve@solaris:~/code/tmp
$ ./bench ./my_stristr > my_stristr.result ; ./bench ./strcasestr > strcasestr.result;
steve@solaris:~/code/tmp
$ cat my_stristr.result
run 1... time = 6.32
run 2... time = 6.31
run 3... time = 6.31
run 4... time = 6.31
run 5... time = 6.32
run 6... time = 6.31
run 7... time = 6.31
run 8... time = 6.31
run 9... time = 6.31
run 10... time = 6.31
average user time over 10 runs = 6.3120
steve@solaris:~/code/tmp
$ cat strcasestr.result
run 1... time = 3.82
run 2... time = 3.82
run 3... time = 3.82
run 4... time = 3.82
run 5... time = 3.82
run 6... time = 3.82
run 7... time = 3.82
run 8... time = 3.82
run 9... time = 3.82
run 10... time = 3.82
average user time over 10 runs = 3.8200
steve@solaris:~/code/tmp
La función main era:
int main(void)
{
char * needle="hello";
char haystack[1024];
int i;
for(i=0;i<sizeof(haystack)-strlen(needle)-1;++i)
{
haystack[i]='A'+i%57;
}
memcpy(haystack+i,needle, strlen(needle)+1);
/*printf("%s\n%d\n", haystack, haystack[strlen(haystack)]);*/
init_stristr();
for (i=0;i<1000000;++i)
{
/*my_stristr(haystack, needle);*/
strcasestr(haystack,needle);
}
return 0;
}
Se modificó adecuadamente para probar ambas implementaciones. Me doy cuenta de que, mientras escribo esto, lo dejé en la llamada init_stristr , pero no debería cambiar mucho las cosas. bench es solo un script de shell simple:
#!/bin/bash
function bc_calc()
{
echo $(echo "scale=4;$1" | bc)
}
time="/usr/bin/time -p"
prog="$1"
accum=0
runs=10
for a in $(jot $runs 1 $runs)
do
echo -n "run $a... "
t=$($time $prog 2>&1| grep user | awk '{print $2}')
echo "time = $t"
accum=$(bc_calc "$accum+$t")
done
echo -n "average user time over $runs runs = "
echo $(bc_calc "$accum/$runs")
Otros consejos
Puede usar la función StrStrI que encuentra la primera aparición de una subcadena dentro de una cadena. La comparación no distingue entre mayúsculas y minúsculas. No olvide incluir su encabezado - Shlwapi.h. Vea esto: http: // msdn.microsoft.com/en-us/library/windows/desktop/bb773439(v=vs.85).aspx
Para uso independiente de la plataforma:
const wchar_t *szk_wcsstri(const wchar_t *s1, const wchar_t *s2)
{
if (s1 == NULL || s2 == NULL) return NULL;
const wchar_t *cpws1 = s1, *cpws1_, *cpws2;
char ch1, ch2;
bool bSame;
while (*cpws1 != L'\0')
{
bSame = true;
if (*cpws1 != *s2)
{
ch1 = towlower(*cpws1);
ch2 = towlower(*s2);
if (ch1 == ch2)
bSame = true;
}
if (true == bSame)
{
cpws1_ = cpws1;
cpws2 = s2;
while (*cpws1_ != L'\0')
{
ch1 = towlower(*cpws1_);
ch2 = towlower(*cpws2);
if (ch1 != ch2)
break;
cpws2++;
if (*cpws2 == L'\0')
return cpws1_-(cpws2 - s2 - 0x01);
cpws1_++;
}
}
cpws1++;
}
return NULL;
}
¿Por qué usas _strlwr (cadena); en init_stristr ()? No es una función estándar. Es de suponer que es para el soporte de configuración regional, pero como no es estándar, solo uso:
char_table[i] = tolower(i);
use boost string enra . Está disponible, es multiplataforma y solo un archivo de encabezado (no hay biblioteca para vincular). Sin mencionar que deberías usar boost de todos modos.
#include <boost/algorithm/string/find.hpp>
const char* istrstr( const char* haystack, const char* needle )
{
using namespace boost;
iterator_range<char*> result = ifind_first( haystack, needle );
if( result ) return result.begin();
return NULL;
}
Le aconsejo que tome parte de la implementación de strcasestr común que ya existe. Por ejemplo, glib, glibc, OpenBSD, FreeBSD, etc. Puede buscar más en google.com/codesearch. A continuación, puede realizar algunas mediciones de rendimiento y comparar las diferentes implementaciones.
Suponiendo que ambas cadenas de entrada ya están en minúsculas.
int StringInStringFindFirst(const char* p_cText, const char* p_cSearchText)
{
int iTextSize = strlen(p_cText);
int iSearchTextSize = strlen(p_cSearchText);
char* p_cFound = NULL;
if(iTextSize >= iSearchTextSize)
{
int iCounter = 0;
while((iCounter + iSearchTextSize) <= iTextSize)
{
if(memcmp( (p_cText + iCounter), p_cSearchText, iSearchTextSize) == 0)
return iCounter;
iCounter ++;
}
}
return -1;
}
También puedes intentar usar máscaras ... si, por ejemplo, la mayoría de las cadenas que vas a comparar solo contienen caracteres de la A a la Z, tal vez valga la pena hacer algo como esto.
long GetStringMask(const char* p_cText)
{
long lMask=0;
while(*p_cText != '\0')
{
if (*p_cText>='a' && *p_cText<='z')
lMask = lMask | (1 << (*p_cText - 'a') );
else if(*p_cText != ' ')
{
lMask = 0;
break;
}
p_cText ++;
}
return lMask;
}
Entonces ...
int main(int argc, char* argv[])
{
char* p_cText = "this is a test";
char* p_cSearchText = "test";
long lTextMask = GetStringMask(p_cText);
long lSearchMask = GetStringMask(p_cSearchText);
int iFoundAt = -1;
// If Both masks are Valid
if(lTextMask != 0 && lSearchMask != 0)
{
if((lTextMask & lSearchMask) == lSearchMask)
{
iFoundAt = StringInStringFindFirst(p_cText, p_cSearchText);
}
}
else
{
iFoundAt = StringInStringFindFirst(p_cText, p_cSearchText);
}
return 0;
}
Esto no tendrá en cuenta la configuración regional, pero si puede cambiar IS_ALPHA y TO_UPPER, puede hacerlo para considerarlo.
#define IS_ALPHA(c) (((c) >= 'A' && (c) <= 'Z') || ((c) >= 'a' && (c) <= 'z'))
#define TO_UPPER(c) ((c) & 0xDF)
char * __cdecl strstri (const char * str1, const char * str2){
char *cp = (char *) str1;
char *s1, *s2;
if ( !*str2 )
return((char *)str1);
while (*cp){
s1 = cp;
s2 = (char *) str2;
while ( *s1 && *s2 && (IS_ALPHA(*s1) && IS_ALPHA(*s2))?!(TO_UPPER(*s1) - TO_UPPER(*s2)):!(*s1-*s2))
++s1, ++s2;
if (!*s2)
return(cp);
++cp;
}
return(NULL);
}
Si desea deshacerse de los ciclos de CPU, puede considerar esto: supongamos que estamos tratando con ASCII y no con Unicode.
Haz una tabla estática con 256 entradas. Cada entrada en la tabla es de 256 bits.
Para probar si dos caracteres son iguales o no, haces algo como esto:
if (BitLookup(table[char1], char2)) { /* match */ }
Para construir la tabla, establezca un poco en todas partes de la tabla [char1] donde considere que es una coincidencia para char2. Por lo tanto, al construir la tabla, debe establecer los bits en el índice para 'a' y 'A' en la entrada 'a' (y en la entrada 'A').
Ahora esto va a ser lento para hacer la búsqueda de bits (la búsqueda de bits será un desplazamiento, una máscara y una adición más probable), por lo que podría usar una tabla de bytes en lugar de 8 bits para representar 1 bit. Esto tomará 32K, así que, ¡ay, has llegado a una compensación de tiempo / espacio! Podríamos querer que la tabla sea más flexible, así que digamos que hacemos esto en su lugar, la tabla definirá las congruencias en su lugar.
Dos caracteres se consideran congruentes si y solo si hay una función que los define como equivalentes. Así que 'A' y 'a' son congruentes para la insensibilidad a los casos. 'A', '& # 192;', '& # 193;' y '& # 194;' son congruentes para la insensibilidad diacrítica.
Así que define los campos de bits que corresponden a sus congruencias
#define kCongruentCase (1 << 0)
#define kCongruentDiacritical (1 << 1)
#define kCongruentVowel (1 << 2)
#define kCongruentConsonant (1 << 3)
Entonces tu prueba es algo como esto:
inline bool CharsAreCongruent(char c1, char c2, unsigned char congruency)
{
return (_congruencyTable[c1][c2] & congruency) != 0;
}
#define CaseInsensitiveCharEqual(c1, c2) CharsAreCongruent(c1, c2, kCongruentCase)
Por cierto, este tipo de juguetear con tablas gigantes es el corazón de ctype.
Si puedes controlar la cadena de la aguja para que siempre esté en minúsculas, puedes escribir una versión modificada de stristr () para evitar las búsquedas de eso, y así acelerar el código. No es tan general, pero puede ser más rápido, un poco más rápido. Los comentarios similares se aplican al pajar, pero es más probable que lea el pajar de fuentes fuera de su control porque no puede estar seguro de que los datos cumplan con el requisito.
Si la ganancia en el rendimiento vale la pena, es otra pregunta. Para el 99% de las solicitudes, la respuesta es "No, no vale la pena". Su aplicación podría ser una de la pequeña minoría donde importa. Lo más probable es que no lo sea.
