在预处理的大文本文件中搜索一行

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