6

これまで、配列をベクトルに格納し、ベクトルをループして一致する要素を見つけ、インデックスを返してきました。

C ++でこれを行うより速い方法はありますか？配列を格納するために使用するSTL構造は、実際には重要ではありません（ベクトルである必要はありません）。私の配列も一意であり（繰り返し要素がない）、順序付けられています（たとえば、将来の日付のリスト）。

4

2 に答える 2

7

要素がソートされているため、バイナリ検索を使用して一致する要素を見つけることができます。C ++標準ライブラリには、std::lower_boundこの目的に使用できるアルゴリズムがあります。明確さと単純さのために、独自のバイナリ検索アルゴリズムでラップすることをお勧めします。

/// Performs a binary search for an element
///
/// The range `[first, last)` must be ordered via `comparer`.  If `value` is
/// found in the range, an iterator to the first element comparing equal to
/// `value` will be returned; if `value` is not found in the range, `last` is
/// returned.
template <typename RandomAccessIterator, typename Value, typename Comparer>
auto binary_search(RandomAccessIterator const  first,
                   RandomAccessIterator const  last,
                   Value                const& value,
                   Comparer                    comparer) -> RandomAccessIterator
{
    RandomAccessIterator it(std::lower_bound(first, last, value, comparer));
    if (it == last || comparer(*it, value) || comparer(value, *it))
        return last;

    return it;
}

（C ++標準ライブラリには。がありますが、範囲に要素が含まれている場合は： std::binary_searchが返されます。それ以外の場合は、要素へのイテレータが必要な場合は役に立ちません。）booltruefalse

要素へのイテレータを取得したら、std::distanceアルゴリズムを使用して範囲内の要素のインデックスを計算できます。

これらのアルゴリズムは両方ともstd::vector、通常のアレイを含むすべてのランダムアクセスシーケンスで同等に機能します。

于 2012-07-07T22:03:22.787 に答える
7

値をインデックスに関連付けてインデックスをすばやく見つけたい場合は、std::mapまたはを使用できますstd::unordered_map。データに対して実行する他の操作に応じて、これらを他のデータ構造（astd::listまたはなど）と組み合わせることもできます。std::vector

たとえば、ベクトルを作成するときに、ルックアップテーブルも作成します。

vector<int> test(test_size);
unordered_map<int, size_t> lookup;
int value = 0;
for(size_t index = 0; index < test_size; ++index)
{
    test[index] = value;
    lookup[value] = index;
    value += rand()%100+1;
}

次に、インデックスを検索するには、次のようにします。

size_t index = lookup[find_value];

ハッシュテーブルベースのデータ構造（unordered_mapなど）の使用は、かなり古典的な空間と時間のトレードオフであり、多くのルックアップを実行する必要がある場合に、この種の「逆」ルックアップ操作のバイナリ検索を実行するよりも優れています。もう1つの利点は、ベクトルがソートされていない場合にも機能することです。

楽しみのために:-)私はVS2012RCで、Jamesのバイナリ検索コードを線形検索と比較し、ルックアップにunordered_mapを使用して、すべてベクトルで簡単なベンチマークを実行しました。 さまざまな検索インデックスメソッドのパフォーマンス

〜50000要素unordered_setが期待されるO（log N）動作を示すバイナリ検索を大幅に上回っていますが、やや意外な結果として、unordered_mapは10000要素を超えるとO（1）動作を失います。おそらくハッシュの衝突が原因です。 、おそらく実装の問題。

編集：順序付けされていないマップのmax_load_factor（）は1であるため、衝突は発生しないはずです。非常に大きなベクトルのバイナリ検索とハッシュテーブルのパフォーマンスの違いは、キャッシュに関連しているように見え、ベンチマークのルックアップパターンによって異なります。

std::mapとstd::unordered_mapのどちらかを選択すると、順序付きマップと順序なしマップの違いがわかります。

于 2012-07-07T22:10:36.163 に答える