Schnellster Weg, um eine Groß- und Kleinschreibung String-Suche in C / C ++ zu tun?

https://stackoverflow.com/questions/211535

03-07-2019
|

Frage

Hinweis

Die Frage unten im Jahr 2008 über einige Codes aus dem Jahr 2003. Da die OP Update zeigt gebeten wurde, dieser ganzer Beitrag wird von Jahrgang 2008 Algorithmen und bleibt hier nur noch als historische Kuriosität holt worden ist.

Ich brauche eine schnelle Groß- und Kleinschreibung String-Suche in C / C ++ zu tun. Meine Anforderungen sind wie folgt:

Sollte wie strstr verhalten () (das heißt einen Zeiger auf den Matchpunkt).
muss Groß- und Kleinschreibung (DOH).
muss die aktuellen locale unterstützen.
muss auf Windows (MSVC ++ 8.0) oder leicht zu transportieren, um Windows (das heißt von einer Open-Source-Bibliothek).

Hier ist die aktuelle Implementierung verwende ich (von der GNU C Library genommen):

/* 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;
}

Können Sie diesen Code schneller machen, oder kennen Sie eine bessere Umsetzung?

Hinweis: Ich habe bemerkt, dass das GNU C Library hat jetzt eine neue Implementierung von strstr() , aber ich bin nicht sicher, wie leicht es modifiziert werden, so zu sein -insensitive, oder wenn es in der Tat schneller als die alten (in meinem Fall). Ich habe auch bemerkt, dass

Lösung

Der Code, den Sie geschrieben ist etwa halb so schnell wie 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

Die main Funktion war:

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

Es wurde in geeigneter Weise modifiziert beide Implementierungen zu testen. Ich merke, wie ich dies bis tippe ich in dem init_stristr Anruf verlassen, aber es sollte nicht viele Dinge ändern. bench ist nur ein einfacher Shell-Skript:

#!/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")

Andere Tipps

Sie können StrStrI Funktion verwenden, die das erste Vorkommen eines Teilstrings in einem String findet. Der Vergleich ist nicht abhängig. Vergessen Sie nicht, ihre Header enthalten - Shlwapi.h. Check this out: http: // msdn.microsoft.com/en-us/library/windows/desktop/bb773439(v=vs.85).aspx

Für plattformunabhängige Nutzung:

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

Warum verwenden Sie _strlwr (string); in init_stristr ()? Es ist keine Standardfunktion. Vermutlich ist es für locale-Unterstützung, aber da es nicht Standard ist, würde ich nur verwenden:

char_table[i] = tolower(i);

Boost-String algo . Es ist möglich, Cross-Plattform, und nur eine Header-Datei (keine Bibliothek verknüpfen in). Ganz zu schweigen davon, dass Sie boost sowieso verwenden sollten.

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

Ich würde empfehlen Sie einige der gemeinsamen strcasestr Umsetzung zu ergreifen, die bereits vorhanden ist. Zum Beispiel von glib, glibc, OpenBSD, FreeBSD, etc. Sie können mehr mit google.com/codesearch suchen. Sie können dann einige Performance-Messungen und die andere Implementierung vergleichen.

Unter der Annahme, beide Eingabezeichenfolgen sind bereits Kleinbuchstaben.

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

Sie könnten auch versuchen, Masken ... wenn zum Beispiel der meisten der Saiten Sie nur Zeichen enthält von a bis z gehen zu vergleichen, vielleicht ist es wert, so etwas zu tun.

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

Dann ...

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

Dies wird das Gebietsschema nicht betrachten, aber wenn Sie die IS_ALPHA ändern und to_upper Sie können es machen es zu berücksichtigen.

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

Wenn Sie die CPU-Zyklen vergießen wollen, könnte man dies berücksichtigen -. Nehmen wir an, dass wir mit ASCII und Unicode nicht es zu tun

Erstellen Sie eine statische Tabelle mit 256 Einträgen. Jeder Eintrag in der Tabelle ist 256 Bit.

Um zu testen, ob zwei Zeichen gleich sind, können Sie etwas tun, wie folgt aus:

if (BitLookup(table[char1], char2)) { /* match */ }

, um die Tabelle zu erstellen, setzen Sie ein wenig überall in der Tabelle [char1], wo Sie es ein Spiel für char2 betrachten. So die Tabelle in dem Aufbau Sie die Bits in dem Index für ‚a‘ gesetzt würden und ‚A‘ in dem ‚a'th Eintrag (und der‘ A'th Eintrag).

Nun ist diese slowish sein wird, die Bit-Lookup zu tun (Bit nachschlagen wird eine Verschiebung, Maske und fügen Sie höchstwahrscheinlich), so dass Sie stattdessen eine Tabelle von Bytes verwenden könnte, so dass Sie 8 Bit verwenden 1 Bit zu repräsentieren. Dies wird 32K nehmen - so hurra - Sie eine Zeit / Raum-Trade-off getroffen haben! Wir wollen könnte der Tisch flexibler machen, also lassen Sie uns sagen, dass wir das tun, statt -. Die Tabelle statt Kongruenzen definieren

Zwei Zeichen werden als kongruent, wenn und nur wenn es eine Funktion, die sie als gleichwertig definiert. So ‚A‘ und ‚a‘ sind deckungsgleich für Groß- und Kleinschreibung. ‚A‘, ‚A‘, ‚A‘ und ‚A‘ sind deckungsgleich für diakritische Unempfindlichkeit.

So Sie bitfields definieren, die zu Ihrem Kongruenzen entsprechen

#define kCongruentCase (1 << 0)
#define kCongruentDiacritical (1 << 1)
#define kCongruentVowel (1 << 2)
#define kCongruentConsonant (1 << 3)

Dann wird Ihr Test ist so etwas wie folgt aus:

inline bool CharsAreCongruent(char c1, char c2, unsigned char congruency)
{
    return (_congruencyTable[c1][c2] & congruency) != 0;
}

#define CaseInsensitiveCharEqual(c1, c2) CharsAreCongruent(c1, c2, kCongruentCase)

Diese Art von Bit mit ginormous Tabellen Hantieren ist das Herz der ctype, die durch.

Wenn Sie die Nadel Zeichenfolge steuern kann, so dass es immer in Kleinbuchstaben, dann können Sie eine modifizierte Version von stristr () schreiben, um die Lookups für das zu vermeiden und damit den Code beschleunigen. Es ist nicht so allgemein, aber es kann schneller sein - etwas schneller. Ähnliche Kommentare gelten für den Heuhaufen, aber sie sind eher die Heuhaufen aus Quellen außerhalb Ihrer Kontrolle zu lesen für Sie nicht sicher sein kann, dass die Daten, die die Anforderung erfüllt.

Ob der Performance-Gewinn ist es wert ist eine ganz andere Frage. Für 99% der Anwendungen ist die Antwort „Nein, es ist es nicht wert“. Ihre Anwendung könnte eine der winzigen Minderheit sein, wo es darauf ankommt. Wahrscheinlicher ist, dass es nicht ist.

Lizenziert unter: CC-BY-SA mit Zuschreibung

Nicht verbunden mit StackOverflow