閱讀一個大文件來計算單詞的數量重複K次

Question

問題

有一個巨大的文件（10GB），一個具有讀取文件和打印出來的單詞數精確重複k倍在文件

我的解決方案

1. 使用ifstream讀取由字的文件字;
2. 插入Word成圖std::map<std::string, long> mp; mp[word] += 1;
3. 一旦文件被讀取時，發現所有詞語的地圖，讓字存在的k次

問題

1. 哪有多線程用於有效讀取文件[按塊讀取]？ OR 任何提高讀取速度的方法。
2. 有沒有比地圖更好的數據結構可以用來有效地找到輸出？

文件信息

1. 每行可以最大500個字長度的
2. 每個字都可以最多100個字符長度的

Answer 1

怎樣才能多線程用於有效讀取文件[按塊讀取]？或任何提高讀取速度的方法。

我一直在嘗試實際的結果，這是一個多線程的好東西，不像我以前的建議。非線程變量運行在1m44,711s，4線程（在4個內核上）運行在0m31,559s，而8線程（在4個內核+ HT上）運行在0m23,435s。主要改進 - 幾乎是加速的5倍。

那麼，你如何分擔工作量？將它拆分爲N個塊（n ==線程數），並且除了首先尋找第一個非單詞字符之外的每個線程。這是他們的邏輯塊的開始。他們的邏輯塊結束於它們的結束邊界，在該點之後被取整爲第一個非單詞字符。

並行處理這些塊，將它們全部同步到一個線程，然後使該線程執行結果合併。

爲了提高閱讀速度，你可以做的最好的下一件事是確保你儘可能不復制數據。通過內存映射文件讀取並通過將指針或索引保存到開始和結束來查找字符串，而不是累積字節。

有沒有比地圖更好的數據結構可以用來有效地找到輸出？

嗯，因爲我不認爲你會使用該命令，unordered_map是一個更好的選擇。我也將它作爲unordered_map<std::string_view, size_t> - string_view將其複製到比字符串更小的位置。

在剖析中，我發現53％的時間花在尋找包含給定單詞的確切桶上。

Answer 2

如果你有一個64位系統，那麼你可以記憶映射文件，並使用例如this solution to read from memory。

結合the answer from dascandy關於std::unordered_map和std::string_view（如果有的話），並且您應該儘可能快地獲得單個線程。您可以使用std::unordered_multiset而不是std::unordered_map，哪一個「更快」我不知道。

使用線程很簡單，只要做你知道的事情，但每個線程只處理部分文件。所有線程完成後合併地圖。 但是當您將文件拆分爲每個線程的塊時，則可能會在中間拆分單詞。處理這不是微不足道的。