使用优先级数组和忽略条件的查询搜索算法

Question

我在公司物流中遇到这个问题：

给定的混合值数组

arr = [
    v1 => a, 
    v2 => b, 
    v3 => c, 
    v4 => d
]

按优先级 ASC 排序（v1 比 v2 更重要，...等）

我需要像这样在 table 中搜索值：

select * from t where 
    ... And
    t.v1 = a And
    t.v2 = b And
    t.v3 = c And
    t.v4 = d

查询中的3个点为固定条件

如果我无法从查询中找到任何值，请执行相同的查询，忽略数组中最不重要的值

select * from t where
    ... And
    t.v1 = a And
    t.v2 = b And
    t.v3 = c

如果未找到值，请重试。执行忽略下一个最不重要值的查询

select * from t where
    ... And
    t.v1 = a And
    t.v2 = b And
    t.v4 = d

查询可以像上次查询一样忽略数组中的所有元素

select * from t where ...

重复直到找到至少1个查询结果或数组中的所有元素都为空并且没有找到结果。 (return 错误)

我使用二进制数进行了我的搜索算法，以找到这样工作的值

binaryValue = (2 ^ arr.lenght) - 1 //(In this case: 2^4-1 = 15)

将二进制 15 转换为 boolean exploded = [1, 1, 1, 1] 数组（二进制中的 15 为 1111）

如果为真，则考虑 booleanArray 的位置 0 展开查询，然后考虑 arr 中的混合值等值

从 15 循环到 0（第 0 次迭代是当布尔数组为 [0,0,0,0] 并忽略所有情况序列将是这样的逻辑：

[a, b, c, d] // [1,1,1,1] = 15 (select * from t where ... and v1=a and v2=b and v3=c and v4=d)
[a, b, c] // [1,1,1,0] = 14 (select * from t where ... and v1=a and v2=b and v3=c)
[a, b, d] // [1,1,0,1] = 13 (select * from t where ... and v1=a and v2=b and v4=d)
...
[] // [0,0,0,0] = 0 (select * from t where ...)

搜索算法工作正常，但我遇到了一个很大的性能问题。

本次搜索的查询次数为arr.length！ (fatorial) 所以当数组长度为 4 时，最坏的情况是执行 24 次查询。如果 arr.length 是 6（我现在在生产代码中处理的长度是多少）最坏的情况是执行 720 个查询，即 unacceptable.

我需要一种方法来改进此搜索。有人可以帮助我吗？

提前致谢。

Answer 1

我使用@RBarryYoung

建议的行的可取性概念提出了解决方案

我没有执行多个查询，而是将所有相关行提取到一个数据表（1 个查询）中，并且我为每一行应用了一个基于合意性的分数。（代码端）

        Dim dicFields As New Dictionary(Of String, String) From { _
            {"v1", a}, _
            {"v2", b}, _
            {"v3", c}, _
            {"v4", d}
        }

        Dim intScore As Integer = dicFields.Keys.Count

        For Each pair As KeyValuePair(Of String, String) In dicFields
            lstRow _
                .Where(Function(p) p.Item(pair.Key) = pair.Value) _
                .ToList() _
                .ForEach(Sub(p) p.Item("__Score") += intScore)

            intScore -= 1
        Next

        return lstRow _
            .OrderByDescending(Function(p) p.Item("__Score")) _
            .FirstOrDefault()

降低了n!的复杂度！只有 1 个查询和 n 个过滤器。系统启动运行顺利。感谢@RBarryYoung

的帮助

使用优先级数组和忽略条件的查询搜索算法

Query Search Algorithm using priority array and ignoring conditions

sql

algorithm

performance

search

logic