私は基本的に何百万というテストを実行しているソフトウェアを最適化しようとしています。これらのテストは、いくつかの繰り返しができるような方法で生成されます。もちろん、私はそれを効率的に避けることができれば、すでに走っているテストを実行する時間を費やしたくありません。ブルームフィルタの向かい？
私はBloomフィルタを使って既に実行されたテストを保存することを考えています。しかし、Bloomフィルタは私にとっては安全でない側でエラーを出します。それは偽陽性をもたらす。つまり、私は私が持っていないテストを実行したことを報告するかもしれません。これは私が取り組んでいるシナリオでは受け入れられるかもしれませんが、Bloomフィルターと同等のものがあるのかどうか疑問に思っていましたが、反対側に間違っています。
私は幸運なことなしに文献を読み飛ばしました。
いいえ、それについて考えると、あまり役に立ちません。あなたのケースでは、いつも「偽陰性」がある場合、常に実行する必要のあるテストが存在するため、テスト実行がいつでも停止することは確かではありません。
ハッシュを使用します。
返信いただきありがとうございます。 固定時間が経過してもいつでも停止することができるので、まだ便利だと思います。実際、私はテストを永遠に続けていくことができます。しかし、このようなデータ構造は、ほとんどのテストが実際に新しいものになるのを確実にするのに役立ちます。 –
を実行したテストを実行することはできますか？これはフィルタの動作を逆にするはずです。
Bloomフィルタから要素を取り出すことは不可能なので、これを行うことはできません。 – RarrRarrRarr
カウントブルームフィルターは、 –
またはCuckooフィルターで動作します。https://www.cs.cmu.edu/~dga/papers/cuckoo-conext2014.pdf https://bdupras.github.io/filter-tutorial/ –
LRUCacheはどうですか？
すみません、私はあまり助けにはなりません - 私は可能ではないと思います。テストの実行を順序付けることができない場合は、パック形式（1バイトあたり8つのテスト）を使用するか、結果をメモリに格納するための優れた疎な配列ライブラリを使用してください。
解決策の一部を除外していると思います。偽陽性を完全に避けるためには、まだ実行しているものを追跡しなければならず、テストを決定するためのショートカットとして本質的にブルームフィルタを使用します。あなたがテストの数を事前に知っているので、いくつかのよく知られている公式を使用して許容可能なエラーレートを提供するようにフィルタのサイズを設定できます。偽陽性を返す確率が1％の場合は〜9.5ビット/エントリが必要なので、100万エントリの場合は1.2メガバイトで十分です。受け入れ可能なエラーレートを0.1％に減らすと、1.8 MBにしか増加しません。
ウィキペディアの記事Bloom Filtersは、数学の興味深い概要と大きな分析を提供します。
はい、ロッシーハッシュテーブルまたはLRUCacheは、偽陰性のみを返す高速O（1）ルックアップを持つデータ構造です。「テストXを実行しましたか？」と尋ねると、はい、あなたは間違いなく "、または"私は覚えていません "。このタスクを達成する正確なデータ構造がDirect-mapped cacheであり、そして一般のCPUで使用される
setup_test_table():
create test_table(some large number of entries)
clear each entry(test_table, NEVER)
return test_table
has_test_been_run_before(new_test_details, test_table):
index = hash(test_details , test_table.length)
old_details = test_table[index].detail
// unconditionally overwrite old details with new details, LRU fashion.
// perhaps some other collision resolution technique might be better.
test_table[index].details = new_test_details
if (old_details === test_details) return YES
else if (old_details === NEVER) return NEVER
else return PERHAPS
main()
test_table = setup_test_table();
loop
test_details = generate_random_test()
status = has_test_been_run_before(test_details, test_table)
case status of
YES: do nothing;
NEVER: run test (test_details);
PERHAPS: if(rand()&1) run test (test_details);
next loop
end.
MRU、LFU、ARCなどのメモリモデルとエビクション戦略を組み合わせた回答は、この質問に対する有効な回答です。 –
離散的なメンバーシップを持つロッシーセットは、確率的メンバーシップを持つセットの "反対"と考えられるデータ構造のファミリであると言えるかもしれませんが、LRUヒューリスティックは完全に別個の関心事であり、私が一般化しようとするなら、私自身の答えもそうです（それは連合性1と仮定します）。 'set'と' item'が与えられたときに 'item'を含む新しい' set'が生成されるように定義された変換 'f（set、item） - > set"が存在するとすれば十分です。カーディナリティの制約のもとでメンバとして使用されます。 'f'の選択は無関係です –
：
は極めて粗擬似コードを許します。
function set_member(set, item)
set[hash(item) % set.length] = item
function is_member(set, item)
return set[hash(item) % set.length] == item
また、何百万というオーダーで、単純なビット配列を使うことができます。 :) –
期待するデータ構造が存在しません。そのようなデータ構造は、多対1のマッピング、すなわち制限された状態のセットでなければならないからです。同じ内部状態にマッピングする少なくとも2つの異なる入力がなければなりません。だから、あなたはどちらか（またはそれ以上）がセットに入っているかどうかを知ることはできません。
EDITこのステートメントは、メモリ効率の良いデータ構造を探している場合にのみtrueです。メモリが無制限の場合は、すべてのメンバーアイテムを格納することで、常に100％正確な結果を得るためのデータ構造を得ることができます。
これは事実上間違っています –
@MartinKällman上記で提案されたすべてのソリューションは元のアイテム（あなたのケースではset_member）の保存を必要とするため、メモリ効率が必須でない場合は正しいです。メモリ制限が満たされると、偽陰性と偽陽性の両方の結果が得られます。あまりにも多くの入力のために偽陽性率がかなり高い場合でも、Bloom Filterは偽陰性の結果を出すことはありません。 – roam
はい、これは任意の連想配列の要件です –
http://cstheory.stackexchange.com/questions/6596/a-probabilistic-set-with-no-false-positives –
完全を期すため、これは興味深いことがあります。https://github.com/ jmhodges/oppos_of_a_bloom_filter – Dave
「ブルームフィルタの反対」という面白い名前のものが1つあります。コード：https://github.com/jmhodges/opposite_of_a_bloom_filter ブログ：http://www.somethingsimilar.com/2012/05/21/the-opposite-of-a-bloom-filter/ – ib84