练习39：字符串算法

这个练习中，我会向你展示可能是最快的字符串搜索算法之一，并且将它与中现有的binstr比较。binstr的文档说它仅仅使用了“暴力搜索”的字符串算法来寻找第一个实例。我所实现的函数使用Boyer-Moore-Horspool（BMH）算法，如果你分析理论时间的话，一般认为它会更快。你也会看到，如果我的实现没有任何缺陷，BMH的实际时间会比binstr简单的暴力搜索更糟。

这个练习的要点并不是真正解释算法本身，因为你可以直接去去阅读它。这个算法的要点就是它会计算出“跳跃字符列表”作为第一步操作，之后它使用这个列表来快速扫描整个字符串。它应当比暴力搜索更快，所以让我们在文件里写出代码来看看吧。

首先，创建头文件：

为了观察“跳跃字符列表”的效果，我打算创建这个算法的两种版本：

String_find

只是在一个字符串中，寻找另一个字符串的首个实例，以一个动作执行整个算法。

StringScanner_scan

使用StringScanner状态结构，将跳跃列表的构建和实际的查找操作分开。这让我能看到什么影响了性能。这个模型有另一个优点，就是我可以在一个字符串中逐步搜索，并且快速地找到所有实例。

#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);
    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函数随后按照“创建、扫描、销毁”的常用模式，并且用于在一个字符串中逐步搜索另一个字符串。当我向你展示单元测试的时候，你会看到它如何使用。

最后，我编写了单元测试来确保算法有效，之后在它的注释部分，我为三个搜索函数运行了简单的性能测试：

我把它们写在#if 0中间，它是使用C预处理器来注释一段代码的方法。像这样输入，并且把它和#endif移除，你就可以运行性能测试。当你继续这本书时，需要简单地把它们再次注释，以防它们浪费你的开发时间。

这个单元测试没有什么神奇之处，它只是在尊换种调用每个不同的函数，循环需要持续足够长的时间来得到一个几秒的样本。第一个测试（test_find_and_scan）只是确保我所编写的代码正常工作，因为测试无效的代码没有意义。之后，下面的三个函数使用三个函数中的每一个来执行大量的搜索。

需要注意的一个技巧是，我在start中存储了起始时间，之后一直循环到至少过了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秒：

$ 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中打开它并且验证结果：

为了理解我为什么要生成这份概要统计，我必须对你解释一些统计学概念。我在这些数字中寻找的东西能够简单地告诉我，“这三个函数（scan、find、binstr）实际上不同吗？”我知道每次我运行测试函数的时候，我都会得到有些不同的数值，并且那些数值始终处理一个固定的范围。你可以看到两个四分位数反映了这一点。

我首先会去看均值，并且我会观察每个样例的均值是否不同于其它的。我可以清楚地看到scan优于binstr，同时后者优于find。然而问题来了，如果我只使用均值，就可以出现每个样例的范围会重叠的可能性。

如果均值不同，但是两个四分位点重叠会怎么用？这种情况下我只能说有这种可能性，并且如果我再次运行测试，均值就可能不同了。很可能出现的范围上的重叠是，我的两个样例（以及两个函数）并非实际上不同。任何我看到的差异都是随机产生的结果。

统计学拥有大量工具来解决这一问题，但是在我们的例子中我可以仅仅观察两个四分位值，以及所有样例的均值。如果均值不同，并且四分位值不可能重叠，就可以说它们完全不同。

在我的三个样例中，我可以说scan、find和binstr都是不同的，范围上没有重叠，并且（最重要的是）我可以相信数据。

从结果中可以看出String_find比其它两个更慢。实际上，我认为慢的原因是我实现的方式有些问题。然而当我将它与StringScanner_scan比较时，我发现正是构造跳跃列表的那一部分最消耗时间。并且它的功能比scan要少，因为它仅仅找到了第一个位置，而scan找到了全部。

我也可以发现scan以很大优势优于binstr。同时我可以说scan的功能比其他两个要多，速度也更快。

下面是这个分析的一些注解：

• 我可能将实现或测试弄乱了。现在我打算研究所有实现BMH的可能方式来改进它。我也会确保我所做的事情正确。
• 如果你修改了测试运行的时间，你会得到不同的结果。这就是我没有考虑的”热身“环节。
• test_scan_performance单元测试和其它两个并不相同，但是它比其它测试做得更多（并且也是按照时间和操作数量计算的），所以他可能是合理的。
• 我只通过在一个字符串内搜索另一个来执行测试。我应该使所查找的字符串随机化，来移除它们的位置和长度，作为干扰因素。
• binstr的实现可能比“暴力搜索”要好。（所以应该自己编写暴力搜索作为对照。）
• 我可能以不幸的顺序来执行这些函数，并且随机化首先运行的测试可能会得到更好的结果。

• 看看你能不能使Scan_find更快。为什么我的实现这么慢？
• 尝试一些不同的搜索时长，看看你是否能得到不同的数值。当你改变scan的测试时间时，时间的长度会有什么影响？对于这些结果你能得出什么结论？
• 修改单元测试，使它最开始执行每个函数一小段时间，来消除任何“热身”缓解。这样会修改所运行时长的依赖性吗？每秒可能出现多少次操作？
• 尝试一些不同顺序的测试，看看能否得到不同的结果。