7

計算済みの値を格納するには、スペース効率の良い確率的データ構造が必要です。私にとって計算は安価ですが、スペースはそうではありません。したがって、このデータ構造が偽陰性を返した場合、時々いくつかの作業をやり直すことは問題ありませんが、偽陽性は受け入れられません。だから私が探しているのは、ブルームフィルターの反対のようなものです。

4

1 に答える 1

8

偽陰性の場合は、非可逆ハッシュ テーブルまたは LRUCache を使用できます。これは、偽陰性のみを与える高速 O(1) ルックアップを備えたデータ構造です。「テストXを実行したことがありますか」と尋ねると、「はい、間違いなく実行しました」または「覚えていません」と答えます。

擬似コード:

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.

同様に、誤検知のブルーム フィルター

于 2012-11-07T09:01:06.477 に答える