優化字符串。替換方法

我有一個不允許在網站上的200多個單詞的列表。下面的string.Replace方法需要約80ms。如果我將s < 1000增加10.00倍至s < 10,000，則延遲時間將增加至約834ms，增加10.43倍。我擔心這個函數的可伸縮性，特別是如果列表的大小增加。我被告知字符串是不可變的，並且text.Replace()正在內存中創建200個新字符串。有沒有類似Stringbuilder這個？優化字符串。替換方法

List<string> FilteredWords = new List<string>(); 
FilteredWords.Add("RED"); 
FilteredWords.Add("GREEN"); 
FilteredWords.Add("BLACK"); 
for (int i = 1; i < 200; i++) 
{ FilteredWords.Add("STRING " + i.ToString()); } 

string text = ""; 

//simulate a large dynamically generated html page 
for (int s = 1; s < 1000; s++) 
{ text += @"Lorem ipsum dolor sit amet, minim BLACK cetero cu nam. 
      No vix platonem sententiae, pro wisi congue graecis id, GREEN assum interesset in vix. 
      Eum tamquam RED pertinacia ex."; } 

// This is the function I seek to optimize 
foreach (string s in FilteredWords) 
{ text = text.Replace(s, "[REMOVED]"); }

來源

2013-10-19 Zerkey

爲什麼這些詞不允許？有很多方式可以表達不被過濾而被阻止的單詞。 –

顯然，顏色是佔位符。關鍵詞，褻瀆，html標籤，腳本等需要被明顯地清除。我們有一個列表。請詳細說明「未經過濾被阻止」。 – Zerkey

我會嘗試使用正則表達式。當你有很長的表情時，它也會變得越來越慢，但它值得一試。另一種選擇是編寫自己的Replace方法 - 查看整個字符串，嘗試查找被阻止的單詞中的每個單詞 – Ondra

使用StringBuilder.Replace並嘗試將其作爲批處理操作。也就是說，您應該嘗試僅創建StringBuilder一次，因爲它有一些開銷。它不一定會快得多，但它會更有效地提高內存。

你也應該只做一次衛生設施，而不是每次請求數據。如果您正在從數據庫中讀取數據，則應在數據插入數據庫時考慮進行一次消毒處理，以便在閱讀頁面並將其顯示到頁面時執行更少的工作。

來源

2013-10-19 06:06:14

感謝您的意見。當數據插入數據庫時，你應該考慮清理一次數據。 - 我希望能夠看到過濾後的單詞在我的末尾，否則，這是非常好的建議。 – Zerkey

@Zekey - 「我希望能夠看到過濾後的單詞在我的最後」 - 然後存儲已清理和未清理的文件（如果它們不同）。如果它們是相同的，我想他們可能大部分時間都是這樣，然後只存儲一次以節省空間。 – Joe

@Joe輝煌。謝謝。 – Zerkey

如果您希望大部分文本比掃描整個文本相對較好，比較好的方法可能會更好。您還可以同時標準化單詞文本以獲取一些標準替換。

I.e.通過匹配各個單詞（即正則表達式如"\w+"）掃描字符串，而不是在要替換的單詞字典中檢測到的每個單詞查找（潛在規格化值）。

您可以簡單地掃描第一個拿到「字來代替」名單，後來不僅僅是替換單詞或掃描，並建立導致在同一時間字符串（使用StringBuilder或StreamWriter，顯然不是String.Concat/+）。

注意：Unicode提供了大量的好用字符，所以不要指望你的努力會非常成功。即嘗試在下面的文字中找到「酷」：「你很蠢」。

示例代碼（依據Regex.Replace進行標記並構建字符串，HashSet用於匹配）。

var toFind = FilteredWords.Aggregate(
     new HashSet<string>(), (c, i) => { c.Add(i); return c;}); 

text = new Regex(@"\w+") 
    .Replace(text, m => toFind.Contains(m.Value) ? "[REMOVED]" : m.Value));

來源

2013-10-19 06:05:54

好的，我試過了。這是一個可怕的想法。 <1000「完成了2031毫秒，」<10000「完成了將近兩分鐘的時間。檢查一個字符串是否存在一個字比檢查列表/字典/散列的每個「\ w +」匹配要有效得多。 – Zerkey

