练习39：字符串算法

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

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

    首先，创建头文件：

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

    String_find

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

    StringScanner_scan

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

    1. #include <lcthw/string_algos.h>
    2. #include <limits.h>
    4. static inline void String_setup_skip_chars(
    5.         size_t *skip_chars,
    6.         const unsigned char *needle, ssize_t nlen)
    7. {
    8.     size_t i = 0;
    9.     size_t last = nlen - 1;
    11.     for(i = 0; i < UCHAR_MAX + 1; i++) {
    12.         skip_chars[i] = nlen;
    13.     }
    15.     for (i = 0; i < last; i++) {
    16.         skip_chars[needle[i]] = last - i;
    17.     }
    18. }
    21. static inline const unsigned char *String_base_search(
    22.         const unsigned char *haystack, ssize_t hlen,
    23.         const unsigned char *needle, ssize_t nlen,
    24.         size_t *skip_chars)
    25. {
    26.     size_t i = 0;
    27.     size_t last = nlen - 1;
    29.     assert(haystack != NULL && "Given bad haystack to search.");
    30.     assert(needle != NULL && "Given bad needle to search for.");
    32.     check(nlen > 0, "nlen can't be <= 0");
    33.     check(hlen > 0, "hlen can't be <= 0");
    35.     while (hlen >= nlen)
    36.     {
    37.         for (i = last; haystack[i] == needle[i]; i--) {
    38.             if (i == 0) {
    39.                 return haystack;
    40.             }
    41.         }
    43.         hlen -= skip_chars[haystack[last]];
    44.         haystack += skip_chars[haystack[last]];
    45.     }
    47. error: // fallthrough
    48.     return NULL;
    49. }
    51. int String_find(bstring in, bstring what)
    52. {
    53.     const unsigned char *found = NULL;
    54.     const unsigned char *haystack = (const unsigned char *)bdata(in);
    55.     ssize_t hlen = blength(in);
    56.     const unsigned char *needle = (const unsigned char *)bdata(what);
    57.     ssize_t nlen = blength(what);
    58.     size_t skip_chars[UCHAR_MAX + 1] = {0};
    60.     String_setup_skip_chars(skip_chars, needle, nlen);
    64.     return found != NULL ? found - haystack : -1;
    65. }
    67. StringScanner *StringScanner_create(bstring in)
    68. {
    69.     StringScanner *scan = calloc(1, sizeof(StringScanner));
    70.     check_mem(scan);
    72.     scan->in = in;
    73.     scan->haystack = (const unsigned char *)bdata(in);
    74.     scan->hlen = blength(in);
    76.     assert(scan != NULL && "fuck");
    77.     return scan;
    79. error:
    80.     free(scan);
    81.     return NULL;
    82. }
    84. static inline void StringScanner_set_needle(StringScanner *scan, bstring tofind)
    85. {
    86.     scan->needle = (const unsigned char *)bdata(tofind);
    87.     scan->nlen = blength(tofind);
    89.     String_setup_skip_chars(scan->skip_chars, scan->needle, scan->nlen);
    90. }
    92. static inline void StringScanner_reset(StringScanner *scan)
    93. {
    94.     scan->haystack = (const unsigned char *)bdata(scan->in);
    95.     scan->hlen = blength(scan->in);
    96. }
    98. int StringScanner_scan(StringScanner *scan, bstring tofind)
    99. {
    100.     const unsigned char *found = NULL;
    101.     ssize_t found_at = 0;
    103.     if(scan->hlen <= 0) {
    104.         StringScanner_reset(scan);
    105.         return -1;
    106.     }
    108.     if((const unsigned char *)bdata(tofind) != scan->needle) {
    109.         StringScanner_set_needle(scan, tofind);
    111.     found = String_base_search(
    112.             scan->haystack, scan->hlen,
    113.             scan->needle, scan->nlen,
    114.             scan->skip_chars);
    116.     if(found) {
    117.         found_at = found - (const unsigned char *)bdata(scan->in);
    118.         scan->haystack = found + scan->nlen;
    119.         scan->hlen -= found_at - scan->nlen;
    120.     } else {
    121.         // done, reset the setup
    122.         StringScanner_reset(scan);
    123.         found_at = -1;
    124.     }
    126.     return found_at;
    127. }
    130. void StringScanner_destroy(StringScanner *scan)
    131. {
    132.     if(scan) {
    133.         free(scan);
    134.     }
    135. }

    整个算法都在两个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设置来运行测试，并且分析结果。

    当我在我的笔记本上运行测试时，我得到的数据是这样的：

    1. $ ./tests/string_algos_tests
    2. DEBUG tests/string_algos_tests.c:124: ----- RUNNING: ./tests/string_algos_tests
    3. ----
    4. RUNNING: ./tests/string_algos_tests
    5. DEBUG tests/string_algos_tests.c:116:
    6. ----- test_find_and_scan
    7. DEBUG tests/string_algos_tests.c:117:
    8. ----- test_scan_performance
    9. DEBUG tests/string_algos_tests.c:105: SCAN COUNT: 110272000, END TIME: 2, OPS: 55136000.000000
    10. DEBUG tests/string_algos_tests.c:118:
    11. ----- test_find_performance
    12. DEBUG tests/string_algos_tests.c:76: FIND COUNT: 12710000, END TIME: 2, OPS: 6355000.000000
    13. DEBUG tests/string_algos_tests.c:119:
    14. ----- test_binstr_performance
    15. DEBUG tests/string_algos_tests.c:54: BINSTR COUNT: 72736000, END TIME: 2, OPS: 36368000.000000
    16. ALL TESTS PASSED
    17. Tests run: 4
    18. $

    我看到了它，觉得每轮运行应该超过两秒。并且，我打算多次运行它，并且像之前一样使用R来验证。下面是我获得的10个样例，每个基本上是10秒：

    1. $ 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
    2. $ less times.log
    3. $ 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的测试时间时，时间的长度会有什么影响？对于这些结果你能得出什么结论？
    • 修改单元测试，使它最开始执行每个函数一小段时间，来消除任何“热身”缓解。这样会修改所运行时长的依赖性吗？每秒可能出现多少次操作？
    • 尝试一些不同顺序的测试，看看能否得到不同的结果。