# 練習39：字符串算法 > 原文：[Exercise 39: String Algorithms](http://c.learncodethehardway.org/book/ex39.html) > 譯者：[飛龍](https://github.com/wizardforcel) 這個練習中，我會向你展示可能是最快的字符串搜索算法之一，并且將它與`bstrlib.c`中現有的`binstr`比較。`binstr`的文檔說它僅僅使用了“暴力搜索”的字符串算法來尋找第一個實例。我所實現的函數使用Boyer-Moore-Horspool（BMH）算法，如果你分析理論時間的話，一般認為它會更快。你也會看到，如果我的實現沒有任何缺陷，BMH的實際時間會比`binstr`簡單的暴力搜索更糟。 這個練習的要點并不是真正解釋算法本身，因為你可以直接去[Boyer-Moore-Horspool 的維基百科頁面](http://en.wikipedia.org/wiki/Boyer%E2%80%93Moore%E2%80%93Horspool_algorithm)去閱讀它。這個算法的要點就是它會計算出“跳躍字符列表”作為第一步操作，之后它使用這個列表來快速掃描整個字符串。它應當比暴力搜索更快，所以讓我們在文件里寫出代碼來看看吧。 首先，創建頭文件： ```c #ifndef string_algos_h #define string_algos_h #include <lcthw/bstrlib.h> #include <lcthw/darray.h> typedef struct StringScanner { bstring in; const unsigned char *haystack; ssize_t hlen; const unsigned char *needle; ssize_t nlen; size_t skip_chars[UCHAR_MAX + 1]; } StringScanner; int String_find(bstring in, bstring what); StringScanner *StringScanner_create(bstring in); int StringScanner_scan(StringScanner *scan, bstring tofind); void StringScanner_destroy(StringScanner *scan); #endif ``` 為了觀察“跳躍字符列表”的效果，我打算創建這個算法的兩種版本： String_find 只是在一個字符串中，尋找另一個字符串的首個實例，以一個動作執行整個算法。 StringScanner_scan 使用`StringScanner`狀態結構，將跳躍列表的構建和實際的查找操作分開。這讓我能看到什么影響了性能。這個模型有另一個優點，就是我可以在一個字符串中逐步搜索，并且快速地找到所有實例。 一旦你完成了頭文件，下面就是實現了： ```c #include <lcthw/string_algos.h> #include <limits.h> static inline void String_setup_skip_chars( size_t *skip_chars, const unsigned char *needle, ssize_t nlen) { size_t i = 0; size_t last = nlen - 1; for(i = 0; i < UCHAR_MAX + 1; i++) { skip_chars[i] = nlen; } for (i = 0; i < last; i++) { skip_chars[needle[i]] = last - i; } } static inline const unsigned char *String_base_search( const unsigned char *haystack, ssize_t hlen, const unsigned char *needle, ssize_t nlen, size_t *skip_chars) { size_t i = 0; size_t last = nlen - 1; assert(haystack != NULL && "Given bad haystack to search."); assert(needle != NULL && "Given bad needle to search for."); check(nlen > 0, "nlen can't be <= 0"); check(hlen > 0, "hlen can't be <= 0"); while (hlen >= nlen) { for (i = last; haystack[i] == needle[i]; i--) { if (i == 0) { return haystack; } } hlen -= skip_chars[haystack[last]]; haystack += skip_chars[haystack[last]]; } error: // fallthrough return NULL; } int String_find(bstring in, bstring what) { const unsigned char *found = NULL; const unsigned char *haystack = (const unsigned char *)bdata(in); ssize_t hlen = blength(in); const unsigned char *needle = (const unsigned char *)bdata(what); ssize_t nlen = blength(what); size_t skip_chars[UCHAR_MAX + 1] = {0}; String_setup_skip_chars(skip_chars, needle, nlen); found = String_base_search(haystack, hlen, needle, nlen, skip_chars); return found != NULL ? found - haystack : -1; } StringScanner *StringScanner_create(bstring in) { StringScanner *scan = calloc(1, sizeof(StringScanner)); check_mem(scan); scan->in = in; scan->haystack = (const unsigned char *)bdata(in); scan->hlen = blength(in); assert(scan != NULL && "fuck"); return scan; error: free(scan); return NULL; } static inline void StringScanner_set_needle(StringScanner *scan, bstring tofind) { scan->needle = (const unsigned char *)bdata(tofind); scan->nlen = blength(tofind); String_setup_skip_chars(scan->skip_chars, scan->needle, scan->nlen); } static inline void StringScanner_reset(StringScanner *scan) { scan->haystack = (const unsigned char *)bdata(scan->in); scan->hlen = blength(scan->in); } int StringScanner_scan(StringScanner *scan, bstring tofind) { const unsigned char *found = NULL; ssize_t found_at = 0; if(scan->hlen <= 0) { StringScanner_reset(scan); return -1; } if((const unsigned char *)bdata(tofind) != scan->needle) { StringScanner_set_needle(scan, tofind); } found = String_base_search( scan->haystack, scan->hlen, scan->needle, scan->nlen, scan->skip_chars); if(found) { found_at = found - (const unsigned char *)bdata(scan->in); scan->haystack = found + scan->nlen; scan->hlen -= found_at - scan->nlen; } else { // done, reset the setup StringScanner_reset(scan); found_at = -1; } return found_at; } void StringScanner_destroy(StringScanner *scan) { if(scan) { free(scan); } } ``` 整個算法都在兩個`static inline`的函數中，叫做`String_setup_skip_chars` 和 `String_base_search`。它們在別的函數中使用，用于實現我想要的的搜索形式。研究這兩個函數，并且與維基百科的描述對比，你就可以知道它的工作原理。 之后`String_find`使用這兩個函數來尋找并返回所發現的位置。它非常簡單并且我使用它來查看“跳躍字符列表”的構建如何影響到真實性能。要注意，你或許可以使它更快，但是我要教給你在你實現算法之后如何驗證理論速度。 `StringScanner_scan`函數隨后按照“創建、掃描、銷毀”的常用模式，并且用于在一個字符串中逐步搜索另一個字符串。當我向你展示單元測試的時候，你會看到它如何使用。 最后，我編寫了單元測試來確保算法有效，之后在它的注釋部分，我為三個搜索函數運行了簡單的性能測試： ```c #include "minunit.h" #include <lcthw/string_algos.h> #include <lcthw/bstrlib.h> #include <time.h> struct tagbstring IN_STR = bsStatic("I have ALPHA beta ALPHA and oranges ALPHA"); struct tagbstring ALPHA = bsStatic("ALPHA"); const int TEST_TIME = 1; char *test_find_and_scan() { StringScanner *scan = StringScanner_create(&IN_STR); mu_assert(scan != NULL, "Failed to make the scanner."); int find_i = String_find(&IN_STR, &ALPHA); mu_assert(find_i > 0, "Failed to find 'ALPHA' in test string."); int scan_i = StringScanner_scan(scan, &ALPHA); mu_assert(scan_i > 0, "Failed to find 'ALPHA' with scan."); mu_assert(scan_i == find_i, "find and scan don't match"); scan_i = StringScanner_scan(scan, &ALPHA); mu_assert(scan_i > find_i, "should find another ALPHA after the first"); scan_i = StringScanner_scan(scan, &ALPHA); mu_assert(scan_i > find_i, "should find another ALPHA after the first"); mu_assert(StringScanner_scan(scan, &ALPHA) == -1, "shouldn't find it"); StringScanner_destroy(scan); return NULL; } char *test_binstr_performance() { int i = 0; int found_at = 0; unsigned long find_count = 0; time_t elapsed = 0; time_t start = time(NULL); do { for(i = 0; i < 1000; i++) { found_at = binstr(&IN_STR, 0, &ALPHA); mu_assert(found_at != BSTR_ERR, "Failed to find!"); find_count++; } elapsed = time(NULL) - start; } while(elapsed <= TEST_TIME); debug("BINSTR COUNT: %lu, END TIME: %d, OPS: %f", find_count, (int)elapsed, (double)find_count / elapsed); return NULL; } char *test_find_performance() { int i = 0; int found_at = 0; unsigned long find_count = 0; time_t elapsed = 0; time_t start = time(NULL); do { for(i = 0; i < 1000; i++) { found_at = String_find(&IN_STR, &ALPHA); find_count++; } elapsed = time(NULL) - start; } while(elapsed <= TEST_TIME); debug("FIND COUNT: %lu, END TIME: %d, OPS: %f", find_count, (int)elapsed, (double)find_count / elapsed); return NULL; } char *test_scan_performance() { int i = 0; int found_at = 0; unsigned long find_count = 0; time_t elapsed = 0; StringScanner *scan = StringScanner_create(&IN_STR); time_t start = time(NULL); do { for(i = 0; i < 1000; i++) { found_at = 0; do { found_at = StringScanner_scan(scan, &ALPHA); find_count++; } while(found_at != -1); } elapsed = time(NULL) - start; } while(elapsed <= TEST_TIME); debug("SCAN COUNT: %lu, END TIME: %d, OPS: %f", find_count, (int)elapsed, (double)find_count / elapsed); StringScanner_destroy(scan); return NULL; } char *all_tests() { mu_suite_start(); mu_run_test(test_find_and_scan); // this is an idiom for commenting out sections of code #if 0 mu_run_test(test_scan_performance); mu_run_test(test_find_performance); mu_run_test(test_binstr_performance); #endif return NULL; } RUN_TESTS(all_tests); ``` 我把它們寫在`#if 0`中間，它是使用C預處理器來注釋一段代碼的方法。像這樣輸入，并且把它和`#endif`移除，你就可以運行性能測試。當你繼續這本書時，需要簡單地把它們再次注釋，以防它們浪費你的開發時間。 這個單元測試沒有什么神奇之處，它只是在尊換種調用每個不同的函數，循環需要持續足夠長的時間來得到一個幾秒的樣本。第一個測試（`test_find_and_scan`）只是確保我所編寫的代碼正常工作，因為測試無效的代碼沒有意義。之后，下面的三個函數使用三個函數中的每一個來執行大量的搜索。 需要注意的一個技巧是，我在`start`中存儲了起始時間，之后一直循環到至少過了`TEST_TIME`秒。這確保了我能或得到足夠好的樣本用于比較三者。我之后會使用不同的`TEST_TIME`設置來運行測試，并且分析結果。 ## 你會看到什么 當我在我的筆記本上運行測試時，我得到的數據是這樣的： ```sh $ ./tests/string_algos_tests DEBUG tests/string_algos_tests.c:124: ----- RUNNING: ./tests/string_algos_tests ---- RUNNING: ./tests/string_algos_tests DEBUG tests/string_algos_tests.c:116: ----- test_find_and_scan DEBUG tests/string_algos_tests.c:117: ----- test_scan_performance DEBUG tests/string_algos_tests.c:105: SCAN COUNT: 110272000, END TIME: 2, OPS: 55136000.000000 DEBUG tests/string_algos_tests.c:118: ----- test_find_performance DEBUG tests/string_algos_tests.c:76: FIND COUNT: 12710000, END TIME: 2, OPS: 6355000.000000 DEBUG tests/string_algos_tests.c:119: ----- test_binstr_performance DEBUG tests/string_algos_tests.c:54: BINSTR COUNT: 72736000, END TIME: 2, OPS: 36368000.000000 ALL TESTS PASSED Tests run: 4 $ ``` 我看到了它，覺得每輪運行應該超過兩秒。并且，我打算多次運行它，并且像之前一樣使用R來驗證。下面是我獲得的10個樣例，每個基本上是10秒： ```r scan find binstr 71195200 6353700 37110200 75098000 6358400 37420800 74910000 6351300 37263600 74859600 6586100 37133200 73345600 6365200 37549700 74754400 6358000 37162400 75343600 6630400 37075000 73804800 6439900 36858700 74995200 6384300 36811700 74781200 6449500 37383000 ``` 我在shell的一點點幫助下獲取數據，之后編輯輸出： ```shell $ for i in 1 2 3 4 5 6 7 8 9 10; do echo "RUN --- $i" >> times.log; ./tests/string_algos_tests 2>&1 | grep COUNT >> times.log ; done $ less times.log $ vim times.log ``` 現在你可以看到`scan`系統要優于另外兩個，但是我會在R中打開它并且驗證結果： ```rebol > times <- read.table("times.log", header=T) > summary(times) scan find binstr Min. :71195200 Min. :6351300 Min. :36811700 1st Qu.:74042200 1st Qu.:6358100 1st Qu.:37083800 Median :74820400 Median :6374750 Median :37147800 Mean :74308760 Mean :6427680 Mean :37176830 3rd Qu.:74973900 3rd Qu.:6447100 3rd Qu.:37353150 Max. :75343600 Max. :6630400 Max. :37549700 > ``` 為了理解我為什么要生成這份概要統計，我必須對你解釋一些統計學概念。我在這些數字中尋找的東西能夠簡單地告訴我，“這三個函數（`scan`、`find`、`binstr`）實際上不同嗎？”我知道每次我運行測試函數的時候，我都會得到有些不同的數值，并且那些數值始終處理一個固定的范圍。你可以看到兩個四分位數反映了這一點。 我首先會去看均值，并且我會觀察每個樣例的均值是否不同于其它的。我可以清楚地看到`scan`優于`binstr`，同時后者優于`find`。然而問題來了，如果我只使用均值，就可以出現每個樣例的范圍會重疊的可能性。 如果均值不同，但是兩個四分位點重疊會怎么用？這種情況下我只能說有這種可能性，并且如果我再次運行測試，均值就可能不同了。很可能出現的范圍上的重疊是，我的兩個樣例（以及兩個函數）并非實際上不同。任何我看到的差異都是隨機產生的結果。 統計學擁有大量工具來解決這一問題，但是在我們的例子中我可以僅僅觀察兩個四分位值，以及所有樣例的均值。如果均值不同，并且四分位值不可能重疊，就可以說它們完全不同。 在我的三個樣例中，我可以說`scan`、`find`和`binstr`都是不同的，范圍上沒有重疊，并且（最重要的是）我可以相信數據。 ## 分析結果 從結果中可以看出`String_find`比其它兩個更慢。實際上，我認為慢的原因是我實現的方式有些問題。然而當我將它與`StringScanner_scan`比較時，我發現正是構造跳躍列表的那一部分最消耗時間。并且它的功能比`scan`要少，因為它僅僅找到了第一個位置，而`scan`找到了全部。 我也可以發現`scan`以很大優勢優于`binstr`。同時我可以說`scan`的功能比其他兩個要多，速度也更快。 下面是這個分析的一些注解： + 我可能將實現或測試弄亂了。現在我打算研究所有實現BMH的可能方式來改進它。我也會確保我所做的事情正確。 + 如果你修改了測試運行的時間，你會得到不同的結果。這就是我沒有考慮的”熱身“環節。 + `test_scan_performance`單元測試和其它兩個并不相同，但是它比其它測試做得更多（并且也是按照時間和操作數量計算的），所以他可能是合理的。 + 我只通過在一個字符串內搜索另一個來執行測試。我應該使所查找的字符串隨機化，來移除它們的位置和長度，作為干擾因素。 + `binstr`的實現可能比“暴力搜索”要好。（所以應該自己編寫暴力搜索作為對照。） + 我可能以不幸的順序來執行這些函數，并且隨機化首先運行的測試可能會得到更好的結果。 可以從中學到的是，你需要確保知己的性能，即使你“正確”實現了一個算法。在這里BMH算法應該優于`binstr`算法，但是一個簡單的測試證明了它是錯誤。如果我沒有這些測試，我可能就使用了一個劣等的算法實現而不自知。參照這些度量，我可以開始調優我的實現，或者只是拋棄它并尋找新的算法。 ## 附加題 + 看看你能不能使`Scan_find`更快。為什么我的實現這么慢？ + 嘗試一些不同的搜索時長，看看你是否能得到不同的數值。當你改變`scan`的測試時間時，時間的長度會有什么影響？對于這些結果你能得出什么結論？ + 修改單元測試，使它最開始執行每個函數一小段時間，來消除任何“熱身”緩解。這樣會修改所運行時長的依賴性嗎？每秒可能出現多少次操作？ + 使單元測試中的所查找字符串隨機化，之后測量你的得到的性能。一種實現它的方式就是使用`bstrlib.h`中的`bsplit`函數在空格處分割`IN_STR`。之后使用你得到的`strList`結構訪問它返回的每個字符串。這也教給你如何使用`bstrList`操作進行字符串處理。 + 嘗試一些不同順序的測試，看看能否得到不同的結果。