これまで、配列をベクトルに格納し、ベクトルをループして一致する要素を見つけ、インデックスを返してきました。
C ++でこれを行うより速い方法はありますか?配列を格納するために使用するSTL構造は、実際には重要ではありません(ベクトルである必要はありません)。私の配列も一意であり(繰り返し要素がない)、順序付けられています(たとえば、将来の日付のリスト)。
要素がソートされているため、バイナリ検索を使用して一致する要素を見つけることができます。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
が返されます。それ以外の場合は、要素へのイテレータが必要な場合は役に立ちません。)bool
true
false
要素へのイテレータを取得したら、std::distance
アルゴリズムを使用して範囲内の要素のインデックスを計算できます。
これらのアルゴリズムは両方ともstd::vector
、通常のアレイを含むすべてのランダムアクセスシーケンスで同等に機能します。
値をインデックスに関連付けてインデックスをすばやく見つけたい場合は、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のどちらかを選択すると、順序付きマップと順序なしマップの違いがわかります。