在預處理的大文本文件中搜索一行

Question

我有一個包含100,000行以上的數據文件，每行只包含兩個字段，鍵和值用逗號分開，所有的鍵都是唯一的。我想通過這個文件中的鍵來查詢值。將它加載到地圖是沒有問題的，因爲這會消耗太多的內存（代碼將在嵌入式設備上運行），並且我不想涉及數據庫。我要做到目前爲止預處理在我的電腦文件，即行進行排序，然後使用二進制搜索類似下面的預處理文件：

public long findKeyOffset(RandomAccessFile raf, String key) 
      throws IOException { 
     int blockSize = 8192; 
     long fileSize = raf.length(); 
     long min = 0; 
     long max = (long) fileSize/blockSize; 
     long mid; 
     String line; 
     while (max - min > 1) { 
      mid = min + (long) ((max - min)/2); 
      raf.seek(mid * blockSize); 
      if (mid > 0) 
       line = raf.readLine(); // probably a partial line 
      line = raf.readLine(); 
      String[] parts = line.split(","); 
      if (key.compareTo(parts[0]) > 0) { 
       min = mid; 
      } else { 
       max = mid; 
      } 
     } 
     // find the right line 
     min = min * blockSize; 
     raf.seek(min); 
     if (min > 0) 
      line = raf.readLine(); 
     while (true) { 
      min = raf.getFilePointer(); 
      line = raf.readLine(); 
      if (line == null) 
       break; 
      String[] parts = line.split(","); 
      if (line.compareTo(parts[0]) >= 0) 
       break; 
     } 
     raf.seek(min); 
     return min; 
    } 

我覺得還有比這更好的解決方案。任何人都可以給我一些啓示嗎？

Answer 1

數據是不可變的，而且鍵是唯一的（正如在問題的評論中提到的那樣）。

一個簡單的解決方案：寫你自己的哈希代碼來映射鍵與行號。

這意味着，離開排序，而是按照哈希算法告訴的順序將數據寫入文件。

當查詢密鑰時，您散列密鑰，獲取特定行號，然後讀取值。

從理論上講，您有一個O（1）解決方案來解決您的問題。

---

確保哈希算法有較少的碰撞，但我認爲，根據您的具體情況，一些碰撞應該沒問題。例如：3個鍵映射到相同的行號，因此您可以將它們全部寫在同一行上，並且當搜索到任何碰撞的鍵時，您將讀取該行的所有3個條目。然後在整個線上進行線性搜索（在這種情況下也稱爲O（3）aka恆定時間）。

Answer 2

一個簡單的算法來爲您具體限制優化性能：

1. 令n爲在原有的，一成不變的，整理文件的行數。
2. let k < n是一個數字（我們稍後會討論理想數字）。
3. 將文件分成k個文件，每個文件中的行數大致相等（因此每個文件都有n/k行）。這些文件將被稱爲F1 ... Fk。如果您希望保持原始文件不變，只需將F1 ... Fk視爲文件內的行號，將其切割爲段。
4. 用k行創建一個名爲P的新文件，每行i是Fi的第一個鍵。
5. 尋找密鑰時，首先使用O（logk）找到P的二進制搜索，找到需要去的文件/段（F1 ... Fk）。然後轉到該文件/段並在其中搜索。
6. 如果k足夠大，那麼Fi（n/k）的大小將足夠小，以加載到HashMap並檢索密鑰，其中O（1）。如果仍不實用，請執行O（log（n/k））的二分查找。

總搜索將O（的logK）+ O（的log（n/k））的，這是對O（logn）時間的改進是您的原始溶液。

我會建議找到一個足夠大的k，以便將特定的Fi文件/段加載到HashMap中，並且不會太大以填滿設備上的空間。最平衡的它sqrt（n），這使得解決方案運行在O（log（sqrt（n））），但這可能是一個相當大的P文件。如果你得到一個允許你將P和Fi加載到HashMap中進行O（1）檢索的k，那將是最好的解決方案。

Answer 3

這是怎麼回事？

#include <iostream> 
#include <fstream> 
#include <boost/algorithm/string.hpp> 
#include <vector> 

using namespace std; 

int main(int argc, char *argv[]) 
{ 
    ifstream f(argv[1],ios::ate); 
    if (!f.is_open()) 
     return 0; 
    string key(argv[2]),value; 

    int max = f.tellg(); 
    int min = 0,mid = 0; 
    string s; 
    while(max-min>1) 
    { 
     mid = min + (max - min)/2; 
     f.seekg(mid); 
     f >> s; 
     std::vector<std::string> strs; 

     if (!f) 
     { 
      break; 
     } 
     if (mid) 
     { 
      f >> s; 
     } 
     boost::split(strs, s, boost::is_any_of(",")); 
     int comp = key.compare(strs[0]); 
     if (comp < 0) 
     { 
      max = mid; 
     } 
     else if (comp > 0) 
     { 
      min = mid; 
     } 
     else 
     { 
      value = strs[1]; 
      break; 
     } 
    } 
    cout<<"key "<<key; 
    if (!value.empty()) 
    { 
     cout<<" found! value = "<<value<<endl; 
    } 
    else 
    { 
     cout<<" not found..."<<endl; 
    } 

    f.close(); 
    return 0; 
}