練習(xí)39：字符串算法

原文：Exercise 39: String Algorithms

譯者：飛龍

這個(gè)練習(xí)中，我會(huì)向你展示可能是最快的字符串搜索算法之一，并且將它與bstrlib.c中現(xiàn)有的binstr比較。binstr的文檔說它僅僅使用了“暴力搜索”的字符串算法來尋找第一個(gè)實(shí)例。我所實(shí)現(xiàn)的函數(shù)使用Boyer-Moore-Horspool（BMH）算法，如果你分析理論時(shí)間的話，一般認(rèn)為它會(huì)更快。你也會(huì)看到，如果我的實(shí)現(xiàn)沒有任何缺陷，BMH的實(shí)際時(shí)間會(huì)比binstr簡單的暴力搜索更糟。

這個(gè)練習(xí)的要點(diǎn)并不是真正解釋算法本身，因?yàn)槟憧梢灾苯尤?a target="_blank" rel="nofollow">Boyer-Moore-Horspool 的維基百科頁面去閱讀它。這個(gè)算法的要點(diǎn)就是它會(huì)計(jì)算出“跳躍字符列表”作為第一步操作，之后它使用這個(gè)列表來快速掃描整個(gè)字符串。它應(yīng)當(dāng)比暴力搜索更快，所以讓我們在文件里寫出代碼來看看吧。

首先，創(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)建這個(gè)算法的兩種版本：

String_find

只是在一個(gè)字符串中，尋找另一個(gè)字符串的首個(gè)實(shí)例，以一個(gè)動(dòng)作執(zhí)行整個(gè)算法。

StringScanner_scan

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

一旦你完成了頭文件，下面就是實(shí)現(xiàn)了：

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

整個(gè)算法都在兩個(gè)static inline的函數(shù)中，叫做String_setup_skip_chars 和 String_base_search。它們在別的函數(shù)中使用，用于實(shí)現(xiàn)我想要的的搜索形式。研究這兩個(gè)函數(shù)，并且與維基百科的描述對比，你就可以知道它的工作原理。

之后String_find使用這兩個(gè)函數(shù)來尋找并返回所發(fā)現(xiàn)的位置。它非常簡單并且我使用它來查看“跳躍字符列表”的構(gòu)建如何影響到真實(shí)性能。要注意，你或許可以使它更快，但是我要教給你在你實(shí)現(xiàn)算法之后如何驗(yàn)證理論速度。

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

最后，我編寫了單元測試來確保算法有效，之后在它的注釋部分，我為三個(gè)搜索函數(shù)運(yùn)行了簡單的性能測試：

#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預(yù)處理器來注釋一段代碼的方法。像這樣輸入，并且把它和#endif移除，你就可以運(yùn)行性能測試。當(dāng)你繼續(xù)這本書時(shí)，需要簡單地把它們再次注釋，以防它們浪費(fèi)你的開發(fā)時(shí)間。

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

需要注意的一個(gè)技巧是，我在start中存儲(chǔ)了起始時(shí)間，之后一直循環(huán)到至少過了TEST_TIME秒。這確保了我能或得到足夠好的樣本用于比較三者。我之后會(huì)使用不同的TEST_TIME設(shè)置來運(yùn)行測試，并且分析結(jié)果。

你會(huì)看到什么

當(dāng)我在我的筆記本上運(yùn)行測試時(shí)，我得到的數(shù)據(jù)是這樣的：

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

我看到了它，覺得每輪運(yùn)行應(yīng)該超過兩秒。并且，我打算多次運(yùn)行它，并且像之前一樣使用R來驗(yàn)證。下面是我獲得的10個(gè)樣例，每個(gè)基本上是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的一點(diǎn)點(diǎn)幫助下獲取數(shù)據(jù)，之后編輯輸出：

$ 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

現(xiàn)在你可以看到scan系統(tǒng)要優(yōu)于另外兩個(gè)，但是我會(huì)在R中打開它并且驗(yàn)證結(jié)果：

