6

语境:

我有一个代码/文本编辑器,而不是我试图优化的。目前,该程序的瓶颈是语言解析器而不是扫描所有关键字(不止一个,但它们的编写大致相同)。

1,000,000在我的电脑上,编辑器在代码行周围的文件上延迟。在 Raspberry Pi 等低端计算机上,延迟开始发生得更快(我不记得确切,但我认为10,000是代码行)。尽管我从未见过比1,000,000代码行更大的文档,但我确信它们就在那里,我希望我的程序能够编辑它们。

问题:

这引出了一个问题:在大型动态字符串中扫描单词列表的最快方法是什么?

以下是一些可能影响算法设计的信息:

  1. 关键字
  2. 限定字符允许成为关键字的一部分,(我称它们为限定符)
  3. 大字符串

瓶颈解决方案:

这是(大致)我目前用来解析字符串的方法:

// this is just an example, not an excerpt
// I haven't compiled this, I'm just writing it to
// illustrate how I'm currently parsing strings

struct tokens * scantokens (char * string, char ** tokens, int tcount){

    int result = 0;
    struct tokens * tks = tokens_init ();

    for (int i = 0; string[i]; i++){

        // qualifiers for C are: a-z, A-Z, 0-9, and underscore
        // if it isn't a qualifier, skip it

        while (isnotqualifier (string[i])) i++;

        for (int j = 0; j < tcount; j++){

            // returns 0 for no match
            // returns the length of the keyword if they match
            result = string_compare (&string[i], tokens[j]);

            if (result > 0){ // if the string matches
                token_push (tks, i, i + result); // add the token
                // token_push (data_struct, where_it_begins, where_it_ends)
                break;
            }
        }

        if (result > 0){
            i += result;
        } else {
            // skip to the next non-qualifier
            // then skip to the beginning of the next qualifier

            /* ie, go from:
                'some_id + sizeof (int)'
                 ^

            to here:
                'some_id + sizeof (int)'
                           ^
            */
        }
    }

    if (!tks->len){
        free (tks);
        return 0;
    } else return tks;
}

可能的解决方案:


上下文解决方案:

我正在考虑以下几点:

  • 扫描一次大字符串,并添加一个函数来评估/调整每次用户输入时的标记标记(而不是一遍又一遍地重新扫描整个文档)。我希望这将解决瓶颈,因为涉及的解析要少得多。但是,它并不能完全修复程序,因为初始扫描可能仍然需要长时间。

  • 优化令牌扫描算法(见下文)

我也考虑过,但拒绝了这些优化:

  • 扫描仅在屏幕上的代码。尽管这会解决瓶颈问题,但它会限制查找出现在屏幕开始位置之前的用户定义标记(即变量名、函数名、宏)的能力。
  • 将文本切换为链表(每行一个节点),而不是单片数组。这并没有真正帮助瓶颈。尽管插入/删除会更快,但索引访问的丢失会减慢解析器的速度。我认为,与分解列表相比,单片阵列更有可能被缓存。
  • 硬编码每种语言的扫描令牌功能。尽管这可能是性能的最佳优化,但从软件开发的角度来看似乎并不实用。

架构解决方案:

使用汇编语言,解析这些字符串的更快方法是将字符加载到寄存器中并一次比较它们48字节。还有一些额外的措施和预防措施需要考虑,例如:

  • 该架构是否支持未对齐的内存访问?
  • 所有字符串的大小都必须为swhere s % word-size == 0,以防止读取违规
  • 其他的?

但这些问题似乎很容易解决。唯一的问题(除了用汇编语言编写的常见问题之外)是它与其说是算法解决方案,不如说是硬件解决方案。

算法解决方案:

到目前为止,我已经考虑让程序重新排列关键字列表,以使二进制搜索算法更有可能。

为此我考虑重新排列它们的一种方法是切换关键字列表的维度。这是一个例子C

// some keywords for the C language

auto  // keywords[0]
break // keywords[1]
case char const continue // keywords[2], keywords[3], keywords[4]
default do double
else enum extern
float for
goto
if int
long
register return
short signed sizeof static struct switch
typedef
union unsigned
void volatile
while

/* keywords[i] refers to the i-th keyword in the list
 *
 */

切换二维数组的维度将使它看起来像这样:

    0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 3 3 3
    1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2
  -----------------------------------------------------------------
1 | a b c c c c d d d e e e f f g i i l r r s s s s s s t u u v v w
2 | u r a h o o e o o l n x l o o f n o e e h i i t t w y n n o o h
3 | t e s a n n f   u s u t o r t   t n g t o g z a r i p i s i l i
4 | o a e r s t a   b e m e a   o     g i u r n e t u t e o i d a l
5 |   k       i u   l     r t           s r t e o i c c d n g   t e
6 |           n l   e     n             t n   d f c t h e   n   i
7 |           u t                       e               f   e   l
8 |           e                         r                   d   e

