將一條線與C++中的規則相匹配

Question

我有一條線和一組規則（其他線）。匹配的行（行=規則）可能很長;規則集可能很大，每個規則可能很長。較短的規則可能是更長的一部分（需要選擇更長的時間）。
目前，我有約70個規則，< 30個字符長，組織在一個長的if-else-if鏈中。
有什麼方法可以預測什麼時候性能會下降？
比較行與每個規則是否有更快的匹配方式？

編輯：沒有文本文件。我有一個字符編碼序列，我通過if-elses比較「規則」，然後採取相應的行動。

Answer 1

如果你只想檢查輸入線是否等於任何的線規則，然後使用std::set（或std::map，如果你想每個規則不同的行爲）來存儲它們。這將匹配複雜度降至O（lg N），其中N是規則的數量。

更好的是，對於O（1）性能，使用unordered_set（C++ 11）。

如果行爲不依賴於哪個規則匹配，那麼你也可以編譯從規則的正則表達式（如(niVVVd__xniVVd__)|(niVVVdxniVVd)）與像RE2的工具來獲得最壞情況O（ñ）行爲，其中n是輸入字符串的長度。

由於您比較平等，您不需要首先匹配最長的規則。