1

私は3つのファイルを持っています。F1、F2、F3。F1 は、200K エントリを持つプライマリ ファイルです。F2 と F3 には、エントリのスーパーセットまたはサブセット (300K または 100K) を含めることができます。私の目標は、F2 と F3 にはない F1 のエントリのリストに到達することです。これが私がこれまでに実装した方法です。

  1. F1 エントリを C++ STL マップにロードします。
  2. F2 の読み取りを開始します。エントリが一致する場合は、カウントを減らします (マップから消去しません)。カウント = 開始する F1 のサイズ。カウントが 0 の場合、F1 のすべてのエントリが既に F2 にあることがわかり、F2 をさらにトラバースしたり、F3 をトラバースしたりする必要はありません。
  3. マップからエントリを「消去」していない理由は、C++ STL マップがバイナリ ツリーであることを確認したからです。私のエントリを見ると、私のツリーがバランスのとれた二分木になることは絶対にありません。とても奥の深い木です。そのため、消去操作は高価であることが判明しています。検索操作もおそらくコストがかかりますが、消去操作では、削除するたびにツリーを再作成する必要があります。
  4. 問題は、F2 に存在するエントリのリストにどのように到達するかです。ブール値フラグ「found = true or false」を持つ構造体を維持する必要がありますか? F2 と F3 を使用した後、STL マップ全体を逆にたどって、= false が見つかった値を検索し、デルタをファイルに書き込み始めますか?

これを行うためのスマートで効率的な方法はありますか?

4

3 に答える 3

1

コメントで、入力は既にシーケンス処理されていると言っているので、コンテナーを完全に避けてください。

#include <iostream>
#include <fstream>
#include <string>
using namespace std;
int main()
{
    ifstream f1("f1.data"), f2("f2.data"), f3("f3.data");
    string f1entry, f2entry, f3entry; 

    while ( getline(f1,f1entry) ) {
        while ( f2 && f2entry < f1entry ) getline(f2,f2entry);
        while ( f3 && f3entry < f1entry ) getline(f3,f3entry);
        if ( f1entry != f2entry
          && f1entry != f3entry )
            cout << f1entry << '\n';

    }
}
于 2013-02-23T15:44:21.033 に答える
0

どこでこの結論を得たのかわかりません：

私のツリーがバランスのとれた二分木になる方法は絶対にありません。

しかし、それは間違っています。std::map がどのように機能するかについて奇妙な考えがあり、その考えに従って時期尚早に最適化しようとします。したがって、マップからアイテムを削除するだけで、そのマップの F2 および F3 から要素を削除した後に残るものが必要になります。標準マップが十分に高速でない場合は、unordered_map とも呼ばれるハッシュ マップを試してください。

PSおよびこれは設定およびunordered_setする必要があります

于 2013-02-23T05:08:20.550 に答える