1

次のフィールドを持つドキュメントがあります。

  • フィールド1
  • フィールド2
  • フィールド3
  • フィールド4

次のテーブル構造があります。

field1  |  field2  |  field3  |  field4  || result
--------------------------------------------------
foo                   bar                   MC
foo        test1                            MR
           test2                 test3      OM
foo        test1      bar                   CM

フィールド 1 が foo、フィールド 2 (null 値)、フィールド 3 がバーであるドキュメントが入ってきた場合、結果の MC を選択する必要があります。field1 が foo、field2 が test1、field3 が bar であるドキュメントが入ってきた場合、結果 CM を選択する必要があります。

もちろん、各列をチェックして、各行をループするまで一致する行を開いたままにすることができます。しかし、このテーブル構造は非常に大きくなる可能性があるため、上記の問題を効率的かつ適切な方法で解決する何らかのアルゴリズムを探しています。

何か案は？

4

2 に答える 2

1

@MarkoTopolnikが書いたように、RDBMSはあなたがやりたいことをします。ただし、それでも独自のアルゴリズムを実装する場合は、ツリーを作成するオプションが1つあります。レベル1はfield1、レベル2はfield2、などです。各ブランチはテーブルの1行です。フィールドが2つしかない場合、これは次のようになります。

root----field1.valueA----field2.valueC---result1
    \                \
     \                \--field2.valueD---result2
      \
       \field1.valueB----field2.valueC---result3
                     \
                      \--field2.valueD---result4

このツリーは、各レベルのハッシュテーブルを使用して実装できます。field1まず、値をキーとして、ハッシュテーブルを値として持つハッシュテーブルがあります。これらのハッシュテーブルにはfield2、キーとresult値があります。null値として許可するため、を使用する必要があります。を使用する必要はHashMapありませんHashtable。

于 2012-10-31T10:02:03.393 に答える
0

このような文字列検索の場合、最速のオプションは基数ツリーです。4 つの基数ツリーを作成します。ツリーのリーフは、値が関与するレコードのソートされたリストであるフィールドごとに 1 つです。たとえば、フィールド 1 の場合、Foo を検索すると、{ 1, 2, 4 } は、Foo がフィールド 1 のレコード 1、2、および 4 にあることを示します。結果として、4 つの数値セットが得られ、その交点が答えになります。

交差を取得するには、並べ替えられた順序で維持されるため、線形時間で実行できます。C でこれを行うための単純なソート済み集合交差アルゴリズムを次に示します。

#define int32 unsigned int

// A, B - operands, sorted arrays
// s_a, s_b - sizes of A and B
// C - result buffer
// return size of the result C
size_t intersect_sorted_list(int32 *A, int32 *B, size_t s_a, size_t s_b, int32 *C) {
    size_t i_a = 0, i_b = 0;
    size_t counter = 0;

    while(i_a < s_a && i_b < s_b) {
        if(A[i_a] < B[i_b]) {
            i_a++;
        } else if(B[i_b] < A[i_a]) {
            i_b++;
        } else {
            C[counter++] = A[i_a];
            i_a++; i_b++;
        }
    }
    return counter;
}
于 2012-10-31T17:18:14.027 に答える