1

我有一个包含以下字段的文档:

  • 字段1
  • 字段2
  • 字段3
  • 字段4

我有以下表结构:

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

当一个文档进来,field1 是 foo,field2(空值),field3 是 bar,应该选择结果 MC。当一个文档进来,field1是foo,field2是test1,field3是bar,应该选择结果CM。

当然,您可以检查每一列并让匹配的行保持打开状态,直到您循环每一行。但是,这个表结构可能会变得非常大,我正在寻找一种解决上述问题的算法,以一种高性能和好的方式。

有任何想法吗?

4

2 回答 2

1

正如@MarkoTopolnik 所写,RDBMS 做你想做的事。但是,如果您仍想实现自己的算法,一种选择是创建一棵树:级别 1 是field1,级别 2 是field2,等等。每个分支是表的一行。如果你只有两个字段,这看起来像这样:

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

您可以在每个级别使用哈希表来实现此树。首先,您有一个哈希表,其中field1值作为键,哈希表作为值。这些哈希表具有field2键和result值。由于您允许null作为一个值,因此您必须使用HashMapand not Hashtable

于 2012-10-31T10:02:03.393 回答
0

对于像这样的任何字符串搜索,最快的选择是基数树。创建 4 根基数树,每个字段的叶子是值参与的记录的排序列表。例如,对于字段 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 回答