求一个数组匹配的优化思路

[enenaaa]

有多个由 id 组成的数组，例：

arr = [11, 34, 8, 7, 6, 2]

id 的取值没有限制，也会在 arr 内重复出现。

有一组待匹配的规则，每个规则划分为多个段，每段包含若干 id。

rule1 = [[11, 3, 19], [34, 56], [8], [7, 90, 57], [6, 8], [2]]

rule2 = [[11, 4], [56, 79], [8], [78], [6], [1, 33]]

规则之间，段之间 id 有交叉重叠。

现在要检查 arr 是否匹配某个规则。 如上面的 arr， 只要 arr 里对应位置的 id 在 rule 的段中存在，则该位置匹配。如果 arr 从头到尾匹配，则 arr 匹配该 rule。 上面的 arr 匹配 rule1， 不匹配 rule2。

现有的优化如下：

1、将所有 rule 首段的 id 汇总成表，只有 arr 首个 id 在表内时才尝试匹配。

2、记住每个 rule 的长度，匹配前先比较长度。

3、rule 以首段分组，只要首段不匹配， 那组内其他 rule 不必再尝试。这个思路再延伸，可以把 rule 做成树状结构，但与一般的树查找不同，感觉效率提升有限。

还有其他更好的优化思路吗。。

[qianlv7]

可以考虑字典树

[imn1]

你用的语言是没有 in/not in 这种判断，还是你要做内存优化？ C/C++？

python 写这个就一行

In [1]: arr = [11, 34, 8, 7, 6, 2]

In [2]: rule1 = [[11, 3, 19], [34, 56], [8], [7, 90, 57], [6, 8], [2]]

In [3]: rule2 = [[11, 4], [56, 79], [8], [78], [6], [1, 33]]

In [11]: all(arr[x] in rule1[x] for x in range(len(arr)))
Out[11]: True

In [12]: all(arr[x] in rule2[x] for x in range(len(arr)))
Out[12]: False

[enenaaa]

@qianlv7 因为 rule 的段内有重叠，不是一般树的查找。
@imn1 用的就是 python， 运行太慢了。 上了 cython 还是慢。

[momocraft]

如果每个 rule 会被匹配多次: 可以考虑把一个 rule 段中的所有 id hash，然后 bitwise or 成一个 id，用这个 id 快速排除不符合的 arr。(即: 只有一层的 bloom filter)

(你只讲了匹配规则，不知道有多少 arr 多少 rule，这边能不能再具体点)

[momocraft]

原来已经是 python 了.. 那可以先把 rule 的每段换成 Set

[enenaaa]

@momocraft arr 数组 10 万左右，rule 现在近 2000 条。你说的方法，将 rule 段内拼合成唯一表， 我也尝试过，只有首段有些效果，后续段提升不明显。原因可能是 10 万条 arr 中，最终匹配的只有 10%左右， 大部分在 rule 首段就失配了。

[enenaaa]

@momocraft 忘了说了，段内本身就是 set 存储的。

[vegito2002]

抛砖引玉, 不一定说得对

相对于 arr 的数量, rule 的数量比较少, 可以预处理一下, 每个 rule 做成一个表, key 是 entry, value 是 list of row_number; 比如你的 rule1 里面应该有一个{8 = {2, 4}} (row_number 是 0-based)的. 这个处理对每一个 rule 只要 O(size_of_rule)就做完了.

你现有的优化, 保留第二个优化, 首先匹配长度.
长度匹配成功以后:
对每一个 arr, 直接对每一个 index, 取出 entry, 然后查这个 rule 的表. 比如 index 为 2 的是 8, 在 rule1 的表里面 get 8, 找到一个{2,4}.contains(2)是 TRUE, 那么这个 index 就过了, 下一个 index 继续. 如果表的查找可以认为是 O(1), 最后每一个 arr 需要的时间也就是 O(size_of_arr). 当然查表的复杂度要根据语言而看了, JAVA 的查表是 O(1), C++的好像就没有这么快了. Python 没有实际做过项目, 所以不知道实现的复杂度到底怎么样; 但是感觉直接用 set.contains(8)这种快一些.

[vegito2002]

最后一句打错了: 感觉**比**直接用 set.contains 快一些.

[imn1]

python，我觉得 100k/2k 这个数量级，用 pandas/numpy 是很快的
你是需要毫秒级的优化么？

另外不清楚 append 的意思，rule 还有一个从 id 组编号提取 id 的过程？如果是这样，我反而觉得瓶颈在这里

[enenaaa]

@vegito2002 假设查表消耗为常量。arr 长度为 n， 那么直接检索查表次数为 n 次。
而你的办法， 一次比较需要两次查表，查表次数为 2n 次哦。

[enenaaa]

@imn1 在我的机器上，一次处理跑下来要 15 秒左右。整个数据库迭代一次耗时近 10 天。大头就在这个匹配上了。
我对 numpy 不熟，因为还有些通配符的处理，不晓得是否适用。

append 里主要想说 rule 段内 id 是以 set 方式存放的， 在预处理阶段已经将 id 组编号转换为 id set 表。
但如#6 所说， 段内 id 存成一个大 set， 相对于多个小 set 只有在首段有较为明显的效率提升。

为简化讨论， 这里就当一个段是一个 set 好了。

[h4x3rotab]

rule 比较多的话，这和正则表达式匹配是同一个问题，只不过你要知道是哪个规则匹配到了。至少用 DFA 可以实现 O(n)匹配。

[vegito2002]

@enenaaa 想了一下, 确实就算把 list of row_number 优化成一个表, 最后的复杂度顶多也是相等, 未必能做到加速;

不知道我对你的做法有没有理解对: 你每一个 rule 的每一个 row 做成一个 Map, 然后 arr 的每一个位置来了直接在这个 Map 里面查表是吗?

反正我的想法还是得预处理 rule. 如果用 Map, 那么最坏情况复杂度可能会比较高(虽然平均大部分操作是 O(1)), 所以要么可以这样, 建立一个二维数组, 一个坐标是 row_number(也就是 arr 里面每个位置的 index), 一个坐标是 id value. 二维数组的每个 entry 代表是否存在(可以用 boolean 或者 0/1).

这个也就是用 array 的直接存取来替代 Map 的查表操作, 不知道最后能不能达到加速. 这样应该可以保证你一个 arr 的复杂度肯定只可能是 N, 加上数组的直接操作应该是比表这种数据结构快的, 可能能获得一点速度上的甜头.

[enenaaa]

@h4x3rotab 先前我想的是以段为节点构建字典树或 DFA，这样因为段内 id 有重叠，不满足查找性质。
不过如果用 id 作为节点， 可能是个好主意。

[ccpp132]

这不就是正则表达式的功能嘛，做个自动机咯

[enenaaa]

@h4x3rotab
@ccpp132
以 id 为节点构建字典树或 dfa 有个比较大的困难。由于 rule 每段的 id 数较多，节点数很快爆炸。例如一个 10 段， 每段 100 个 id 的 rule， 按正常做法节点数是 100^10。

如果改为共用节点， 即 100+100+100。。。的方式， 由于 id 重叠，又会在多个 rule 之间造成混乱。

例如下面 2 个 rule 构造树：

rule1 = [[1, 3], [2]]

rule2 = [[1, 6], [2], [4]]

rule1 和 rule2 共用了 1，2 节点。但是 3 和 6 也连到 2 上，2 又连到 4 上。 这样 4 节点没法判断到底 rule1 还是 rule2。

现在看来， 可能先得划分好 rule 的数据， 才能进一步处理。



@vegito2002 #4 #6 就是这个想法，效果有限。