Le moyen le plus rapide de faire une recherche de sous-chaîne insensible à la casse en C / C ++?
https://stackoverflow.com/questions/211535
-
03-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
Remarque
La question ci-dessous a été posée en 2008 à propos de certains codes de 2003. Comme le montre la mise à jour du PO, cet article est totalement obsolète pour les algorithmes du millésime 2008 et persiste ici uniquement à titre de curiosité historique.
Je dois effectuer une recherche rapide de sous-chaînes insensible à la casse en C / C ++. Mes exigences sont les suivantes:
- Devrait se comporter comme strstr () (c.-à-d. retourner un pointeur au point de correspondance).
- Doit être sensible à la casse (doh).
- Doit prendre en charge les paramètres régionaux en cours.
- Doit être disponible sous Windows (MSVC ++ 8.0) ou facilement portable vers Windows (c'est-à-dire depuis une bibliothèque open source).
Voici l'implémentation actuelle que j'utilise (tirée de la bibliothèque 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;
}Pouvez-vous rendre ce code plus rapide ou connaissez-vous une meilleure implémentation?
Remarque: J'ai remarqué que la bibliothèque GNU C dispose désormais de une nouvelle implémentation de strstr () , mais je ne suis pas sûr avec quelle facilité il peut être modifié pour tenir compte de la casse, ou s'il est en fait plus rapide que l'ancien (dans mon cas). J'ai également remarqué que l'ancienne implémentation est toujours utilisée pour les chaînes de caractères larges . Si quelqu'un sait pourquoi, partagez-le.
Mettre à jour
Juste pour clarifier les choses - au cas où ce ne soit pas déjà fait - je n’ai pas écrit cette fonction, elle fait partie de la bibliothèque GNU C. Je ne l'ai modifié que pour tenir compte de la casse.
Merci également pour le conseil relatif à strcasestr () et la vérification d'autres implémentations à partir d'autres sources (telles que OpenBSD, FreeBSD, etc.). Cela semble être la voie à suivre. Le code ci-dessus date de 2003, c'est pourquoi je l'ai posté ici dans l'espoir qu'une meilleure version soit disponible, ce qui est apparemment le cas. :)
La solution
Le code que vous avez publié est environ deux fois moins rapide 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 fonction main était:
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;
}
Il a été modifié pour tester les deux implémentations. Je remarque que, pendant que je tape ceci, je suis parti dans l'appel init_stristr , mais cela ne devrait pas trop changer les choses. bench n'est qu'un simple script shell:
#!/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")
Autres conseils
Vous pouvez utiliser la fonction StrStrI qui trouve la première occurrence d’une sous-chaîne dans une chaîne. La comparaison n'est pas sensible à la casse. N'oubliez pas d'inclure son en-tête - Shlwapi.h. Découvrez ceci: http: // msdn.microsoft.com/en-us/library/windows/desktop/bb773439(v=vs.85).aspx
Pour une utilisation indépendante de la plate-forme:
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;
}
Pourquoi utilisez-vous _strlwr (string); dans init_stristr ()? Ce n'est pas une fonction standard. Je suppose que c'est pour la prise en charge des paramètres régionaux, mais comme ce n'est pas standard, j'utiliserais simplement:
char_table[i] = tolower(i);
utilisez boost string algo . Il est disponible, multiplate-forme, et uniquement un fichier d’en-tête (pas de bibliothèque à relier). Sans compter que vous devriez quand même utiliser boost.
#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;
}
Je vous conseillerais de prendre certaines des implémentations courantes de strcasestr qui existent déjà. Par exemple, glib, glibc, OpenBSD, FreeBSD, etc. Vous pouvez en rechercher davantage avec google.com/codesearch. Vous pouvez ensuite effectuer des mesures de performance et comparer les différentes implémentations.
En supposant que les deux chaînes en entrée sont déjà en minuscules.
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;
}
Vous pouvez également utiliser des masques ... si, par exemple, la plupart des chaînes que vous allez comparer ne contiennent que des caractères de a à z, il est peut-être utile de faire quelque chose comme ça.
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;
}
Alors ...
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;
}
Ceci ne tiendra pas compte des paramètres régionaux, mais si vous pouvez modifier les paramètres IS_ALPHA et TO_UPPER, vous pouvez le prendre en compte.
#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 vous souhaitez supprimer les cycles du processeur, vous pouvez envisager ceci: supposons qu'il s'agisse d'ASCII et non d'Unicode.
Créez une table statique avec 256 entrées. Chaque entrée du tableau est de 256 bits.
Pour vérifier si deux caractères sont égaux ou non, procédez comme suit:
if (BitLookup(table[char1], char2)) { /* match */ }
Pour construire la table, vous définissez un peu partout dans la table [char1] où vous le considérez comme une correspondance pour char2. Ainsi, lors de la construction de la table, vous définissez les bits dans les index pour "a" et "A" dans l'entrée "a" (et l'entrée "A").
Maintenant, la recherche de bits va être lente (la recherche de bits sera un décalage, un masque et l'ajout le plus probable), de sorte que vous pouvez utiliser à la place une table d'octets, de sorte que vous utilisez 8 bits pour représenter 1 bit. Cela prendra 32K - donc hourra - vous avez fait un compromis entre le temps et l'espace! Nous voudrions peut-être rendre la table plus flexible, alors disons que nous le faisons à la place - la table définira plutôt les congruences.
Deux caractères sont considérés congruents si et seulement si une fonction les définit comme équivalents. Donc, 'A' et 'a' sont congruents pour l'insensibilité à la casse. 'A', '& # 192;', '& # 193;' et '& # 194;' sont congruents pour l'insensibilité diacritique.
Vous définissez donc les champs de bits qui correspondent à vos congruences
#define kCongruentCase (1 << 0)
#define kCongruentDiacritical (1 << 1)
#define kCongruentVowel (1 << 2)
#define kCongruentConsonant (1 << 3)
Ensuite, votre test ressemble à ceci:
inline bool CharsAreCongruent(char c1, char c2, unsigned char congruency)
{
return (_congruencyTable[c1][c2] & congruency) != 0;
}
#define CaseInsensitiveCharEqual(c1, c2) CharsAreCongruent(c1, c2, kCongruentCase)
Ce genre de bricolage avec des tables ginormous est le coeur de ctype, par le par.
Si vous pouvez contrôler la chaîne d'aiguille de sorte qu'elle soit toujours en minuscule, vous pouvez écrire une version modifiée de stristr () pour éviter les recherches et ainsi accélérer le code. Ce n'est pas aussi général, mais cela peut être plus rapide - légèrement plus rapide. Des commentaires similaires s'appliquent à la botte de foin, mais vous êtes plus susceptible de lire la botte de foin à partir de sources indépendantes de votre contrôle, car vous ne pouvez pas être sûr que les données répondent à l'exigence.
La question de savoir si le gain en performance vaut la peine est une autre question. Pour 99% des applications, la réponse est "Non, cela ne vaut pas la peine". Votre application est peut-être l’une des très petites minorités où elle compte. Plus probablement, ce n’est pas le cas.
