ソートされたベクトルからソートされたサブベクトルを獲得する方法、高速

StackOverflow https://stackoverflow.com/questions/4308912

質問

私は次のようなデータ構造を持っています：

struct X {
  float value;
  int id;
};

それらのベクトル（サイズ n （100000を考えてください）、ソート 価値 （プログラムの実行中は一定のままです）：

std::vector<X> values;

今、私は関数を書きたいです

void subvector(std::vector<X> const& values, 
               std::vector<int> const& ids, 
               std::vector<X>& out /*, 
               helper data here */);

それがいっぱいです アウト のソート付きサブセットを持つパラメーター 値, 、合格者によって与えられます IDS （サイズ m < n （約0.8倍 n)), 速い （メモリは問題ではなく、これは繰り返し行われるため、見た目を構築します（ ヘルパーデータ 関数パラメーターから）または一度だけ行われた他の何かは完全に問題ありません）。

これまでの私の解決策：
見た目が良いものを構築します lut 含む ID - >オフセット 値 （準備、一定のランタイム）
作成 std::vector<X> tmp, 、サイズn、無効なIDで満たされている（in線形 n)
各IDについて、コピーします values[lut[id]] に tmp[lut[id]] （線形in m)
ループオーバー TMP, 、アイテムをコピーします アウト （線形in n)

これは線形です n （それはより大きいので m）、しかし、一時的な変数と繰り返されるコピーは私を悩ませます。これよりも早くそれを行う方法はありますか？ご了承ください m 近くになります n, 、だからo（m ログ n）不利です。

編集： http://ideone.com/xr8vp 上記のアルゴリズムのサンプル実装であり、目的の出力を明確にし、線形時間で実行可能であることを証明するために、問題は一時的な変数を回避したり、他の方法でスピードアップする可能性についてです。もっと早く ：）。

役に立ちましたか？

解決

試してみることができる別のアプローチは、ベクトルの代わりにハッシュテーブルを使用してIDを検索することです。

void subvector(std::vector<X> const& values, 
               std::unordered_set<int> const& ids, 
               std::vector<X>& out) {

    out.clear();
    out.reserve(ids.size());
    for(std::vector<X>::const_iterator i = values.begin(); i != values.end(); ++i) {
        if(ids.find(i->id) != ids.end()) {
            out.push_back(*i);
        }
    }
}

これは線形時間で実行されます unordered_set::find 一定の予想時間です（INTをハッシュするのに問題がないと仮定します）。ただし、実際には、最初にベクトルを使用して説明したアプローチほど速くないのではないかと思います。

他のヒント

ベクトルがソートされ、そのサブセットが同じようにソートされたいので、再配置せずに必要なチャンクをスライスできると思います。

Find_if（）を2回使用してみませんか。必要な範囲の開始を見つけ、一度は範囲の終わりを見つけるために一度。これにより、サブベクトルの開始および終了イテレーターが得られます。これらの反復器を使用して新しいベクトルを構築します。ベクトルの1つ コンストラクタ オーバーロードには2つの反復器が必要です。

それまたは パーティション アルゴリズムは機能するはずです。

問題を正しく理解した場合、実際に線形時間並べ替えアルゴリズムを作成しようとします（数字mの入力サイズの対象となります）。それは不可能です。

現在のアプローチは、可能な値のソートされたリストを持つことです。これには、可能な値nの数に線形時間がかかります（理論的には、マップ検索にO（1）時間がかかることを考えると）。

あなたができる最善のことは、Mの小さな値に対して、クイックソートメソッド（O（MLOGM）FEクイックソート、MergESORTなど）で値（マップから見つかった）を並べ替え、Mのより大きな値を線形検索することを行うことです。 。たとえば、nが100000、mが100の場合、ソートアルゴリズムを使用するだけではるかに高速です。

私が言っていることを理解できることを願っています。あなたがまだ質問があるならば、私はそれらに答えようとします:)

編集：（コメント）私が意味することをさらに説明します。あなたの数字は1から100の範囲であることを知っているとしましょう。あなたはそれらをどこかでソートして（実際には「自然に」ソートされています）、ソートされた形でそれらのサブセットを取得したいとします。 O（N）またはO（MLOGM）よりも速く実行できる場合、ソートアルゴリズムはこの方法を使用してソートするだけです。

数字のセット{5,10,3,8,9,1,7}を使用することで、それらがソートされた数字のセットのサブセットであることを知って{1,2,3,4,5,6,7、 8,9,10} o（n）（n = 10）またはo（mlogm）（m = 7）よりも速くソートすることはできません。

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top