百姓网公开笔试题:查询条件的子集判断
作者:Jian Shuo Wang 发表于:2010-05-05 09:12 · 公司的艺术 · #编程 #创业这是发布在百姓网官方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
这里是百姓网的职位。
44 Comments
2、比较操作的右端都是常量,还是有可能是变量?例如是否需要考虑 "A>B AND B>C"->isSubSet("A>C") 的情形?
$queryA = new AndQuery(
new RangeQuery('age', 20),
new NotQuery('status', true)
);
大家可以自己写一个自己顺手的builder。
比较操作只要考虑左边是field名,右边是常量就好了,这是最简单,也是到现在需要用得到的部分。
@tyler durden,我同意这个“感觉起来很难”。也同意“not that perfect but doable and feasible”,我们最需要的就是就是实用主义的解决方案,但无论什么“主义”,首先要有一个解决方案。
谢谢大家参与,有什么问题可以问我。
【1】将原问题[判断1个复杂范围是否是另1个复杂范围的子集]降解为[判断1个数是否为1个简单范围的子集]
【2】1个简单范围可以降解为2个数(或1个,当等于时);比如age>30,即取 31,999999(根据场景定义)
【3】 AND/OR的处理就比较简单了,不说了
不知道会不会有bug,具体实现就不说了,大家都懂得~
- 为实时优化的实时库(小但是快),是按照时间维度切的;
- 为了地域优化的地域库(比如上海库),是按照地域维度切的
- 为了查询优化的active广告库,是按照状态维度切的
- 为了最全的数据优化的大数据库(全却慢),可能把5年的数据都放进去
还有合并了各种维度为每种特殊情况优化的库。手工判断一个广告进哪个库,从哪个库查已经越来越复杂,会因为一个小调整而产生大调整。所有这些问题,在数据量不大或者对速度要求不高的情况下都是没有的。我要解决的是大数据量的分布式查询问题。
我们实际的应用中对于基于Solr的搜索库的切分的需求大于对MySQL的切分。MySQL其实内部的Partition等方案已经大概的解决了类似的问题。
而且这个算法是一个比较通用的算法,MySQL和SQL Server里的Query Optimizer在优化Execution Plan的时候就是类似的算法,只是懒得去看源代码,而是用一个很简单的算法来完成。对于SQL Parser和lua,愿闻其详。
@AvergerMoJo,抱歉,可否更详细一点?多谢
第一种方法是加缓存,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*相对来说更简单实用一些
以上只是一些浅见,而且很多地方也非这几个字能描述的清楚。各位看了,见笑见谅:)
写了一下午,发现写错了
如果我没理解错的话,这题狂难
不是抢答吧?
建议有答对的的就公布一下,超过三个我就放弃挣扎了……
@mikster,想法相当不错,只是以我愚见,逆波兰表达式在这个帮不了忙,但是想法和我是一致的。
@Platinum,别放弃,不是抢答,长期有效。在百姓网,经常遇到的技术问题都是没有现成答案的。虽然实际使用中大概支持个五、六级括号就好了,但是这道题是应该支持无限括号和所有And,OR,Not及括号组成的表达式的 - 都是一个算法。这道题难倒也不是特别难,就是比较耗费体力。选这个题,倒也不是因为难,而是的确这就是一个典型的应用。
现在已经收到大家的邮件了。非常感谢大家的热情。如果在寄过来算法的时候一并有简历就最好了。
我比较怀疑这个问题的下限。
我不认为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)
这样总该行了吧
@gmigh,相当清晰的算法。
@Raidenxu,抱歉,还需要考虑一下,并不是那么简单。再试试?
欢迎大家继续寄写好的代码(PHP或者Java的)到[email protected]来。如果能注明希望在百姓网工作还是仅仅是有兴趣切磋一下会最好(否则我们有点迷茫,不知道接下来怎么处理)。最好同时有简历。谢谢。
正确流程我认为是
1.预处理,主要是去除所有的not,如not(a > 3 or b > 5)改为a b and b > c 与 a > c ,后者是前者的子集
解题关键字:语法树,与或树
以下是用来测试的一些用例
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一样,得证。
但有点像用微积分求灯泡的容积一样 有点大才小用
其实把灯泡里倒满水 量一下就行了么
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......
怎么样 暴力吧
这叫乱拳打死老师傅
想想看 效率反而可能是最高的
不过 我写这样 求职您要么
你说的出错的几率指的是什么
等于的情况也要考虑的。
的确这样做复杂度最低,而且是可以证明的,那就是取所有的端点,以及端点的中点,联合产生检查点。
我想得太复杂了....
分段那一步 应该可以剪枝
如果一个字段在AB里分段一样的话 一定条件下可以忽略该字段
大家可以想想这里应该怎么写
今天要做6个小时的车 可能没精力写一个完整的程序出来了
我认为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一样,为各种数据源建立统计信息,在查询时可以参考一下统计信息来得到一个近似的最优查询计划。一个问题往往在数学上没有答案时,用概率统计方法可以得到很近似最优解的解。
问题更有针对性?
比较各种方案,也有依据。
讨论一般意义的query subset 过于理论化了。
只能处理QueryBuilder,不能处理NOT,可以处理多层括号,
关于把查询字符串 parse 成语法树,很有兴趣了解!
如 age > 15 OR height == 0 与 age > 20 OR gender == 1
要判断第一个OR是否第二个OR的子集,只要第一个OR中的所有分子是第二个OR中任意一个分子的子集即可。
要确定第一个OR是第二个OR的子集,只要第一个OR中的所有分子是第二个OR中任意一个分子的子集即可。
==> 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