1

私は現在、2 つのテキスト ファイルを結合する小さなプログラムに取り組んでいます (データベース結合に似ています)。1 つのファイルは次のようになります。


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

2番目のものは似ています：


    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 行ずつ追加してファイルをベクトルに読み込むには、長い時間がかかります。配列を使用すると、ランダム アクセスが簡単になりますが、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

1 つの解決策は、ファイル全体を一度に読み取ることです。

istream::seekg と istream::tellg を使用して、2 つのファイルのサイズを計算します。両方を格納するのに十分な大きさの文字配列を割り当てます。istream::read を使用して、適切な場所で両方のファイルを配列に読み込みます。

上記の関数の例を次に示します。

于 2013-10-10T02:35:43.877 に答える
0

この値が最初のファイルで一意である場合O(nlogn)、セットの特性を利用するときにこれは簡単になります。以下は、コマンドライン引数としてセットに渡された最初のファイルのすべての行を格納しO(logn)、2 番目のファイルの各行を検索します。

編集: 4 文字のみのプリアンブル検索を追加しました。これを行うために、セットには各行の最初の 4 文字のみが含まれ、2 番目からの検索では各検索行の最初の 4 文字のみが検索されます。一致する場合、2 番目のファイル行全体が出力されます。最初のファイルを全行で印刷するのは、もう少し難しいでしょう。

#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 に答える