練習39：字符串算法

原文：Exercise 39: String Algorithms

譯者：飛龍

這個練習中，我會向你展示可能是最快的字符串搜索算法之一，并且將它與bstrlib.c中現有的binstr比較。binstr的文檔說它僅僅使用了“暴力搜索”的字符串算法來尋找第一個實例矾湃。我所實現的函數使用Boyer-Moore-Horspool（BMH）算法恼蓬，如果你分析理論時間的話惊完，一般認為它會更快。你也會看到处硬，如果我的實現沒有任何缺陷小槐，BMH的實際時間會比binstr簡單的暴力搜索更糟。

這個練習的要點并不是真正解釋算法本身荷辕，因為你可以直接去Boyer-Moore-Horspool 的維基百科頁面去閱讀它凿跳。這個算法的要點就是它會計算出“跳躍字符列表”作為第一步操作，之后它使用這個列表來快速掃描整個字符串疮方。它應當比暴力搜索更快控嗜，所以讓我們在文件里寫出代碼來看看吧。

首先骡显，創(chuàng)建頭文件：

#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

為了觀察“跳躍字符列表”的效果疆栏，我打算創(chuàng)建這個算法的兩種版本：

String_find

只是在一個字符串中，尋找另一個字符串的首個實例惫谤，以一個動作執(zhí)行整個算法壁顶。

StringScanner_scan

使用StringScanner狀態(tài)結構，將跳躍列表的構建和實際的查找操作分開溜歪。這讓我能看到什么影響了性能若专。這個模型有另一個優(yōu)點，就是我可以在一個字符串中逐步搜索痹愚，并且快速地找到所有實例富岳。

一旦你完成了頭文件，下面就是實現了：

#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使用這兩個函數來尋找并返回所發(fā)現的位置。它非常簡單并且我使用它來查看“跳躍字符列表”的構建如何影響到真實性能爬早。要注意哼丈，你或許可以使它更快，但是我要教給你在你實現算法之后如何驗證理論速度筛严。

StringScanner_scan函數隨后按照“創(chuàng)建醉旦、掃描、銷毀”的常用模式，并且用于在一個字符串中逐步搜索另一個字符串车胡。當我向你展示單元測試的時候檬输，你會看到它如何使用。

最后匈棘，我編寫了單元測試來確保算法有效丧慈，之后在它的注釋部分，我為三個搜索函數運行了簡單的性能測試：

#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移除簇搅，你就可以運行性能測試笑旺。當你繼續(xù)這本書時，需要簡單地把它們再次注釋馍资，以防它們浪費你的開發(fā)時間筒主。

這個單元測試沒有什么神奇之處，它只是在尊換種調用每個不同的函數鸟蟹，循環(huán)需要持續(xù)足夠長的時間來得到一個幾秒的樣本乌妙。第一個測試（test_find_and_scan）只是確保我所編寫的代碼正常工作，因為測試無效的代碼沒有意義建钥。之后藤韵，下面的三個函數使用三個函數中的每一個來執(zhí)行大量的搜索。

需要注意的一個技巧是熊经，我在start中存儲了起始時間泽艘，之后一直循環(huán)到至少過了TEST_TIME秒。這確保了我能或得到足夠好的樣本用于比較三者镐依。我之后會使用不同的TEST_TIME設置來運行測試匹涮，并且分析結果。

你會看到什么

當我在我的筆記本上運行測試時槐壳，我得到的數據是這樣的：

$ ./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秒：

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的一點點幫助下獲取數據吨灭，之后編輯輸出：

$ 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系統(tǒng)要優(yōu)于另外兩個，但是我會在R中打開它并且驗證結果：

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

為了理解我為什么要生成這份概要統(tǒng)計刑巧，我必須對你解釋一些統(tǒng)計學概念喧兄。我在這些數字中尋找的東西能夠簡單地告訴我无畔，“這三個函數（scan、find繁莹、binstr）實際上不同嗎檩互？”我知道每次我運行測試函數的時候，我都會得到有些不同的數值咨演，并且那些數值始終處理一個固定的范圍闸昨。你可以看到兩個四分位數反映了這一點。