@Zekey - 我已經添加了我的代碼示例...它顯示了您的代碼的4倍改進。我不知道爲什麼你的版本慢得多（沒有代碼很難推理）。 –

可能有更好的辦法，但這是我將如何去解決問題。

您將需要創建一個樹結構，其中包含要替換的單詞字典。這個類可能是這樣的：

public class Node 
{ 
    public Dictionary<char, Node> Children; 
    public bool IsWord; 
}

使用兒童字典可能不是最好的選擇，但它提供了最簡單的例子。此外，您將需要一個構造函數來初始化Children字段。 IsWord字段用於處理編輯的「單詞」可能是另一個編輯的「單詞」的前綴的可能性。例如，如果你想刪除「紅色」和「補救」。

您將從每個替換字中的每個字符構建樹。例如：

public void AddWord (string word) 
{ 
    // NOTE: this assumes word is non-null and contains at least one character... 

    Node currentNode = Root; 

    for (int iIndex = 0; iIndex < word.Length; iIndex++) 
    { 
     if (currentNode.Children.ContainsKey(word[iIndex]))) 
     { 
      currentNode = currentNode.Children[word[iIndex]; 
      continue; 
     } 

     Node newNode = new Node(); 
     currentNode.Children.Add(word[iIndex], newNode); 
     currentNode = newNode; 
    } 

    // finished, mark the last node as being a complete word.. 
    currentNode.IsWord = true; 
}

您需要處理區分大小寫的地方。此外，您只需構建樹一次，然後您可以從任意數量的線程使用它，而不用擔心鎖定，因爲您只能從中讀取數據。（基本上，我說：它存儲在一個靜態的地方。）

現在，當你準備刪除您的字符串的話，你需要做到以下幾點：

創建StringBuilder實例存儲結果
解析通過您的源字符串，尋找「單詞」的開始和停止。你如何定義「單詞」將很重要。爲了簡單起見，我建議從Char.IsWhitespace開始定義單詞分隔符。
一旦確定某個字符範圍是一個「單詞」，從樹的根部開始，找到與「單詞」中第一個字符關聯的子節點。
如果你沒有找到一個子節點，如果發現一個子節點整個單詞添加到StringBuilder
，則繼續下一個字符對當前節點的兒童匹配，直到您用完字符或節點外。
如果到達「單詞」的末尾，請檢查最後一個節點的IsWord字段。如果排除true這個詞，請不要將它添加到StringBuilder。如果IsWord爲false，則該單詞不會被替換，而是將其添加到StringBuilder
重複此操作，直到用盡輸入字符串。

您還需要將字詞分隔符添加到StringBuilder，希望在分析輸入字符串時這會很明顯。如果您小心只使用輸入字符串中的開始和結束索引，則應該能夠解析整個字符串而不創建任何垃圾字符串。

當所有這些都完成後，使用StringBuilder.ToString()來獲得最終結果。

您可能還需要考慮Unicode代用代碼點，但您可以可能不用擔心它。

請注意，我直接在此輸入此代碼，因此可能包含語法錯誤，拼寫錯誤和其他意外錯誤導向。

來源

2013-10-19 06:21:59 William

爲什麼要構建自定義數據結構？一個基本的HashSet可能會明顯更快，並且內存使用量要低得多。如果有很多類似的詞，那麼基數樹可能是有道理的，但只有幾百個我懷疑它。 –

當然，'HashSet'可以用來存儲單詞列表。 OP似乎擔心垃圾字符串的創建。每個「單詞」必須被分配到一個新的字符串中，作爲「HashSet」中的一個鍵，這將導致更多的垃圾創建。 – William

謝謝你這樣深入的回答。 – Zerkey

真正的正則表達式的解決辦法是：

var filteredWord = new Regex(@"\b(?:" + string.Join("|", FilteredWords.Select(Regex.Escape)) + @")\b", RegexOptions.Compiled); 
text = filteredWord.Replace(text, "[REMOVED]");

我不知道這是否是更快（但要注意，它也只替換整個單詞）。

來源

2013-10-19 14:23:25 Ryan

優化字符串。替換方法

回答

相關問題