c++ - 多くの離散値に対してテストするための好ましい方法は?

Question

次のシナリオがあります。

variable in {12, 4, 999, ... }:

リストには約 100 個の離散値があります。これを C++ に変換するためのパーサーを作成していますが、それを行うために考えられる唯一の方法は、100 個の case ステートメント、または 100 個の if == です。

どちらかが優先されますか、それともこれを行うためのより良い方法はありますか?

明確にする必要がありますが、値は定数の整数です。ありがとう

Answer 1

離散値のいずれかの最大値が十分に小さいstd::vector<bool>場合、そのエントリがリストにあるかどうかに応じて true または false に設定されたフラグが最適である必要があります - 値がほぼ等しい確率で発生すると仮定します。

Answer 2

1 つの方法は、値を順番に並べ、二分探索を使用して値がコレクションに含まれているかどうかを確認することです。

std::lower_bound挿入ポイントを使用して並べ替えられた順序でベクトルに値を入れてstd::binary_searchからメンバーシップをテストするために使用するか、値を に入れてstd::setその機能を無料で取得することができます (std::set::find()メンバーシップ テストに使用)。

どちらのオプションを優先するかについては、パフォーマンスに関するわずかな考慮事項があります。プロファイリングして、自分で決めてください。

2番目のアプローチは、値を次のようなハッシュテーブルに入れることですstd::unordered_set（または、値が静的にわかっている場合は、ある種の静的同等物）。

Answer 3

switch値が定数であると仮定すると、確かにステートメントを使用できます。コンパイラは、バイナリ検索タイプのアプローチまたはテーブル [またはテーブルとバイナリ検索の組み合わせ] を使用して、これをかなり効率的に実行します。if ステートメントの長いリストは、数値を並べ替えてバイナリ検索タイプのアプローチを作成しない限り、それほど効率的ではありません。コンパイラーが数値を決定するための最適なアプローチを整理するため、switch ステートメントの生成ははるかに簡単です。リストにあるものとそうでないもの。

値が定数でない場合、switch ステートメントは明らかに解決策ではありません。実際の範囲によっては、ビットマップが機能する場合がありますが、値の範囲が広い場合、多くのメモリを使用するため、これは適切な解決策ではありません [しかし、これはおそらく最速の方法の 1 つです。単純な>>and演算子を使用して実行できる 2^n の数での除算/モジュロの場合&、その後に 1 回のメモリ読み取りが続きます]。