语境：
我有一个代码/文本编辑器，而不是我试图优化的。目前，该程序的瓶颈是语言解析器而不是扫描所有关键字（不止一个，但它们的编写大致相同）。
1,000,000在我的电脑上，编辑器在代码行周围的文件上延迟。在 Raspberry Pi 等低端计算机上，延迟开始发生得更快（我不记得确切，但我认为10,000是代码行）。尽管我从未见过比1,000,000代码行更大的文档，但我确信它们就在那里，我希望我的程序能够编辑它们。
问题：
这引出了一个问题：在大型动态字符串中扫描单词列表的最快方法是什么？
以下是一些可能影响算法设计的信息：
- 关键字
- 限定字符允许成为关键字的一部分，（我称它们为限定符）
- 大字符串
瓶颈解决方案：
这是（大致）我目前用来解析字符串的方法：
// 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;
}
可能的解决方案：
上下文解决方案：
我正在考虑以下几点：
扫描一次大字符串，并添加一个函数来评估/调整每次用户输入时的标记标记（而不是一遍又一遍地重新扫描整个文档）。我希望这将解决瓶颈，因为涉及的解析要少得多。但是，它并不能完全修复程序，因为初始扫描可能仍然需要很长时间。
优化令牌扫描算法（见下文）
我也考虑过，但拒绝了这些优化：
- 扫描仅在屏幕上的代码。尽管这会解决瓶颈问题，但它会限制查找出现在屏幕开始位置之前的用户定义标记（即变量名、函数名、宏）的能力。
- 将文本切换为链表（每行一个节点），而不是单片数组。这并没有真正帮助瓶颈。尽管插入/删除会更快，但索引访问的丢失会减慢解析器的速度。我认为，与分解列表相比，单片阵列更有可能被缓存。
- 硬编码每种语言的扫描令牌功能。尽管这可能是性能的最佳优化，但从软件开发的角度来看似乎并不实用。
架构解决方案：
使用汇编语言，解析这些字符串的更快方法是将字符加载到寄存器中并一次比较它们4或8字节。还有一些额外的措施和预防措施需要考虑，例如：
- 该架构是否支持未对齐的内存访问？
- 所有字符串的大小都必须为
swheres % 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 算法（据我了解）是一种用于在字符串中查找子字符串的算法。由于我正在解析多个字符串，我认为还有更多的优化空间。