12

次のようなデータ構造があります。

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 */);

これは、渡されたID (サイズM < N ( Nの約 0.8 倍) )で指定された、並べ替えられた値のサブセットでoutパラメータを埋めます。関数パラメーターからのヘルパー データ) または 1 回だけ実行される何かは完全に問題ありません)。

これまでの私の解決策: idを含む
ルックアップテーブルlutを作成 ->値のオフセット(準備、したがって一定の実行時間) create 、サイズ N、各 id の無効な id ( Nで線形)で埋められ、 tmpを介して ( Mで線形) ループ にコピーされます、項目をoutにコピー ( Nで線形)
std::vector<X> tmp
values[lut[id]]tmp[lut[id]]

これはNで線形です ( Mよりも大きいため) が、一時変数と繰り返されるコピーは私を悩ませます。これよりも速くする方法はありますか？MはNに近いため、O( M log N ) は好ましくないことに注意してください。

編集: http://ideone.com/xR8Vpは、前述のアルゴリズムのサンプル実装であり、目的の出力を明確にし、線形時間で実行可能であることを証明します。問題は、一時変数を回避するか、高速化する可能性についてです他の方法では、線形ではないものは高速ではありません:)。

4

3 に答える 3

2

別の方法として、ベクターの代わりにハッシュ テーブルを使用して 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 のハッシュに問題がないことを前提としています)。ただし、ベクトルを使用して最初に説明したアプローチほど実際には高速ではない可能性があると思います。

于 2010-11-30T01:39:44.847 に答える
1

ベクターはソートされており、そのサブセットを同じ方法でソートする必要があるため、再配置せずに必要なチャンクをスライスするだけでよいと思います。

find_if() を 2 回使用しないのはなぜですか。1 回目は目的の範囲の開始点を見つけ、もう 1 回は範囲の終わりを見つけます。これにより、サブベクターの開始イテレータと終了イテレータが得られます。これらの反復子を使用して新しいベクトルを構築します。ベクトルコンストラクターのオーバーロードの 1 つは、2 つの反復子を取ります。

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

于 2010-11-29T23:01:56.833 に答える
0

私があなたの問題を正しく理解していれば、実際に線形時間ソートアルゴリズムを作成しようとしています (数値 M の入力サイズに従います)。それは不可能です。

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

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

私の言っていることが理解できると思います。まだ質問がある場合は、答えようとします:)

編集：（コメント）私が何を意味するのかをさらに説明します。数値の範囲が 1 から 100 であることがわかっているとします。数値をどこかで並べ替えて (実際には "自然に" 並べ替えられています)、並べ替えられた形式でそれらのサブセットを取得したいとします。O(N) または O(MlogM) よりも高速に実行できる場合、並べ替えアルゴリズムはこの方法を使用して並べ替えます。

Fe は、一連の数字 {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) よりも高速にソートすることはまだできません。

于 2010-11-29T23:38:39.960 に答える