> 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)計(jì)，我必須對你解釋一些統(tǒng)計(jì)學(xué)概念。我在這些數(shù)字中尋找的東西能夠簡單地告訴我，“這三個(gè)函數(shù)（scan、find、binstr）實(shí)際上不同嗎？”我知道每次我運(yùn)行測試函數(shù)的時(shí)候，我都會(huì)得到有些不同的數(shù)值，并且那些數(shù)值始終處理一個(gè)固定的范圍。你可以看到兩個(gè)四分位數(shù)反映了這一點(diǎn)。

我首先會(huì)去看均值，并且我會(huì)觀察每個(gè)樣例的均值是否不同于其它的。我可以清楚地看到scan優(yōu)于binstr，同時(shí)后者優(yōu)于find。然而問題來了，如果我只使用均值，就可以出現(xiàn)每個(gè)樣例的范圍會(huì)重疊的可能性。

如果均值不同，但是兩個(gè)四分位點(diǎn)重疊會(huì)怎么用？這種情況下我只能說有這種可能性，并且如果我再次運(yùn)行測試，均值就可能不同了。很可能出現(xiàn)的范圍上的重疊是，我的兩個(gè)樣例（以及兩個(gè)函數(shù)）并非實(shí)際上不同。任何我看到的差異都是隨機(jī)產(chǎn)生的結(jié)果。

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

在我的三個(gè)樣例中，我可以說scan、find和binstr都是不同的，范圍上沒有重疊，并且（最重要的是）我可以相信數(shù)據(jù)。

分析結(jié)果

從結(jié)果中可以看出String_find比其它兩個(gè)更慢。實(shí)際上，我認(rèn)為慢的原因是我實(shí)現(xiàn)的方式有些問題。然而當(dāng)我將它與StringScanner_scan比較時(shí)，我發(fā)現(xiàn)正是構(gòu)造跳躍列表的那一部分最消耗時(shí)間。并且它的功能比scan要少，因?yàn)樗鼉H僅找到了第一個(gè)位置，而scan找到了全部。

我也可以發(fā)現(xiàn)scan以很大優(yōu)勢優(yōu)于binstr。同時(shí)我可以說scan的功能比其他兩個(gè)要多，速度也更快。

下面是這個(gè)分析的一些注解：

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

可以從中學(xué)到的是，你需要確保知己的性能，即使你“正確”實(shí)現(xiàn)了一個(gè)算法。在這里BMH算法應(yīng)該優(yōu)于binstr算法，但是一個(gè)簡單的測試證明了它是錯(cuò)誤。如果我沒有這些測試，我可能就使用了一個(gè)劣等的算法實(shí)現(xiàn)而不自知。參照這些度量，我可以開始調(diào)優(yōu)我的實(shí)現(xiàn)，或者只是拋棄它并尋找新的算法。

附加題

• 看看你能不能使Scan_find更快。為什么我的實(shí)現(xiàn)這么慢？
• 嘗試一些不同的搜索時(shí)長，看看你是否能得到不同的數(shù)值。當(dāng)你改變scan的測試時(shí)間時(shí)，時(shí)間的長度會(huì)有什么影響？對于這些結(jié)果你能得出什么結(jié)論？
• 修改單元測試，使它最開始執(zhí)行每個(gè)函數(shù)一小段時(shí)間，來消除任何“熱身”緩解。這樣會(huì)修改所運(yùn)行時(shí)長的依賴性嗎？每秒可能出現(xiàn)多少次操作？
• 使單元測試中的所查找字符串隨機(jī)化，之后測量你的得到的性能。一種實(shí)現(xiàn)它的方式就是使用bstrlib.h中的bsplit函數(shù)在空格處分割IN_STR。之后使用你得到的strList結(jié)構(gòu)訪問它返回的每個(gè)字符串。這也教給你如何使用bstrList操作進(jìn)行字符串處理。
• 嘗試一些不同順序的測試，看看能否得到不同的結(jié)果。