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

Question

我有一个包含 100,000 多行的数据文件，每行仅包含两个字段，键和值以逗号分隔，并且所有键都是唯一。我想从此文件中按键查询值。将它加载到地图是毫无疑问的，因为这会消耗太多内存（嵌入式设备上的代码将运行）而且我不希望涉及数据库。到目前为止，我所做的是在我的 PC 中预处理文件，即对行进行排序，然后在预处理文件中使用二进制搜索，如下所示：

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

针对特定约束优化性能的简单算法：

令 n 为原始的、不可变的、排序的文件中的行数。
设k < n 为一个数（稍后我们将讨论理想数）。
将文件分成k个文件，每个文件的行数大致相等（因此每个文件有n/k行）。这些文件将被称为 F1...Fk。如果您希望保持原始文件完整，只需将 F1...Fk 视为文件中的行号，将其分成几段。
新建k行文件P，每行i为Fi的第一个key
在查找密钥时，首先使用 O(logk) 对 P 进行二分查找，以查找您需要查找的文件/段 (F1...Fk)到。然后转到 file/segment 并在其中搜索。
如果 k 足够大，则 Fi (n/k) 的大小将足够小以加载到 HashMap 并使用 O(1) 检索密钥。如果还是不行，再二分查找O(log(n/k)).

总搜索量将是 O(logk)+O(log(n/k))，这是对 O(logn ) 这是您的原始解决方案。

我建议找到一个足够大的 k 以允许您将特定的 Fi file/segment 加载到 HashMap 中，并且不要太大而无法在您的设备上填满 space。最平衡的 k 是 sqrt(n)，它使得解运行 in O(log(sqrt(n)))，但这可能是一个相当大的 P 文件.如果你得到一个 k 允许你将 P 和 Fi 加载到 HashMap 中以进行 O(1) 检索，那将是最好的解决方案。

Answer 2

数据是不可变的，键是唯一的（如问题评论中所述）。

一个简单的解决方案：编写您自己的散列代码以将键与行号映射。

这意味着，保留排序，而是按照哈希算法告诉的顺序将数据写入文件。

查询key时，对key进行hash，得到具体的行号，然后读取value。

理论上，您的问题有 O(1) 的解决方案。

确保散列算法具有较少的冲突，但我认为根据您的具体情况，一些冲突应该没问题。示例：3 个键映射到相同的行号，因此您将所有三个键都写在同一行上，并且当搜索到任何冲突的键时，您将从该行读取所有 3 个条目。然后在整行上进行线性搜索（在这种情况下也称为 O(3) 或常数时间）。

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

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

search a line in preprocessed big text file

java

algorithm

search

file

random-access