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

可以考虑字典树

你用的语言是没有 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

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

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

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

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

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

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

抛砖引玉, 不一定说得对

相对于 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)这种快一些.

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

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

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

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

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

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

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

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

@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, 加上数组的直接操作应该是比表这种数据结构快的, 可能能获得一点速度上的甜头.

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

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

@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 就是这个想法，效果有限。