0

さまざまなフィールドに基づいて大規模なデータセットを検索するための最良の方法は何かを知りたい. たとえば、Person オブジェクトは次のように定義されます。

Person:
    first name
    last name
    phone numbers

Person タイプのオブジェクトが 10 万個あり、フィールドのいずれかに基づいて特定の人物を検索したいですか?

O(logn) 時間で検索操作を実行できるように、さまざまなフィールドを使用してデータ セットを並べ替えようとしましたが、それが正しい方法ではないことはわかっています。

4

2 に答える 2

1

あなたが試すことができますBoost.MultiIndex：

Boost Multi-index Containers Library は、multi_index_container という名前のクラス テンプレートを提供します。これにより、異なる並べ替えとアクセス セマンティクスを持つ 1 つ以上のインデックスを維持するコンテナーの構築が可能になります。

しかし、自分で試してみたい場合、最も簡単な解決策の 1 つは、すべてのデータに対して 1 つのコンテナーを使用し、さらに適切なインデックスを使用して複数のマップを維持することです。

class Indixer
{
    vector<Record> values; // without specific order
    unordered_map<field_type1, Record*> index1; // Search: O(1) average
    unordered_map<field_type2, Record*> index2; // Search: O(1) average
    map<field_type3, Record*> index3; // Search: O(log N) worst case
public:
    // ...
};

std::unordered_mapO(1) 平均アクセスを取得するために使用できます。次に例を示します。

#include <initializer_list>
#include <unordered_map>
#include <functional>
#include <algorithm>
#include <iostream>
#include <iterator>
#include <utility>
#include <vector>
#include <string>
using namespace std;

struct Record
{
    string first_name, last_name;
};

class Indexer
{
    typedef vector<Record> Container;
    typedef Record *Handle;
    Container values;
    unordered_map<string, Handle> first_name_index, last_name_index;

public:
    Indexer(Container &&x) : values(move(x))
    {
        for(auto &x : values)
        {
            first_name_index[x.first_name] = &x;
            last_name_index[x.last_name] = &x;
        }
    }
    const Record &first_name(const string &x)
    {
        return *first_name_index[x];
    }
    const Record &last_name(const string &x)
    {
        return *last_name_index[x];
    }
};

int main()
{
    vector<Record> v = {{"F1", "L1"}, {"F2", "L2"}};
    Indexer x(move(v));

    cout << x.first_name("F1").last_name << endl;
    cout << x.first_name("F2").last_name << endl;

    cout << x.last_name("L1").first_name << endl;
    cout << x.last_name("L2").first_name << endl;
}

出力は次のとおりです。

L1
L2
F1
F2

Coliru でのライブデモ

于 2013-10-30T19:25:29.013 に答える