1

私が必要としているのは、数値のベクトルによって評価される、文字列キーを持つ順序付きの連想コンテナーです。さらに、O(1)挿入時間が必要です。

私の説明は抽象的に聞こえますが、シナリオを示します。

オンラインテストがあります。人がこのテストを受けると、彼の名前がデータベースに追加されます。必要に応じて、繰り返しテストを受けることができます。すべてのスコアは、その名前で記録されます (これは一意です)。たとえば、デビッド、トム、アリスが何度か試験を受けに来ます。プログラムは、次の形式で出力を出力できるはずです。

Alice 65 70 84
David 98 97 93
Tom   100 45 
...

ご覧のとおり、それらの名前は辞書順に印刷されているはずです。誰かがテストを受けるたびに、そのスコアがデータベースに追加されます。たくさんの人が試験を受けに来るので、これはO(1)時間の複雑さに違いありません。ただし、データベースの印刷も頻繁に行われます。毎秒言ってください。したがって、各ディスプレイで明示的にソートする必要がないことが有利です。

ここで使用できるデータ構造は何ですか? （STLが推奨されます。）挿入できるため、現在使用しunordered_mapていますが、キーを辞書順で反復することはできません。O(1)

4

3 に答える 3

4

O(1)挿入して順序付けされた反復を提供できるコンテナをO(n)使用して、文字列を線形時間でソートできます。

コンパレーターベースの並べ替えには の下限があるため、このコンテナーはコンパレーターだけでは機能しないとすぐに結論付けることができO(n log n)ます。

線形時間で並べ替える並べ替えアルゴリズムはごくわずかであり、通常、機能するにはキー空間の知識が必要です。このようなアルゴリズムの漸進的な「オンライン」バージョンは役に立つ可能性があり、それが使用する漸進的に構築された内部データはコンテナになります。

ここでは、線形時間ソート アルゴリズムについて説明します。

于 2013-03-30T06:22:27.617 に答える
1

この場合の実際のO(1)操作は非常に複雑な問題であり、STL の使用を好むことを考慮すると、次のデータ構造のようなものをお勧めします。これが Big-Oh の要件を満たさないというわけではなく、STL を使用しても実装できる最も効率的な方法ではありませんが、シンプルで効率的です。

主なデータ構造はstd::map. std::unordered_mapしかし、O(1) へのルックアップを高速化するには、次のように使用できます。

using std::map, std::string, std::vector, std::unordered_map;

typedef map<string, vector<int> > TestTakersMap;
typedef unordered_map<string, TestTakersMap::iterator> LookupAccelerator;

これで、さまざまな操作が次のようになります。

  • 新しい人物の追加: マップに挿入しますが、新しいレコードを unordered_map に挿入したマップに名前とイテレータも追加します。O(ログ(N)) .
  • 人を調べる: unordered_map を使用して、その人のイテレータとデータを取得できます。O (1)が必要です。
  • Add a new score : unordered_map を使用して人を見つけ、取得したイテレータを使用して新しいスコアを追加します。償却 O(1)。
  • すべての名前とスコアの出力: マップ自体を反復処理し、並べ替え手順を追加せずに名前を辞書順に取得します。O(S)と見なすことができます。ここで、Sはすべての参加者のスコアの合計数です。

このすべてにおいて、ボトルネックはキャッシュになることに注意してください。このすべてのポインターがメモリ内で追跡およびジャンプしても、まったく役に立ちません。もちろん、これは他のいくつかの要因に依存します。たとえば、実際に獲得した名前の数、1 人あたりのスコア数、新しい人物を追加する頻度、新しいスコアを追加する頻度、すべてのスコアを印刷する頻度などです。名前とスコア、1 人あたりおよびテストあたりのデータの量と必要量など。

UPDATE : 次のような基本的な操作を実行できます。インクルードなどは次のようになります。

#include <map>
#include <string>
#include <unordered_map>
#include <vector>

using std::map;
using std::string;
using std::unordered_map;
using std::vector;

これは、必要な操作のいくつかを実行するための非常に単純なクラスです。私は C++11 の機能 ( auto、emplace、 ...) を使用していますが、このコードを特に優れたプログラミング スタイルとは見なしていないことに注意してください。私はそれを保証することはできません。

class TestScores
{
private:
    typedef int ScoreType;
    typedef vector<ScoreType> ScoreList;
    typedef map<string, ScoreList> TestTakersMap;
    typedef unordered_map<string, TestTakersMap::iterator> LookupAccelerator;

public:
    bool hasName (string const & new_name) const
    {
        return m_lookup.end() != m_lookup.find (new_name);
    }

    // Returns true if the name is really new
    bool addName (string const & new_name)
    {
        if (hasName(new_name))
            return false; // name already in there

        auto i = m_takers.emplace (new_name, vector<int>()).first;
        m_lookup.emplace (new_name, i);

        return true;
    }

    ScoreList const & getScores (string const & name) const
    {
        // This redirects to the private, non-const version
        return const_cast<TestScores *>(this)->getScores(name);
    }

    void addScore (string const & name, ScoreType new_score)
    {
        getScores(name).push_back (new_score);
    }

private:
    // If the name doesn't already exist, it is added!
    ScoreList & getScores (string const & name)
    {
        if (!hasName(name))
            addName (name);

        return m_lookup[name]->second;
    }

private:
    TestTakersMap m_takers;
    LookupAccelerator m_lookup;
};
于 2013-03-30T07:17:18.073 に答える