定数セットのテストが含まれています

code-generation language-agnostic predicate set
定数セットのテストが含まれています

問題の声明:

前もって知られている整数の集合が与えられると、その集合の中に単一の整数があるかどうかをテストするためのコードを*生成*します。 テスト関数の定義域は、連続した範囲の整数です。

” ” ‘

テストされる範囲やセットについては、特に何も知られていません。 範囲は小さくても大きくても構いません(ただし、解決策は、大きくても上限が高いほど問題を排除できます)。 許容範囲内の値のほんのわずかがセット内にあるか、それらの大部分があるか、またはその間にあるものである可能性があります。 この集合は、一様に分布していてもクラスタ化されていてもよい。 含まれている/含まれていない値のみの大きなセクションがあるか、またはほとんどの帯で各タイプの値の少なくともいくつかがあるかもしれません。 (ソートアルゴリズムを分析するときにソートされる項目について行われた仮定のようなもの)

目的は、テストを実行するための効果的なコードを生成するための手順です。

頭に浮かぶ部分的な解決策が含まれています

  • 完全なハッシュ関数(大規模な集合には費用がかかります)

  • 範囲テスト:
    foreach(b in range)if(b.l ⇐ v && v ⇐ b.h)return true;

  • ツリー/インデックス(場合によっては他のものよりもコストがかかります)

  • テーブル検索(大規模なセットには費用がかかる)

  • これらのいずれかの逆(kodos to
    Jason S

理想的な解決策は、どのオプションが最良であるかを選択するか、うまくいかない場合は、ツリーを使用して全範囲をセクションに分割してから、それらに適したサブセクションの他のオプションに切り替えることができます。

役立つトピックは次のとおりです。

” ” ‘

注:これは宿題ではありません。 それが博士課程以下のレベルで宿題として発行された場合、教授はNerf銃で撃たれるべきです(もしそれが得られないならば、問題を再読しなさい、それは非常に些細ではありません)

注:これは、数日のうちに私に発生した問題であり、私はそれについて何度も戸惑い続けています。 これを直接使用することはありませんが、攻撃するのはクールな問題だと思いました。 私がコードを生成したいのは、生成されたコードは一般的なコードより遅くならず(必要なら同じこともあり得ます)、場合によってはもっと速くなるかもしれないからです。

私の考えを明確にするために、私はこの質問をできるだけ多く投稿しています。 もし私がそれらをテンプレートメタプログラムとして実装することを計画している合理的またはクールな解決策を思いつくことができるならば(生成されたコードのための他の理由)

この問題はごく一般的なものだと言う人もいます。 そこが肝心だ。 私は非常に一般的なドメインで動作するシステムを生成したいと考えています。ある範囲の整数のセットです。

  2  2


ベストアンサー

https://stackoverflow.com/questions/405433/[辞書/スペルチェックに関する以前の質問]には、 https://stackoverflow.com/questions/405433/[Bloom filters]と記載された多数の回答がありました。多分それは役立つだろう。

私は大規模なセットのテストは何をしても高価になるだろうと思います。

1


ちょっと、これが本当の質問であるとしましょう。

  • ベースセットまたは入力セットのサイズに制限はありません

これは「問題」を現実的ではなく非特定化され、そして解決不可能なものにします。

誰かが解決策を提案したい場合は、ここにいくつかのユニットテストケースがあります:

  • 単体テスト1:基本セットは、ランダムに削除された100,000,000,000の値を除いて、-1,000,000,000,000と1,000,000,000,000の間のすべての整数です。入力セットは、同じ範囲内の100,000,000,000のランダムに生成された整数です。

  • 単体テスト2:基本集合はフィボナッチ数列入力集合は0Tの範囲でランダムに生成された1Tの整数

1


http://www.boost.org/doc/libs/1_37_0/libs/dynamic_bitset/dynamic_bitset.html[boost::dynamic_bitset]もありますが、時間の経過や元の数の分布に対する空間の変化については不明です。 。 (例えば。 ビットが8/16/32/64のチャンクに格納されている場合、スパースビットセットは非効率的です。

または this(圧縮ビットセット)またはhttp://bmagic.sourceforge.net/memsave.html[this(ビットベクトル)]のWebページ( 「ラージスパースビットセット」および「圧縮ビットセット」)

1


タイトルとURLをコピーしました