如何加快列表比較/字符串替換？

我有一個小程序讀取包含類C宏的輸入文件。處理過程分兩次進行：第一次搜索宏定義並存儲它們，第二次搜索宏調用並擴展/替換它們。如何加快列表比較/字符串替換？

這一切都很好，但很耗時。目前，這是我要做的事：

foreach token in file: 
    foreach macro in macroDefinitions: 
     if token equals macro.name: 
      expand() 
     endif 
    end foreach 
endforeach

在這個僞例如，「令牌」是從源文件中的一句話，「宏觀」是從第一通宏定義。大約有20 000個宏定義和1800個輸入文件，總共需要處理約600 000行（並且每行被分成n個令牌）。這意味着總比較計數是（令牌計數）*（宏定義的計數）。我怎麼能加快速度？我錯過了什麼，還是我真的必須做所有這些比較？

有關其他信息，令牌是字符串[]數組中的字符串，而宏是ArrayList類型列表中的宏對象。我可以用其他類型的數據結構來加速進程嗎？

來源

2013-04-16 manabreak

類C宏需要在使用前定義，所以你只需要1次通過文件。 – Dukeling

我有很多文件，並且這些宏被用於交叉文件。:) – manabreak

您需要使用從宏名稱映射到其定義的Map。

在僞代碼：

for each token in file: 
    if this is a macro defininition: 
     name, definition <- parse definition 
     map.put(name, definition) 

for each token in file: 
    if map.contains(token): 
     definition <- map.get(token): 
     expand definition

（更新 - 你可以擺脫contains通話並調用get，然後測試null這是值得一讀的javadoc，以獲得更好的理解。 Map，TreeMap和HashMap API的工作原理）

Map的典型實現使用平衡二叉樹或散列表，並且具有複雜的查找和插入操作O(logN)或O(1)（正常情況下）。

來源

2013-04-16 10:53:17

謝謝！試圖通過將當前ArrayList轉換爲HashMap，並且執行時間從7分鐘下降到不到一分鐘。 :)當我從頭開始構建HashMap時，它會變得更快！ – manabreak

我會建議創建一個腳本，例如在Perl實際上執行文件處理並使用ProcessBuilder從您的Java代碼調用該腳本。
爲每個問題使用最好的工具。

來源

2013-04-16 10:38:17 Cratylus

我不能使用除Java以外的任何其他語言。 – manabreak

@manabreak：使用java調用腳本。該腳本將只是一個文件（甚至可能是專家的一行代碼）並提供它。 – Cratylus

將宏定義放在Map中將顯着減少查找宏所需的時間。

來源

2013-04-16 10:39:36

編輯：如果您可以添加密鑰，KlasLindbäck解決方案會更好。如果你不能按照我的建議搜索算法，那麼這將是提高搜索速度的一種方法。

你可以添加一些搜索算法，如Binary search這將極大地改善搜索結果

來源

2013-04-16 10:41:40 Sem

可以使用HashSet包含的宏定義和每個令牌的名稱，檢查它是否包含在集：

for(String token : token) { 
    if(macroNamesSet.contains(token)) { 
     expand(); 
    } 
}

contains方法將O（1）時間。因此，總體而言，一旦創建了一組宏名稱，就需要（令牌計數）時間。

來源

2013-04-16 10:43:40

'Set'是一個接口，因此如何實現的'contains'尚未定義。 2實現：對於'HashSet'' contains'需要'O（1）'。對於'TreeSet''contains'需要'O（log n）'。 – Dukeling

是啊。我將其更改爲HashSet ... –

如何加快列表比較/字符串替換？

回答

相關問題