1

我目前正在开发一个小程序来连接两个文本文件（类似于数据库连接）。一个文件可能如下所示：


    269ED3
    86356D
    818858
    5C8ABB
    531810
    38066C
    7485C5
    948FD4

第二个类似：


    hsdf87347
    7485C5
    rhdff
    23487
    948FD4

这两个文件都有超过 1.000.000 行，并且不限于特定数量的字符。我想做的是在两个文件中找到所有匹配的行。

我已经尝试了一些东西，数组、向量、列表——但我目前正在努力决定什么是最好的（最快和容易记忆的）方法。

我的代码目前看起来像：



    #include iostream>
    #include fstream>
    #include string>
    #include ctime>
    #include list>
    #include algorithm>
    #include iterator>
    using namespace std;


    int main()
    {

        string line;

        clock_t startTime = clock();

        list data;
        //read first file
        ifstream myfile ("test.txt");
        if (myfile.is_open())
        {
            for(line; getline(myfile, line);/**/){
                data.push_back(line);
            }

            myfile.close();
        }

        list data2;
        //read second file
        ifstream myfile2 ("test2.txt");
        if (myfile2.is_open())
        {
            for(line; getline(myfile2, line);/**/){
                data2.push_back(line);
            }

            myfile2.close();
        }
        else cout  data2[k], k++
        //if data[j] > a;

        return 0;


    }

我的想法是：使用向量，对元素的随机访问非常困难，并且跳转到下一个元素不是最佳的（不是在代码中，但我希望你明白这一点）。通过使用 push_back 并逐行添加将文件读入向量也需要很长时间。使用数组，随机访问更容易，但是将 >1.000.000 条记录读入数组将非常占用内存并且也需要很长时间。列表可以更快地读取文件，随机访问又很昂贵。

最终，我不仅会寻找完全匹配，还会寻找每行的前 4 个字符。

你能帮我决定，最有效的方法是什么？我尝试过数组、向量和列表，但目前对速度并不满意。有没有其他方法可以找到我没有考虑过的匹配项？我很高兴完全更改代码，期待任何建议！

非常感谢！

编辑：输出应列出匹配的值/行。在此示例中，输出应如下所示：


    7485C5
    948FD4
4

3 回答 3

1

读取 200 万行不会太慢，可能会变慢的是您的比较逻辑：

利用 ：std::intersection

data1.sort(data1.begin(), data1.end()); // N1log(N1)
data2.sort(data2.begin(), data2.end()); // N2log(N2)

std::vector<int> v; //Gives the matching elements

std::set_intersection(data1.begin(), data1.end(),
                      data2.begin(), data2.end(),
                      std::back_inserter(v)); 

 // Does 2(N1+N2-1) comparisons (worst case)

您也可以尝试使用std::set两个文件中的行并将其插入其中，结果集将只有唯一元素。

于 2013-10-10T02:48:39.233 回答
0

一种解决方案是一次读取整个文件。

使用 istream::seekg 和 istream::tellg 计算两个文件的大小。分配一个足够大的字符数组来存储它们。使用 istream::read 在适当的位置将这两个文件读入数组。

这是上述功能的示例。

于 2013-10-10T02:35:43.877 回答
0

如果此值在第一个文件中是唯一的，则在利用O(nlogn)集合的特征时这将变得微不足道。下面将第一个文件中的所有行作为命令行参数传递给一个集合，然后O(logn)对第二个文件中的每一行执行搜索。

编辑：添加了仅 4 个字符的前导搜索。为此，该集合仅包含每行的前四个字符，并且从第二个开始的搜索仅查找每个搜索行的前四个字符。如果有匹配项，则完整打印第二个文件行。完整地打印第一个文件会更具挑战性。

#include <iostream>
#include <fstream>
#include <string>
#include <set>

int main(int argc, char *argv[])
{
    if (argc < 3)
        return EXIT_FAILURE;

    // load set with first file
    std::ifstream inf(argv[1]);
    std::set<std::string> lines;
    std::string line;
    for (unsigned int i=1; std::getline(inf,line); ++i)
        lines.insert(line.substr(0,4));

    // load second file, identifying all entries.
    std::ifstream inf2(argv[2]);
    while (std::getline(inf2, line))
    {
        if (lines.find(line.substr(0,4)) != lines.end())
            std::cout << line << std::endl;
    }

    return 0;
}
于 2013-10-10T02:51:15.627 回答