最有效的方式來比較短串小字典（解析）

我試圖優化我的簡單的C interpretter，我只是爲了好玩做，我做解析這樣的 - 首先，我分析文件到雙向鏈表中的令牌，然後我做語法和語義分析。
我想優化此原型的功能：最有效的方式來比較短串小字典（解析）

bool parsed_keyword（struct token *，char dictionary [] []）;

裏面的函數我基本上調用strcmp對所有關鍵字和編輯標記類型。這當然會導致對正在解析（幾乎）每個字符串的20個strcmp調用。

我想拉賓，卡普將是最好的，但它聽起來好像它是不是最適合這個工作（匹配對小字典一個字）。做這項工作最好的算法是什麼？感謝您的任何建議。

來源

2012-07-09 AoeAoe

當涉及到「n = 20」時，優化應該是您最擔心的問題。幾乎任何順序多項式函數都可以滿足您的需求。 – corsiKa 2012-07-09 17:22:57

根據Niklaus Wirth的說法，當您在編譯器/解釋器中查找本地符號時，*是*最有效的方法。他甚至做了測試以確保。（當然，他的指標可能與你的指標不同，但是他的指標是非常好的指標。） – 2012-07-09 17:25:44

散列表可能是我對這個特定問題的選擇。它將提供O(1)查找您的大小的表格。儘管如此，特里也是一個不錯的選擇。

但是，爲了實現將是把你的話在按字母順序排列，然後用bsearch C庫中最簡單的。它應該幾乎與散列或特里一樣快，因爲你只處理30個單詞。它實際上可能會比散列表更快，因爲您不必計算散列值。

Steve Jessop的想法是一個很好的想法，用相同大小的char數組來排列字符串。

const char keywords[][MAX_KEYWORD_LEN+1] = { 
"auto", "break", "case", /* ... */, "while" 
}; 

#define NUM_KEYWORDS sizeof(keywords)/sizeof(keywords[0]) 

int keyword_cmp (const void *a, const void *b) { 
    return strcmp(a, b); 
} 

const char *kw = bsearch(word, keywords, NUM_KEYWORDS, sizeof(keywords[0]), 
         keyword_cmp); 

int kw_index = (kw ? (const char (*)[MAX_KEYWORD_LEN+1])kw - keywords : -1);

如果你不已經擁有了它，你應該考慮收購的Compilers: Principles, Techniques, and Tools副本。由於它的封面，它通常被稱爲龍書。

來源

2012-07-09 17:18:22 jxh

如果將所有單詞用nul個字節填充到最長的單詞的長度，那麼二分法搜索變得特別簡單，因爲您可以將字符串首尾相連 - 沒有第二種間接方式。由於它們是關鍵字，因此列表不會經常更改。 – 2012-07-09 17:29:55

@SteveJessop：我將你的實現建議添加到答案中，問候 – jxh 2012-07-09 17:56:52

無關緊要，但是對於comp sci書（恐龍os書，更不用說所有的o'reilly動物書）的所有荒謬封面，編譯器書最酷覆蓋永遠。 – nook 2012-07-09 17:58:19

如果你正在尋找的效率我會說，拉賓卡普是不是你最好的選擇，和你最好的效率將與博耶，摩爾發現，但它更是一個公平一點難以實現。

如果你是爲了好玩而做這件事，說實話，我不認爲有必要優化，因爲這些調用應該在相當短的時間內運行，並且你並不需要它以工業速度運行。

如果您正在尋找使用字符串匹配算法，這是一個很酷且有用的目標，我建議您查看KMP算法和Boyer-Moore算法，這兩種算法在實現過程中都會教你很多。

當然還有其他更直接的方法，比如字典查找和簡單的二分查找等等，但那些並不真正優化你處理字符串和字符串比較是一個非常有趣的領域，你會在某個時候不可避免地遇到。

來源

2012-07-09 17:21:54

Nah，boyer moore在這個特定情況下非常無效（與多於一個詞相匹配），可能與天真匹配算法一樣低效。是的，我只是爲了好玩，否則我可能根本不在乎。 – AoeAoe 2012-07-09 19:27:38

，想到時做的查找是隻使用鍵盤的排序陣列，並對其做一個二進制搜索的第一件事。

來源

2012-07-09 17:24:11

如果關鍵字的集合是固定的，你可以使用gperf使用理想哈希，例如。這隻需要不斷的工作和單個字符串比較，因此可能比其他方法更快。

來源

2012-07-09 20:36:41

假設您的關鍵字沒有改變，這聽起來像是perfect hash function的正確情況。完美的散列函數將輸入映射到整數（如常規散列函數），但沒有衝突。

Wikipedia有幾個完美的哈希生成器的鏈接，包括GNU gperf。

來源

2012-07-09 21:01:03 mike

最有效的方式來比較短串小字典（解析）

回答

相關問題