以前以為 strstr 不是標準函式庫,最近才發現原來它是標準的。先放上一個範例出來

 

strstr 使用範例
  1. #include <string.h>
  2. #include <stdio.h>
  3.  
  4. int main()
  5. {
  6.     const char * str = "abcabcabaabccabcab";
  7.     const char * pattern = "bcab";
  8.  
  9.     char *ret = strstr(str, pattern);
  10.     while(ret){
  11.         printf("find \"%s\" at position : %u\n", pattern, ret - str);
  12.         ret = strstr(ret+1, pattern);
  13.     }
  14.     getchar();
  15.     return 0;
  16. }

 

輸出結果如下

find "bcab" at position : 1
find "bcab" at position : 4
find "bcab" at position : 14

 

幾份實作

 

完全不調用 string library 的作法

 

bf_strstr
  1. char * bf_strstr ( const char * str1, const char * str2)
  2. {
  3.     char *cp = (char *) str1;
  4.     char *s1, *s2;
  5.  
  6.     if ( !*str2 ) return((char *)str1);
  7.     while (*cp)    {
  8.         s1 = cp;
  9.         s2 = (char *) str2;
  10.         while ( *s1 && *s2 && (*s1==*s2) ) ++s1, ++s2;
  11.  
  12.         if (!*s2) return(cp);
  13.         cp++;
  14.     }
  15.     return(NULL);
  16. }

 

"疑似" g++ 作法,使用 strchr,再調用 strncmp

 

gpp_strstr
  1. char * gpp_strstr ( const char * s1, const char * s2)
  2. {
  3.     register char *p = s1;
  4.     register int len = strlen (s2);
  5.     for (; (p = strchr (p, *s2)); p++)
  6.         if (strncmp (p, s2, len) == 0)
  7.             return p;
  8.     return NULL;
  9. }

 

其他 KMP 之類的演算法不適合在這篇文討論,就不放上了。

 

沒特殊需求不要自己重刻 string.h

 

 

strcmp、strncmp、strcpy、strncpy ,這幾個函式其實在網路上都找得到很簡單的 sample code,筆者也在另一篇  [C] C-Style string.h 部份函式實作 裡給了十五份常見到的 code。

然後要強調的是,上面給的都只是網路上查得到、給初學者看、初學者用、效能很差的 code ,光是想到可以針對 aliignment 後,1 次 4 bytes 或 8 btyes 方式做寫入、取出,這技巧應該就可加速不少,這部份實作和 memcpy、memchr 很像,有興趣加速自己寫的玩具,應是先研究這兩個 library 才對,就算寫出來可能也沒比較快 ( 這種技巧真的是廣為人知,何況實作的時候可能是以組語實作) ,這裡就不再贅述。

 

效率?

 

接下來討論效率的問題。一般來講上述給的三個 (內建 strstr、純暴力、g++ 所用) 之複雜度都是 O(m * n),而 KMP 複雜度為 O(m+n),但不少人反應,實際上在用的時候 KMP 比 strstr 還慢 "不少" 。

 

雖筆者不知這些測試是怎來的,但猜測測資來源是實際資料,而不是像教科書上寫的、上面範例給的 abcaaabcaabca... 這種較特殊之字串 ( 在猜這種編碼大概只存在於基因編碼之類的吧 ),導致 pattern 在比對時才會近似於 O(m*n)。

 

但一般在使用搜尋文章字串時,一方面文章量並不非常大,就算文章量很大好了 ( 一本書的 pdf ),出現上述之字串機會應該不多,甚至光是「第一個字母」相同的機會就不多,KMP 發揮之空間有限 (倒是前置處理可能都是浪費時間) ;即使該字串出現機會很多,像是英文字母的 is、A 、The、This 等這種常見單字,考慮到 cache hit 問題,再考慮 KMP 調整方式,KMP 也不見得快到哪去。

edisonx 發表在 痞客邦 PIXNET 留言(1) 人氣()


留言列表 (1)

發表留言
  • novus
  • 我最近打算重刻一些舊文,很巧第一篇就和文字有關,如果有空幫忙試讀一下
    http://novus.pixnet.net/blog/post/30371481

    現在想要正確處理文字必須考慮很多事情,C/C++ 在這方面提供的協助非常少。
  • 那篇寫得真的很讚!在您發文的第一天我就細閱了一遍,然後剛又上去看了一下,似乎有些東西有小修過。

    我看完該文馬上想到早期遇到的兩個問題,整理後將回覆在該文底下, novus 大可參考一下 :)

    edisonx 於 2012/12/26 22:28 回覆

您尚未登入,將以訪客身份留言。亦可以上方服務帳號登入留言

請輸入暱稱 ( 最多顯示 6 個中文字元 )

請輸入標題 ( 最多顯示 9 個中文字元 )

請輸入內容 ( 最多 140 個中文字元 )

請輸入左方認證碼:

看不懂,換張圖

請輸入驗證碼