問題文:
事前にわかっている整数のセットが与えられた場合、そのセットに単一の整数が含まれているかどうかをテストするコードを生成します。テスト関数の定義域は、連続した範囲内の整数です。
テスト対象の範囲やセットについては、特に何もわかっていません。範囲は小さくても大きくてもかまいません (ただし、ソリューションは大きすぎる問題を拒否できますが、上限が高い方が優れています)。許容範囲内の値のほとんどがセットに含まれていないか、ほとんどの値が含まれているか、またはその中間にある可能性があります。セットは、均一に分散されているか、クラスター化されている場合があります。含まれる/含まれない値のみの大きなセクションがある場合もあれば、ほとんどのスワスに各タイプの値が少なくともいくつかある場合もあります。（並べ替えアルゴリズムを分析するときに並べ替えられる項目について行われた仮定のようなもの）
目的は、テストを実行するための効果的なコードを生成する手順です。
頭に浮かぶ部分的な解決策には、
- 完全ハッシュ関数 (大規模なセットではコストがかかる)
- 範囲テスト:
foreach(b in ranges) if(b.l <= v && v <= b.h) return true; - ツリー/インデックス (場合によっては他のものよりもコストがかかります)
- テーブル ルックアップ (大規模なセットではコストがかかる)
- これらのいずれかの逆 (kodos to Jason S )
理想的な解決策は、最適なオプションを選択するか、どれもうまくいかない場合は、ツリーを使用して全範囲をセクションに分割し、サブセクションの他のオプションに適したものに切り替えることができるようです。
役に立つかもしれないトピックは次のとおりです。
注: これは宿題ではありません。それが博士レベル以下の宿題として出された場合、教授はNerfガンで撃たれるべきです（それがわからない場合は、問題を読み直してください。それは非常に重要です）
注: これは数日おきに発生する問題で、ときどき頭を悩ませてきました。これを直接使用することはありませんが、攻撃するのはクールな問題だと思いました。私がコードを生成したい理由は、生成されたコードが一般的なコードよりも遅くなく (必要に応じて同じこともできます)、場合によっては高速になる可能性があるためです。
私の考えを明確にするために、この質問を投稿しています。合理的またはクールな解決策を思い付くことができれば、それらをテンプレート メタ プログラムとして実装する予定です (コードを生成するもう 1 つの理由)。
一部の人々は、問題が非常に一般的であると指摘しています。そこが肝心だ。私は非常に一般的なドメインで動作するシステムを生成したいと考えています: ある範囲の整数のセットです。