在C++中用於非常大的輸入的文件中搜索字符串的有效方法

我有一個包含數百萬行的主文件。然後，當從文件中讀取每行時，我需要在另一個文件中找到行少得多的行（僅數千行）來做出決定。目前，我正在使用vector來讀取第一個文件，然後對主文件中的每一行進行遍歷，以查找該行。問題是運行時間很長。是否有任何有效的方法來執行任務並將運行時間限制在一定的合理範圍內。在C++中用於非常大的輸入的文件中搜索字符串的有效方法

來源

2013-10-14 Timir

是否有一些獨特的屬性，你可以歸於每一行？一些哈希？您可以使用哪些數據功能減少搜索空間？然後將較小的數據集加載到內存中進行處理？在算法上思考並思考經濟問題，因爲目前您對原始數據進行了'O（n * m）'搜索，而且效率不高。 –

最小的數據集作爲字符串向量存儲在內存中。數據集中的每一行都有四列。每列中的值可能有冗餘值，但組合是唯一的。 – Timir

通過比較字符串長度，您可能會贏得一噸。如果它們不相等，則字符串不相等，如果它們相等，則確切知道應該比較多少個字符。 – MSalters

你可以嘗試用STD來取代第二（較小）向量組::。

來源

2013-10-14 10:38:17 zabulus

'unordered_set'將是更好的選擇。 – MSalters

你應該讀第二個文件到std::map<std::string,int>。 Map鍵是行，值是在第二個文件中遇到的次數。檢查

這樣的時間，如果從第一個文件指定行在第二個發現是恆定的，和你的運行總時間應在磁盤驅動器的速度僅限於讀取第一大文件的內容。

來源

2013-10-14 10:38:35 mvp

小心，地圖具有[對數複雜度]（http://en.cppreference.com/w/cpp/container/map）用於搜索，插入等。無論如何，它仍然比矢量的線性複雜性要好得多。 – Sigroad

問題僅在第二個文件中提到了幾千行 - 無需擔心。 – mvp

@mvp：很可能是「需要擔心的事情」;你對目標平臺一無所知。它可能是一臺洗衣機。 –

您有一個內部循環，其中主文件在輔助文件線的電流線進行比較。如果你採取一些堆棧樣本，你可能會在大部分時間內在內部循環中找到它。

你可能會考慮this technique，在那裏你你進行預處理輔助文件到一個專用的過程，你再編譯，並與主程序鏈接英寸花費的時間將是讀取輔助文件的時間，然後按照一秒或兩秒的順序編寫特殊用途過程，然後編譯並鏈接整個過程。

然後你的主程序的運行應該是I/O密集型閱讀的主要文件，因爲內循環會快很多。

來源

2013-10-14 13:08:12

在C++中用於非常大的輸入的文件中搜索字符串的有效方法

回答

相關問題