1

データのグループがあるとします。

Data 1: (1, 2);
Data 2: (1, 3);
Data 3: (7, 8);
Data 4: (8, 20);

ここでのタスクは、データ セットに共通の要素がある場合、そのデータ セットを別のデータ セットとマージすることです。この例では、共通の番号 1 を共有しているため、データ 1 はデータ 2 とマージされます。データ 3 とデータ 4 も同様です。私の質問は、この関数を C++ で非常に効率的に実装するにはどうすればよいかということです。当面の間、私の実装は std::vector > data 構造に基づいています。これは、次のコードに示されています。

#include <iostream>
#include <map>
#include <set>
#include <algorithm>
#include <vector>


using namespace std;
bool find_the_element(const set<int> &mysets, const vector<int> &myvector)
{
    for(int i=0; i<myvector.size(); i++)
    {
        set<int>::iterator it;
        it = mysets.find(myvector[i]);
        if (it != mysets.end())
            return true;
    }
    return false;

}





int main () 
{



    set<vector<int> > myset;
    vector<int> a;
    a.push_back(1);
    a.push_back(2);

    vector<int> b;
    b.push_back(1);
    b.push_back(3);

    vector<int> c;
    c.push_back(7);
    c.push_back(8);

    vector<int> d;
    d.push_back(8);
    d.push_back(20);
    vector<vector<int> > my_vector_array;
    my_vector_array.push_back(a);
    my_vector_array.push_back(b);
    my_vector_array.push_back(c);
    my_vector_array.push_back(d);


    vector<set<int> > my_sets;
    for(int i=0; i<my_vector_array.size(); i++)
    {
        vector<int> temp_vector = my_vector_array[i];

        if (my_sets.empty())
        {
            set<int> temp_set;
            for(int j=0; j<temp_vector.size(); j++)
                temp_set.insert(temp_vector[j]);

            my_sets.push_back(temp_set);
        }
        else
        {
            bool b_find = false;
            for(int j=0; j<my_sets.size(); j++)
            {
                set<int>temp_set;
                temp_set = my_sets[j];
                if (find_the_element(temp_set,temp_vector))
                {
                    b_find = true;
                    my_sets[j].insert(temp_vector.begin(), temp_vector.end());

                    break;
                }

            }
            if (b_find)
            {
                // something already done
            }
            else
            {
                set<int> temp_set;
                for(int j=0; j<temp_vector.size(); j++)
                    temp_set.insert(temp_vector[j]);

                my_sets.push_back(temp_set);
            }

        }
    }
}

C++ にもっと効果的なデータ構造があるのか​​、それとも仕事をするための効率的なアルゴリズムがあるのか​​疑問に思っていました。ありがとう！

4

1 に答える 1

4

すばやくマージできるセットを実装する最も効率的な方法の 1 つは、Disjoint-set Data Structureを使用することです。

アイデアは、最初に各セットをリンクされたリストとして表し、リストの先頭がセット全体の識別子として機能することです。セットがマージされると、ノードはヘッドに再ポイントされ、さらなる検索が高速化されます。

リンクの記事には疑似コードがあります。C++ の実装はそれほど難しくありません。

mapこれまでに見た整数を素集合フォレスト内のノードと接続する別のものを保持する必要があります。データ セットを調べて、それらのアイテムを 1 つずつ取得し、 でアイテムを調べて、mapそのセットへのリンクをたどるか、追加するアイテムで新しい「シングルトン」分離セットを作成します。

于 2012-10-03T14:06:04.693 に答える