語境：優化一句話解析器
我有一個代碼/文本編輯器比我試圖優化。目前，該程序的瓶頸是語言解析器，而不是掃描所有關鍵字（不止一個，但它們通常寫成相同）。
在我的電腦上，編輯器延遲了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;
}
可能的解決方案：
語境解決方案：
我正在考慮以下內容：
掃描大字符串一次，並添加一個函數來評估/調整標記標記，每次有用戶輸入時（而不是一遍又一遍地重新掃描整個文檔）。我期望這將解決瓶頸問題，因爲有遠遠少於解析涉及。但是，它並沒有完全修復程序，因爲初始掃描可能仍然需要很長時間。
優化令牌掃描算法（見下文）
我也考慮過，但是已經拒絕了，這些優化：
- 掃描，這只是在屏幕上的代碼。雖然這可以解決瓶頸問題，但它會限制查找比屏幕開始位置更早出現的用戶定義標記（即變量名稱，函數名稱，宏）的能力。
- 將文本切換到鏈接列表（每行一個節點），而不是單片陣列。這並不能真正幫助瓶頸。雖然插入/刪除操作會更快，但索引訪問的丟失會降低解析器的速度。我認爲，單一數組更容易被緩存，而不是分解列表。
- 對每種語言的掃描標記功能進行硬編碼。雖然這可能是性能的最佳優化，但從軟件開發的角度來看，這似乎並不實際。
建築溶液：
彙編語言，一個更快的方式來解析這些字符串將字符加載到寄存器和在一個時間對它們進行比較48或字節。有一些額外的措施和預防措施必須加以考慮，例如：
- 該體系結構是否支持未對齊的內存訪問？
- 所有字符串必須是大小
s，其中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"
這使得使用二進制搜索算法更高效（甚至是一個普通的蠻力算法）。但它只是每個關鍵字中的第一個字符的單詞，之後沒有任何內容可以被視爲「排序」。這可能有助於像編程語言這樣的小詞彙集，但對於更大的詞彙集（比如整個英語語言）還不夠。
是否有更多可以做到改善這種算法？
是否有另一種方法可以提高性能？
注：
This question從SO並不能幫助我。 Boyer-Moore-Horspool算法（據我所知）是一種在字符串中查找子字符串的算法。由於我解析爲多個字符串，我認爲還有更多優化空間。
如果你想快速做到這一點您不會使用字符串比較和字符串列表進行循環，但會根據發現關鍵字時觸發的所有字符串的每個字符構建一個有限狀態機。 Lex實用程序執行此操作。 – Jiminion