我首先會去看均值薄风，并且我會觀察每個樣例的均值是否不同于其它的饵较。我可以清楚地看到scan優(yōu)于binstr，同時后者優(yōu)于find遭赂。然而問題來了循诉，如果我只使用均值，就可以出現每個樣例的范圍會重疊的可能性撇他。

如果均值不同茄猫，但是兩個四分位點重疊會怎么用？這種情況下我只能說有這種可能性困肩，并且如果我再次運行測試划纽，均值就可能不同了。很可能出現的范圍上的重疊是锌畸，我的兩個樣例（以及兩個函數）并非實際上不同勇劣。任何我看到的差異都是隨機產生的結果。

統(tǒng)計學擁有大量工具來解決這一問題潭枣，但是在我們的例子中我可以僅僅觀察兩個四分位值比默，以及所有樣例的均值。如果均值不同盆犁，并且四分位值不可能重疊命咐，就可以說它們完全不同。

在我的三個樣例中蚣抗，我可以說scan侈百、find和binstr都是不同的，范圍上沒有重疊翰铡，并且（最重要的是）我可以相信數據。

分析結果

從結果中可以看出String_find比其它兩個更慢讽坏。實際上锭魔，我認為慢的原因是我實現的方式有些問題。然而當我將它與StringScanner_scan比較時路呜，我發(fā)現正是構造跳躍列表的那一部分最消耗時間迷捧。并且它的功能比scan要少织咧，因為它僅僅找到了第一個位置，而scan找到了全部漠秋。

我也可以發(fā)現scan以很大優(yōu)勢優(yōu)于binstr笙蒙。同時我可以說scan的功能比其他兩個要多，速度也更快庆锦。

下面是這個分析的一些注解：

• 我可能將實現或測試弄亂了⊥蔽唬現在我打算研究所有實現BMH的可能方式來改進它。我也會確保我所做的事情正確搂抒。
• 如果你修改了測試運行的時間艇搀，你會得到不同的結果。這就是我沒有考慮的”熱身“環(huán)節(jié)求晶。
• test_scan_performance單元測試和其它兩個并不相同焰雕，但是它比其它測試做得更多（并且也是按照時間和操作數量計算的），所以他可能是合理的芳杏。
• 我只通過在一個字符串內搜索另一個來執(zhí)行測試矩屁。我應該使所查找的字符串隨機化，來移除它們的位置和長度爵赵，作為干擾因素吝秕。
• binstr的實現可能比“暴力搜索”要好。（所以應該自己編寫暴力搜索作為對照亚再。）
• 我可能以不幸的順序來執(zhí)行這些函數郭膛，并且隨機化首先運行的測試可能會得到更好的結果。

可以從中學到的是氛悬，你需要確保知己的性能则剃，即使你“正確”實現了一個算法。在這里BMH算法應該優(yōu)于binstr算法如捅，但是一個簡單的測試證明了它是錯誤棍现。如果我沒有這些測試，我可能就使用了一個劣等的算法實現而不自知镜遣。參照這些度量己肮，我可以開始調優(yōu)我的實現，或者只是拋棄它并尋找新的算法悲关。

附加題

• 看看你能不能使Scan_find更快谎僻。為什么我的實現這么慢？
• 嘗試一些不同的搜索時長寓辱，看看你是否能得到不同的數值艘绍。當你改變scan的測試時間時，時間的長度會有什么影響秫筏？對于這些結果你能得出什么結論诱鞠？
• 修改單元測試挎挖，使它最開始執(zhí)行每個函數一小段時間，來消除任何“熱身”緩解航夺。這樣會修改所運行時長的依賴性嗎蕉朵？每秒可能出現多少次操作？
• 使單元測試中的所查找字符串隨機化阳掐，之后測量你的得到的性能始衅。一種實現它的方式就是使用bstrlib.h中的bsplit函數在空格處分割IN_STR。之后使用你得到的strList結構訪問它返回的每個字符串锚烦。這也教給你如何使用bstrList操作進行字符串處理觅闽。
• 嘗試一些不同順序的測試，看看能否得到不同的結果涮俄。