1

即使我打开一个新文件，即使在一个非常大的文件上，搜索命令也能运行得非常快？用于实现它的算法是什么。

我只是好奇？

4

1 回答 1

1

这只是您的常规正则表达式实现。

首先，模式被编译成正则表达式 ( vim_regcomp)。

接下来，vim_regexec{_multi,_nl,_both}用于执行它。它通过逐步处理各种原子来做到这一点（有一个明确的回溯堆栈）。

现在，正则表达式的叶节点仅由行人功能处理，例如

  • vim_strbyte
  • vim_strchr

  • cstrchr; 例如，这显示了实现的“直截了​​当”（特别是，如果您查看FEAT_MBYTE未定义的更简单的情况）

    /*
* cstrchr: This function is used a lot for simple searches, keep it fast!
*/
    static char_u *
cstrchr(s, c)
    char_u  *s;
    int     c;
{
    char_u  *p;
    int     cc;

    if (!ireg_ic
#ifdef FEAT_MBYTE
            || (!enc_utf8 && mb_char2len(c) > 1)
#endif
            )
        return vim_strchr(s, c);

    /* tolower() and toupper() can be slow, comparing twice should be a lot
    * faster (esp. when using MS Visual C++!).
    * For UTF-8 need to use folded case. */
#ifdef FEAT_MBYTE
    if (enc_utf8 && c > 0x80)
        cc = utf_fold(c);
    else
#endif
        if (MB_ISUPPER(c))
        cc = MB_TOLOWER(c);
    else if (MB_ISLOWER(c))
        cc = MB_TOUPPER(c);
    else
        return vim_strchr(s, c);

#ifdef FEAT_MBYTE
    if (has_mbyte)
    {
        for (p = s; *p != NUL; p += (*mb_ptr2len)(p))
        {
            if (enc_utf8 && c > 0x80)
            {
                if (utf_fold(utf_ptr2char(p)) == cc)
                    return p;
            }
            else if (*p == c || *p == cc)
                return p;
        }
    }
    else
#endif
        /* Faster version for when there are no multi-byte characters. */
        for (p = s; *p != NUL; ++p)
            if (*p == c || *p == cc)
                return p;

    return NULL;
}

现在短篇小说是：

  • 涉及到正则表达式的实现（因为它支持很多特性，比如 Unicode 大小写折叠）
  • 5966 LoC 运行中的实现src/regexp.c（7652 包括注释和空格）

但是，如果您正在寻找“复杂”的算法（例如 Boyer Moore），您将找不到它，因为坦率地说，在单个文件中查找文本并不需要它。

现在，如果您想查看性能最佳的搜索算法，您可能需要查看 GNUgrep的源代码...... :)

所有计数均基于vim-7.3.547debian 软件包存档

于 2013-09-22T21:21:51.250 回答