前処理された大きなテキストファイルの行を検索

Question

私は10万以上の行を含むデータファイルを持っています。各行には2つのフィールドがあり、キーと値はコンマで区切られています。私はこのファイルからキーで値を照会したい。それをマップにロードすることは、あまりにも多くのメモリを消費するため（コードは組み込みデバイス上で実行されるため）、DBを関与させたくないということは疑問です。

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; 
    } 

が、私はこれよりも良いソリューションがあると思います。私はこれまでやっていることは、すなわち、その後、前処理ファイルに以下のようにバイナリ検索を使用して、行を並べ替える、前処理に私のPC内のファイルです。誰か私に啓発を与えることができますか？

Answer 1

データは不変で、キーは固有です（この質問のコメントに記載されています）。

簡単な解決策：キーを行番号でマップするための独自のハッシングコードを作成します。

これは、並べ替えのままにしておき、ハッシングアルゴリズムが指示する順序でファイルにデータを書き込むことを意味します。

キーが照会されると、キーをハッシュし、特定の行番号を取得して値を読み取ります。

理論的には、問題に対するO（1）解決策があります。

---

ハッシュアルゴリズムの衝突が少ないことを確認してください。ただし、正確なケースによっては、いくつかの衝突が問題にならないと思います。例：3つのキーは同じ行番号にマッピングされ、3つの行を同じ行に書きます。衝突したキーのいずれかが検索されると、その行から3つの項目すべてが読み込まれます。次に線全体（この場合は別名O（3）ともいう）の検索を行います。

Answer 2

あなたの特定の制約のためにパフォーマンスを最適化するための簡単なアルゴリズム：

1. 不変、nは元の行数であるとするには、ファイルをソート。
2. 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元解決するO（LOGN）上の改善である（ログ（N/K））、。

特定のFiファイル/セグメントをHashMapに読み込むのに十分な大きさで、デバイスのスペースを埋めるには大きすぎないkを見つけることをお勧めします。最も均衡のとれたk it sqrt（n）は、O（log（sqrt（n）））ので実行されますが、それはかなり大きいPファイルです。あなたがO（1）検索のためのHashMapにPとFiをロードすることを可能にする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; 
}