这是发布在百姓网官方blog上的一道公开笔试题。转发到这里,我知道我的blog读者有很多优秀的程序员,还有我敬仰的一些技术大牛,热切希望能够得到你的来信,并且有机会一起解决一个又一个这样有趣的技术挑战。也欢迎转载,多谢!
=====================================
百姓网需要最聪明,最有潜力的技术牛人来帮助我们给世界惊奇。为了让我们互相找到的过程变得更加直接了当,我这里有一个公开的笔试题目。这是我们日常的工作中遇到的一个典型问题。如果你有答案,请直接寄到 geeks @ baixing.com而不需要使用 shhr @ baixing.com。
题目
请写一个算法,判断一个查询表达式是不是另外一个查询表达式的子集。
稍微加一点解释
就拿SQL语句为例,如果查询A是
age > 21
查询B是
age > 20
我们知道,A所代表的集合是B所代表的集合的子集。凡是满足A的条件的记录,也一定满足B的条件。我需要一个算法,在给出任意两个表达式以后,判断一个是不是另外一个的子集。
if($queryA->isSubSet($queryB)) { echo(“A is subset of B”);}
为了简单起见,只需要实现最简单的AND, OR逻辑操作,大于,等于,小于三种比较操作就好。最好用PHP,其他语言,比如Java也没问题。
这有什么用呢?
这是个我们不到10人的技术团队日常典型需要解决的问题。给个例子:百姓网为了应付更大的搜索数据量,把搜索分布在多个城市的多台服务器上。系统管理员可以根据数据的使用频度等规律,配置几个不同的数据库(MySQL的,和Solr的)。这样,当有一个新的广告出来后,子集算法根据搜索库的配置查询就可以决定,它更新到哪一个或多个库里面。
查询的时候,如果确认给定的查询条件是以前配置的一个库的子集,就可以只从那个库里查询了。这可以让我们轻松地配置几十个搜索库,而不用改一行代码。
热切期待优秀的你和我们联系。重复一遍:邮件请发到:geeks @ baixing.com
这里是百姓网的职位。
说明用的例题可能有误哦。age=22, height=159 这个样本满足A但不满足B,所以A不是B的子集。把例子中 AND 改成 OR 的话就可以了。
@gx,对的。一个笔误,原来的A比较复杂,改了改,改错了。该打。看了你的blog制造回忆,很有意思,悠闲、唯美。
1、$queryA和$queryB是字符串吗?还是已经处理好的逻辑树?
2、比较操作的右端都是常量,还是有可能是变量?例如是否需要考虑 “A>B AND B>C”->isSubSet(“A>C”) 的情形?
感觉很难找到一个通用的方法,具体问题具体分析,一共又多少种查询语句列一下,通常只有少数语句会占用很大量的资源。不追求完美,not that perfect but doable and feasible
@qmigh: 为了简化起见,$queryA 和 $queryB 可以是一个Query构造器 (QueryBuilder),大家可以自己写,比从字符串分析简单一点。我们的Builder是这样子的:
$queryA = new AndQuery(
new RangeQuery(‘age’, 20),
new NotQuery(‘status’, true)
);
大家可以自己写一个自己顺手的builder。
比较操作只要考虑左边是field名,右边是常量就好了,这是最简单,也是到现在需要用得到的部分。
@tyler durden,我同意这个“感觉起来很难”。也同意“not that perfect but doable and feasible”,我们最需要的就是就是实用主义的解决方案,但无论什么“主义”,首先要有一个解决方案。
谢谢大家参与,有什么问题可以问我。
谢谢你的回复,如果能分享一下更多的具体场景,也许大家可以帮忙。如果只是单纯的判断mysql查询条件的判断,个人感觉范围大一些,也许不能最好的得到解决。提几点,mysql proxy似乎有SQL parser的功能,用lua可以操作。另外,有一个用二进制位求所有子集的方法,不知是否能有启发
路过的 :) SQL语句本来就是用来处理 Set和Bag所优化出来的语言 是不是更应该和把所有条件放到表内去搜比用算法更合理?
路过,提供一种纯理论的思路:
【1】将原问题[判断1个复杂范围是否是另1个复杂范围的子集]降解为[判断1个数是否为1个简单范围的子集]
【2】1个简单范围可以降解为2个数(或1个,当等于时);比如age>30,即取 31,999999(根据场景定义)
【3】 AND/OR的处理就比较简单了,不说了
不知道会不会有bug,具体实现就不说了,大家都懂得~
@tyler durden,具体的场景在上文里面简单描述了。再详细一点,就是说我们可能有非常多为不同的场景优化的数据库,切割的维度可能都不一样。比如:
– 为实时优化的实时库(小但是快),是按照时间维度切的;
– 为了地域优化的地域库(比如上海库),是按照地域维度切的
– 为了查询优化的active广告库,是按照状态维度切的
– 为了最全的数据优化的大数据库(全却慢),可能把5年的数据都放进去
还有合并了各种维度为每种特殊情况优化的库。手工判断一个广告进哪个库,从哪个库查已经越来越复杂,会因为一个小调整而产生大调整。所有这些问题,在数据量不大或者对速度要求不高的情况下都是没有的。我要解决的是大数据量的分布式查询问题。
我们实际的应用中对于基于Solr的搜索库的切分的需求大于对MySQL的切分。MySQL其实内部的Partition等方案已经大概的解决了类似的问题。
而且这个算法是一个比较通用的算法,MySQL和SQL Server里的Query Optimizer在优化Execution Plan的时候就是类似的算法,只是懒得去看源代码,而是用一个很简单的算法来完成。对于SQL Parser和lua,愿闻其详。
@AvergerMoJo,抱歉,可否更详细一点?多谢
谢谢你的回复。根据你提供的场景,我想说一点针对这个场景的其他想法,不知可否?从我的理解来看,solr搜索和MySQL都存在数据量过大,或者数据热点问题,而且搜索方面的瓶颈可能更为突出一些。
第一种方法是加缓存,memcache或者redis都可,而且最好是主动缓存(只有数据更新的时候才去更新缓存)。被动缓存比较常见,而且实现也比较简单,尚不赘述,只是被动缓存会对网站的实时性造成影响。主动缓存有几个实施的难点,针对MySQL,通过日志分析得到影响资源最大的几个SQL语句类型,对这几种语句进行优化,一个可能的办法是利用mysql proxy对这些语句进行一些调整,使得一些记录通过ID调用memcache得缓存;并在web前端得程序种加入对缓存得更新处理(如果对mysql log进行分析得到更新也可,类似与log同步机制,不用修改前端程序,只是实施代价稍大);针对solr搜索,同样是先通过日志分析热点,对于这样得搜索加入缓存,对于搜索结果得主动更新缓存,更为麻烦一些,可能需要对一条信息所有可能得搜索条件求子集,然后批量进行更新。
个人感觉缓存是可以用并且应该用好,只是需要很精心得设计。(不知到你们已经在用?)
另一个思路是采用分布式的处理方式。这个思路可以从Cassandra展开,C*的bigtable的数据模型似乎更适合baixing.com的半结构化信息(结构很多,对应到MySQL可能要分很多表,或者采用entity-attribute-value模式存储),同时C*的分布式处理模型能减少mysql partition/sharding带来的维护成本。分布式的搜索可以参考一下lucandra,一个结合了lucene/solr和Cassandra 的东西(可能还不适合用于生产环境,但是个不错的思路)。分布式的东西很多,个人感觉C*相对来说更简单实用一些
以上只是一些浅见,而且很多地方也非这几个字能描述的清楚。各位看了,见笑见谅:)
随手写了个实现,因为命题规定简单的逻辑操作,所以逆波兰计算最简表达式之后展开成为若干个与子式的或操作,因为是&&操作,所以对每个token的区间操作可以做简单的删减,再将各个&&子式的离散区间进行合并。最后再遍历A查询的各个token的区间是否都落在B查询的该token的区间上。考虑到查询语句的长度,子式应该不多,所以离散化检查区间应该更具效率,但是编程比较烦,用线段树实现比较简单。实现的很丑陋…..
貌似实现的不对….faint
是说要支持无限括号么?
写了一下午,发现写错了
如果我没理解错的话,这题狂难
不是抢答吧?
建议有答对的的就公布一下,超过三个我就放弃挣扎了……
@tyler durden,你说的应用系统其他层的解决方案,比如memcached,的确都在使用,不过我们非常开心的看到,随着数据量的增大,原有的解决方案还是捉襟见肘(多兴奋的一件事情呀!技术人员最幸福的就是有足够挑战的问题需要解决)。比如说,很多的方案在跨服务器或者cluster没有问题,跨数据中心的时候就有问题。而且考虑到系统的延续性,也不能今天MySQL,明天Cassandra这样的折腾,所以才有了这道题目。这是我们在去年面临的一个实际问题。谢谢你的建议。
@mikster,想法相当不错,只是以我愚见,逆波兰表达式在这个帮不了忙,但是想法和我是一致的。
@Platinum,别放弃,不是抢答,长期有效。在百姓网,经常遇到的技术问题都是没有现成答案的。虽然实际使用中大概支持个五、六级括号就好了,但是这道题是应该支持无限括号和所有And,OR,Not及括号组成的表达式的 – 都是一个算法。这道题难倒也不是特别难,就是比较耗费体力。选这个题,倒也不是因为难,而是的确这就是一个典型的应用。
现在已经收到大家的邮件了。非常感谢大家的热情。如果在寄过来算法的时候一并有简历就最好了。
实际上是高维空间里的覆盖问题,离散化后逐个检查是朴素做法,复杂度取决于每次排除后的分裂速度。逆波兰是将空间立方体化的手段而已。如果高维线段树空间和速度都不好,所以朴素做法还是最好的,但是看起来还是不能满足要求
我比较怀疑这个问题的下限。
如果是处理QueryBuilder的话,那简单很多哦。其实这里面最繁琐的一步就是解析字符串格式的Query。其实就算是字符串形式的,如果每个AND和OR都有括号括起来的话,处理也不复杂。
我不认为tyler durden的“很难找到一个通用的方法”的想法是对的。这应该有通用解决办法的。
初步思路就是把queryA和queryB分别规整为一系列的原子条件的AND集合的OR集合。例如,将
(A20) AND (B20)
变换成为:
(A20) OR (A>20 AND B20 AND B>20)
为方便叙述,我们将A20等称为“原子条件”,将原子条件的AND集合,称为“条件集”。将条件集的OR集合,称为“查询”。
要判断查询A是否为查询B的子集,需要将A的所有条件集都为B的子集。
要判断一个条件集A’是否为查询B的子集,只需要A’为B的任意一个条件集的子集。
要判断一个条件集A’是否为条件集B’的子集,需要A’的所有原子条件A”:或者在B’中没有相应的条目,或者B’中的相应条目的条件已经涵盖了A”,我相信这一步已经很容易做了。
————————————-
写完了之后,发现已经有mikster的留言把上面这个过程用很数学的术语给描述过了。苍天作证,我是写完之后才看到那个留言的,绝对没有抄袭。 :-D
贴出来怎么变这样了。
中间的那一段是:
(A20) AND (B20)
变换成为:
(A20) OR (A>20 AND B20 AND B>20)
呃~~
(A<10 OR A>20) AND (B<10 OR B>20)
变换成为:
(A<10 AND B<10) OR (A<10 AND B>20) OR (A>20 AND B<10) OR (A>20 AND B>20)
这样总该行了吧
我写了一个比较简单的,处理QueryBuilder的方法,发到邮箱里了!很惭愧限制条件比较多!
to gmigh,我写了把查询字符串 parse 成语法树的代码,但对于复合查询如何判断子集关系,从你的回复里得到启发了。thx。
早上好。
@gmigh,相当清晰的算法。
@Raidenxu,抱歉,还需要考虑一下,并不是那么简单。再试试?
欢迎大家继续寄写好的代码(PHP或者Java的)到geeks@baixing.com来。如果能注明希望在百姓网工作还是仅仅是有兴趣切磋一下会最好(否则我们有点迷茫,不知道接下来怎么处理)。最好同时有简历。谢谢。
基本上如qmigh所说的,可以解决and,or的逻辑运算问题,可以称之为规范化。
正确流程我认为是
1.预处理,主要是去除所有的not,如not(a > 3 or b > 5)改为a b and b > c 与 a > c ,后者是前者的子集
晕,怎么评论内容会被截断,而且是中间的丢失了?
是我的问题。MTCommentBody忘了encode_html,以前没有觉得,现在大于号小于号满天飞的代码就出问题了。现在应该好了。
发了个cpp的code到geek邮箱,蛮有兴趣知道你们的solution
@mikster,收到。
嗯,写了一份自己的答案,自己测试了一些情况,发现没有问题,写了个具体点的方案描述文字,已连代码给博主发去。
解题关键字:语法树,与或树
以下是用来测试的一些用例
t2 = Query(‘age > 18 and weight 18 or weight 40’) # 中年人
t1 = Query(‘age > 18’) # 成年人
t0 = Query(‘(age 30’)
t1 = Query(‘age < 7’)
t2 = Query(‘age < 18’)
翻了下离散数学,觉得可以这样做。
设有两集合
I. A > 30 | A >5 & B > 20
II. A > 20 & B =30
做一下alias, 保证
Q = A > 30
W = A > 5
R = B > 20
T = A > 20
Y = B=30
I. = Q | W & R
II. = T & Y
如果II是I的子集,则I 交 II应该等于II。
I & II = T & Y & ( Q | W & R )
简单地,用真值表法求出唯一主析取范式。这个程序应该能比较容易实现。
Q W R T Y IsFits
1. 0 0 0 0 0 F
2. 0 0 0 0 1 F
3. 0 0 0 1 0 F
4. 0 0 0 1 1 F
5. 0 0 1 0 0 F
6. 0 0 1 0 1 F
7. 0 0 1 1 0 F
8. 0 0 1 1 1 F
9. 0 1 0 0 0 F
10. 0 1 0 0 1 F
11. 0 1 0 1 0 F
12. 0 1 0 1 1 F
13. 0 1 1 0 0 F
14. 0 1 1 0 1 F
15. 0 1 1 1 0 F
16. 0 1 1 1 1 T
17. 1 0 0 0 0 F
18. 1 0 0 0 1 F
19. 1 0 0 1 0 F
20. 1 0 0 1 1 T
21. 1 0 1 0 0 F
22. 1 0 1 0 1 F
23. 1 0 1 1 0 F
24. 1 0 1 1 1 T
25. 1 1 0 0 0 F
26. 1 1 0 0 1 F
27. 1 1 0 1 0 F
28. 1 1 0 1 1 T
29. 1 1 1 0 0 F
30. 1 1 1 0 1 F
31. 1 1 1 1 0 F
32. 1 1 1 1 1 T
则主析取范式为:
(!Q & W & R & T & Y) | (Q & !W & !R & T & Y) | (Q & !W & R &T & Y) | (Q & W & !R & T & Y) | (Q &W &R & T &Y)
代入替换,因为是简单一元的与关系,可以比较容易合并:
B=30, A 20 | NULL | NULL | NULL | A > 30 & B=30
=
B=30 & A 20 | A > 30 & B=30
做到这里就不是很确定了。对于这次,我们可以用反分配律, 得出 B = 30 & ( 2030),
B=30 & A>20。可能还有一些其他情况无法用分配律可以化简的。
化简后和II一样,得证。
对了,集合II也需要化为 主析取范式才好比较。这里不需要化。
用离散数学的知识肯定能解决
但有点像用微积分求灯泡的容积一样 有点大才小用
其实把灯泡里倒满水 量一下就行了么
A:(age>21)and(level>1)
B:(age>20)or(level>0)
首先 把每个字段分段
age :分成 [0 ,20 ,21] 三段
level :分成 [0, 1] 两端
这很容易实现
然后 每段取中点 作为测试值
age: [10,20.5,22]
level: [0.5,2]
然后 age*level 产生测试用例
放到A和B里测试
如果存在一个值属于A却不属于B……
怎么样 暴力吧
这叫乱拳打死老师傅
想想看 效率反而可能是最高的
不过 我写这样 求职您要么
楼上的,可以用蒙特卡洛的,如果tolerance高的话,但是你这样做出错的几率肯定是不能容忍的。
蒙特卡洛绝对不行 题目是要求确定的解的
你说的出错的几率指的是什么
额…貌似我理解错楼上的意思了.
等于的情况也要考虑的。
的确这样做复杂度最低,而且是可以证明的,那就是取所有的端点,以及端点的中点,联合产生检查点。
我想得太复杂了….
可证完备,自愧不如~~
对哦 如果是>=就不取中点 直接取端点
分段那一步 应该可以剪枝
如果一个字段在AB里分段一样的话 一定条件下可以忽略该字段
大家可以想想这里应该怎么写
今天要做6个小时的车 可能没精力写一个完整的程序出来了
“而且这个算法是一个比较通用的算法,MySQL和SQL Server里的Query Optimizer在优化Execution Plan的时候就是类似的算法,只是懒得去看源代码,而是用一个很简单的算法来完成。对于SQL Parser和lua,愿闻其详。”
我认为SQL Server做查询计划优化的时候主要还是根据统计信息来决定使用什么索引,如何使用索引,而非王建硕认为的那样归并查询条件的。例如最简单的一个例子:
SELECT *
FROM [Order]
WHERE [sOrderID]=’R10000510000000001′
AND [sOrderID]<>’R10000510000000001′
这样一个查询式,我想人一眼就可以看出最高效的查询计划就是返回空集合,因为不可能存在这样的记录。而SQL Server的查询计划还真是去查找这条id的记录,然后在当中筛选出id不等于的记录,也就是说,SQL Server没能认出这其实是一个空集。
根据阅微堂(http://zhiqiang.org/blog/science/computer-science/database-query-is-np-hard.html)中给出的证明来看,要证明一个查询是空集都是一个NP问题,那么判定是否是子集一定是一个NP问题,所以这个问题我赞同阅微堂的答案,没有什么多项式算法。
但是我认为可以参照SQL Server一样,为各种数据源建立统计信息,在查询时可以参考一下统计信息来得到一个近似的最优查询计划。一个问题往往在数学上没有答案时,用概率统计方法可以得到很近似最优解的解。
能否多加加上一些测试,比如4-5层括号的典型例子,
问题更有针对性?
比较各种方案,也有依据。
讨论一般意义的query subset 过于理论化了。
感谢大家的参与。我们收到了很多种不同的答案。这是一道有趣却也很实用的问题。大家的结局方案从Java,到C++,到PHP,到Python都有。技术的世界就是好,技术人员看到有挑战性的问题,撸起袖子就开始写代码,写好调好就心满意足。已经寄过来的朋友当然欢迎把答案发到自己的blog上面,晚些我会把链接给大家。
被墙了?
重新写了个算法,已经发给博主,献丑了!
只能处理QueryBuilder,不能处理NOT,可以处理多层括号,
关于把查询字符串 parse 成语法树,很有兴趣了解!
两个 OR 之间怎么比较是否是子集?
如 age > 15 OR height == 0 与 age > 20 OR gender == 1
To: freddu,
要判断第一个OR是否第二个OR的子集,只要第一个OR中的所有分子是第二个OR中任意一个分子的子集即可。
前面的表达有点问题,应该是:
要确定第一个OR是第二个OR的子集,只要第一个OR中的所有分子是第二个OR中任意一个分子的子集即可。
r= age > 15 OR height == 0 与 age > 20 OR gender == 1
==> use f1 or f2 f3 or f4 replace four exp
==> r= f1 in f3 or f1 in f4 or f2 in f3 or f2 in f4
==> r= 0 or 0 or 0 or 0
r is 0