C / C ++で大文字と小文字を区別しない部分文字列検索を行う最も速い方法は？
https://stackoverflow.com/questions/211535
-
03-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian質問
注
2003年のコードについて、2008年に以下の質問が行われました。OPの更新が示すように、この投稿全体は2008年のビンテージアルゴリズムによって廃止され、歴史的な好奇心としてのみここに保持されます。
C / C ++で大文字と小文字を区別しない高速な部分文字列検索を実行する必要があります。私の要件は次のとおりです。
- strstr（）のように動作する必要があります（つまり、一致ポイントへのポインターを返します）。
- 大文字と小文字を区別しない（doh）。
- 現在のロケールをサポートする必要があります。
- Windows（MSVC ++ 8.0）で利用可能であるか、Windowsに簡単に移植できる必要があります（つまり、オープンソースライブラリから）。
これは私が使用している現在の実装です（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;
}このコードを高速化できますか、またはより良い実装を知っていますか？
注： GNU Cライブラリには strstr（） の新しい実装ですが、よくわかりません大文字と小文字を区別しないように簡単に変更できるか、実際に古いものよりも高速である場合（私の場合）。また、ワイド文字列には古い実装が引き続き使用されています。だれかが理由を知っている場合は、共有してください。
更新
わかりやすくするために、＆＃8212;この関数をまだ作成していない場合は、GNU Cライブラリの一部です。大文字と小文字を区別しないように変更しただけです。
また、 strcasestr（）に関するヒントと、他のソース（OpenBSD、FreeBSDなど）からの他の実装をチェックしてくれてありがとう。それが進むべき道のようです。上記のコードは2003年のものであるため、より良いバージョンが利用可能になることを期待してここに投稿しました。 ：）
解決
投稿したコードは、 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
main 関数は次のとおりです。
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;
}
両方の実装をテストするために適切に修正されました。これを入力しているので、 init_stristr 呼び出しに残しましたが、あまり変更しないでください。 bench は単なるシェルスクリプトです：
#!/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")
他のヒント
StrStrI関数を使用して、文字列内の最初の部分文字列を検索できます。比較では大文字と小文字は区別されません。 ヘッダー-Shlwapi.hを含めることを忘れないでください。 これを確認してください： http：// msdn.microsoft.com/en-us/library/windows/desktop/bb773439(v=vs.85).aspx
プラットフォームに依存しない使用の場合：
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;
}
_strlwr（string）;を使用する理由init_stristr（）で？これは標準機能ではありません。おそらくロケールのサポート用ですが、標準ではないので、私はただ使用します：
char_table[i] = tolower(i);
ストリングアルゴリズムをブーストします。クロスプラットフォームで利用可能で、ヘッダーファイルのみです（リンクするライブラリはありません）。とにかくブーストを使用する必要があることは言うまでもありません。
#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;
}
すでに存在する一般的なstrcasestr実装をいくつか使用することをお勧めします。たとえば、glib、glibc、OpenBSD、FreeBSDなど。google.com/ codesearchで詳細を検索できます。その後、いくつかのパフォーマンス測定を行い、異なる実装を比較できます。
両方の入力文字列がすでに小文字であると仮定します。
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;
}
マスクを使用することもできます。たとえば、比較する文字列のほとんどにa〜zの文字しか含まれていない場合は、このようなことをする価値があるかもしれません。
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;
}
その後...
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;
}
これはロケールを考慮しませんが、IS_ALPHAとTO_UPPERを変更できる場合は、考慮に入れることができます。
#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);
}
CPUサイクルを削減したい場合、これを検討するかもしれません-UnicodeではなくASCIIを扱っていると仮定しましょう。
256エントリの静的テーブルを作成します。テーブルの各エントリは256ビットです。
2つの文字が等しいかどうかをテストするには、次のようにします：
if (BitLookup(table[char1], char2)) { /* match */ }
テーブルを作成するには、table [char1]のどこでも、char2と一致すると見なすビットをすべて設定します。したがって、テーブルを構築する際には、「a」番目のエントリ（および「A」番目のエントリ）の「a」および「A」のインデックスにビットを設定します。
これでビット検索が遅くなります（ビット検索はシフト、マスク、および加算である可能性が高いため）代わりにバイトのテーブルを使用して、8ビットを使用して1ビットを表すことができます。これには32Kがかかります。つまり、時間とスペースのトレードオフが発生しています。テーブルをより柔軟にしたい場合があるので、代わりにこれを行うとしましょう-テーブルは代わりに合同を定義します。
2つの文字は、それらを同等と定義する関数が存在する場合にのみ、合同と見なされます。したがって、「A」と「a」は大文字と小文字を区別しません。 「A」、「＆＃192;」、「＆＃193;」および「＆＃194;」発音区別の区別がないことを示しています。
したがって、一致に対応するビットフィールドを定義します
#define kCongruentCase (1 << 0)
#define kCongruentDiacritical (1 << 1)
#define kCongruentVowel (1 << 2)
#define kCongruentConsonant (1 << 3)
その後、テストは次のようになります：
inline bool CharsAreCongruent(char c1, char c2, unsigned char congruency)
{
return (_congruencyTable[c1][c2] & congruency) != 0;
}
#define CaseInsensitiveCharEqual(c1, c2) CharsAreCongruent(c1, c2, kCongruentCase)
この種類の巨大なテーブルをいじるのは、by by by ctypeの心臓部です。
針文字列を常に小文字になるように制御できる場合は、stristr（）の修正バージョンを記述して、その検索を回避し、コードを高速化できます。それほど一般的ではありませんが、より高速にすることができます-わずかに高速です。同様のコメントが干し草の山にも適用されますが、データが要件を満たしているかどうかを確認できないため、制御外のソースから干し草の山を読んでいる可能性が高くなります。
パフォーマンスの向上に価値があるかどうかは、まったく別の質問です。 99％のアプリケーションにとって、答えは「いいえ、価値がありません」です。あなたのアプリケーションは、それが重要な小さな少数派の1つかもしれません。おそらくそうではありません。