// note that, now, keywords[0] refers to the string "abccccdddeeefffiilrr"

这使得使用二分搜索算法(甚至是普通的蛮力算法)更有效。但它只是每个关键字中第一个字符的单词,之后什么都不能被认为是“排序的”。这可能有助于像编程语言这样的小词集,但对于更大的词集(比如整个英语语言)来说,这还不够。

改进这个算法还有更多的办法吗?

是否可以采取另一种方法来提高性能?

笔记:

SO的这个问题对我没有帮助。Boyer-Moore-Horspool 算法(据我了解)是一种用于在字符串中查找子字符串的算法。由于我正在解析多个字符串,我认为还有更多的优化空间。

4

4 回答 4

4

Aho-Corasick 是一个非常酷的算法,但它并不适合关键字匹配,因为关键字匹配是对齐的;你不能有重叠的匹配,因为你只匹配一个完整的标识符。

对于基本的标识符查找,您只需要从您的关键字中构建一个trie (请参见下面的注释)。

您的基本算法很好:找到标识符的开头,然后查看它是否是关键字。改进这两个部分很重要。除非您需要处理多字节字符,否则查找关键字开头的最快方法是使用包含 256 个条目的表,每个可能的字符对应一个条目。有三种可能:

  1. 该字符不能出现在标识符中。(继续扫描)

  2. 该字符可以出现在标识符中,但没有关键字以该字符开头。(跳过标识符)

  3. 角色可以开始一个关键字。(开始遍历trie;如果无法继续遍历,则跳过标识符。如果遍历找到关键字并且下一个字符不能在标识符中,则跳过标识符的其余部分;如果可以在标识符中,请尝试继续如果可能的话,步行。)

实际上,第 2 步和第 3 步非常接近,因此您并不需要特殊的逻辑。

上述算法存在一些不精确性,因为在很多情况下,您会发现一些看起来像标识符但在语法上不可能的东西。最常见的情况是注释和引用字符串,但大多数语言都有其他可能性。例如,在 C 中,您可以使用十六进制浮点数;虽然不能仅从 构造 C 关键字[a-f],但用户提供的单词可能是:

0x1.deadbeef

另一方面,C++ 允许用户定义数字后缀,如果用户将它们添加到列表中,您可能希望将其识别为关键字:

274_myType

除了以上所有之外,每次用户在编辑器中键入字符时解析一百万行代码确实是不切实际的。您需要开发一些缓存标记化的方法,最简单和最常见的一种是按输入行缓存。将输入行保存在一个链表中,并且每个输入行还记录行首的标记器状态(即,无论您是在多行引用字符串中;多行注释,还是其他一些特殊的词汇状态)。除了在一些非常奇怪的语言中,编辑不会影响编辑之前行的标记结构,因此对于任何编辑,您只需重新标记已编辑的行以及标记器状态已更改的任何后续行。(注意在多行字符串的情况下工作太辛苦:


注意:对于少量(数百)个关键字,一个完整的 trie 并不会真正占用那么多空间,但在某些时候您需要处理臃肿的分支。一个非常合理的数据结构,如果你注意数据布局,它可以很好地执行,它是三元搜索树(尽管我称之为三元搜索树。)

于 2013-08-21T03:49:59.200 回答
2

很难击败此代码。

假设您的关键字是“a”、“ax”和“foo”。

获取关键字列表,排序,然后将其输入到打印出如下代码的程序中:

switch(pc[0]){
  break; case 'a':{
    if (0){
    } else if (strcmp(pc, "a")==0 && !alphanum(pc[1])){
      // push "a"
      pc += 1;
    } else if (strcmp(pc, "ax")==0 && !alphanum(pc[2])){
      // push "ax"
      pc += 2;
    }
  }
  break; case 'f':{
    if (0){
    } else if (strcmp(pc, "foo")==0 && !alphanum(pc[3])){
      // push "foo"
      pc += 3;
    }
    // etc. etc.
  }
  // etc. etc.
}

然后,如果您没有看到关键字,只需增加并重pc试。关键是,通过调度第一个字符,您可以快速进入以该字符开头的关键字子集。您甚至可能想要进行两个级别的调度。

当然,和往常一样,取一些堆栈样本来查看时间被用于什么。无论如何,如果您有数据结构类,您会发现这会占用您大部分时间,因此请将其保持在最低限度(将宗教抛诸脑后:)

于 2013-08-23T17:41:16.593 回答
1

最快的方法是为单词集构建一个有限状态机。使用 Lex 构建 FSM。

于 2013-08-21T03:08:00.937 回答
0

这个问题的最佳算法可能是 Aho-Corasick。已经存在 C 实现,例如,

http://sourceforge.net/projects/multifast/
于 2013-08-21T03:15:28.537 回答