如何用Ruby快速計算字符串中子字符串的出現次數

Question

我有一個文本文件大小爲300MB，我想計算文件中每個10,000個子字符串的出現次數。我想知道如何快速做到這一點。

現在，我使用下面的代碼：

content = IO.read("path/to/mytextfile") 
Word.each do |w| 
    w.occurrence = content.scan(w.name).size 
    w.save 
end 
 

字是ActiveRecord類。

我花了差不多1天時間完成計算。無論如何要做得更快？謝謝。

編輯1： 再次感謝您。我正在運行rails 2.3.9。 name字段表中包含我正在搜索的內容，並且它僅包含唯一值。而不是使用Word.each，我使用批次（每次1000行）加載。它應該有所幫助。

我用bpaulon的思想重新編寫了整個代碼。現在只需要幾個小時就可以完成計數。

我異型新版本的代碼，現在最大的時間成本計算方法是UTF8編碼支持的字符串截斷碼

def truncate(n) 
    self.slice(/\A.{0,#{n}}/m) 
end 

和字符計數代碼

def utf8_length 
    self.unpack('U*').size 
end 

任何其他更快的方法來替代它們？

Answer 1

我想你可以解決這個問題不同

你並不需要掃描的文件很多次，你可以創建一個數據庫，想在mongo或mysql，併爲每個你找到的話，你取數據庫爲它，然後添加一些「計數器」字段。

你可以問我「但我必須掃描我的數據庫很多，這可能需要更多」。那麼，確定你不會問這個問題，但不會花費更多時間，因爲數據庫集中在IO中，除此之外你總是可以使用index it。

---

編輯：沒有辦法在所有劃定？讓我們說，你有一個Word.name字符串，你真的擁有一個（而不是簡單的）正則表達式。正則表達式是否包含\ n？那麼，如果正則表達式可以包含任何值，則應該估計正則表達式可以獲取的字符串的最大大小，將其加倍，然後通過該字符集來掃描文件，但將光標移動該數字。

可以說你對你的正則表達式可以獲取的最大值的估計就像你的文件有0到30000個字符的20個字符。你通過每個正則表達式，你有0到40個字符，然後再從20到60，從40到80等...

你還應該保持你找到的更小的正則表達式的位置，所以它不會重複。

最後，這個解決方案似乎不值得你付出努力，你的問題可能基於那些正則表達式有更大的解決方案，但它會比調用掃描Words.count時間更快的300Mb字符串更快。

Answer 2

您使用scan會創建一個數組，計算它的大小，然後將其丟棄。如果您在大文件中出現大量子字符串，您將暫時創建一個大數組，但可能會耗費內存管理的CPU時間，但即使在300MB的情況下，該時間仍應該很快運行。

因爲Word是一個ActiveRecord類，它依賴於數據庫中的模式和索引，以及數據庫服務器可能遇到的任何問題。如果數據庫未優化或響應速度緩慢，或者用於檢索數據的查詢效率不高，則迭代速度會很慢。你可能會發現它抓住Word的組合很快，因此它們在RAM中，然後迭代它們。

而且，如果數據庫和你的代碼是在同一臺機器上運行，你可以從資源約束痛苦的樣子只有一個驅動器，沒有足夠的RAM等

不知道更多關於你的環境和硬件這很難說。

---

編輯：

我可以抓住子到一個數組/哈希第一，則計數結果添加到數組或哈希，並且所有的計數是後的結果寫回到數據庫完成。你認爲它會更快，對吧？

沒有，我懷疑這將有很大的幫助，而且，不知道問題出在哪裏你可能做的是使問題變得更糟，因爲你必須加載10000條記錄從數據庫對象，然後再建一個10000個元素的散列或數組，這些元素也將與DB記錄一起存儲在內存中，然後寫出它們。

Ruby目前只能使用一個核心，但您可以通過使用Ruby 1.9+來獲得速度。我建議使用installing RVM並讓它管理你的Ruby。請務必閱讀該頁面上的說明，然後運行rvm notes並按照這些說明操作。

你的Word模型和底層模式和索引是什麼樣的？數據庫是否在同一臺機器上？

---

編輯：從看你的表模式，你有除了id無索引這確實幫助不大正常的查找窗口。我建議在Stack Overflow的兄弟網站https://dba.stackexchange.com/上展示你的模式，並解釋你想要做什麼。至少我會在文本字段中添加一個鍵，以幫助避免對您執行的任何搜索進行全表掃描。

有什麼可以幫助更多的是從「Active Record Query Interface」中讀取：Retrieving Multiple Objects in Batches。

另外，看看您的Word.each正在運行時發出的SQL。是不是像"select * from word"？如果是這樣的話，Rails會在10,000條記錄中逐個迭代它們。如果它類似於"select * from word where id=1"，那麼對於每次更新計數的記錄，您都會讀取數據庫，然後寫入數據。這是「批量檢索多個對象」鏈接將有助於解決的情況。

此外，我猜content是您正在搜索的文本，但我無法確定。是否有可能您有重複的文本值，導致您對同一文本進行多次掃描？如果是這樣，請在該字段上使用unique條件選擇記錄，然後一次更新所有匹配記錄的計數。

你是否對你的代碼進行了剖析，看看Ruby本身是否可以幫助你找出問題所在？修改你的代碼來處理100或1000條記錄。用-r profile標誌啓動應用程序。當應用程序退出分析器時，將輸出一個表格顯示時間花費在哪裏。

你正在運行哪個版本的Rails？

Answer 3

您可以將整個「Word」表加載到Trie中，然後執行反向跟蹤，因爲您說文本中沒有分隔符。

因此，對於文本中的每個字符，沿着三字之下。如果你打了一個字，增加它的計數。 「走下來」涉及三種情況：

1. 這個角色沒有節點。 （如果你是中間搜索，彈出後退堆棧）
2. 這個角色有一個節點。 （但它不是一個字）
3. 這個角色有一個節點。 （這是一個字 - 增量和「髒」）

追溯只是跟蹤你想要去的地方，你已經用盡了Trie的這個「搜索」，這是當你用完節點訪問。這可能是你訪問的每個角色都是Trie的根源。

完成此操作後，您可以訪問您更改的所有節點並更新它們所代表的記錄。

這將需要一些時間來實現，但肯定會比每個&掃描更快。