分享一下SQL数据库编程大赛第一期我的解法

rollingpig

其实，我想过更进一步，就是把5*5扩展成M*M, 但是，我很悲剧的发现，在当前给定条件下，就算是简单的M=6,N=2, 就算是用上probe也是以分钟计，更别说6/3, 7/2之类的。
所以，放弃了进一步扩展的想法。

巧的是，评委们也觉得扩展成M*M将会很有意思，于是，在用"等于号"限定了球数之后，作为第二期题目了……

guapo

楼主利害啊，我先记号一下，慢慢看

guapo

楼主可否把后面几期的思路也分析一下？

solomon_007

好人，谢谢分享，慢慢品读。。。

jboracle1981

牛人

lastwinner

我在 http://www.itpub.net/thread-1407072-1-1.html
对楼主一期答案的评价
评析：构思巧妙，采用由浅入深的做法，先用probed_result探测出可以放置的球最少是多少，当然，作者期望这个值越大越好，所以在之前probed_result要调用的linesrc查询中，作者特意做了一个从大到小的倒排序（ORDER BY 1 desc），以期能从中尽早尽快的获得可能的最大的球数。然而这个代码并非就是那么完美，一旦probed_max_balls-4*:N<=0，则probed_result查询所做的工作就等于打水漂了，即便probed_max_balls-4*:N=1也占不了0.01%的便宜，rownum < power(16,:N)的条件并不科学，不过从认为此值应该是一个“不小的较合适的数”去看，则可算合理。最后的solution查询没有使用前面得到的probed_max_balls来产生一个新的制约条件也是一个遗憾。不管怎样，“浅入虎穴”的思路是不错的，值得我们学习。

lastwinner

原帖由 rollingpig 于 11-3-29 12:36 发表
如果能用上=:N的条件，性能将会提高数百倍。       

直接用，没那个胆，毕竟“正确性和完善程度”是很重要的，在题目内容中及有限的推理过程中，并不能得出 =:N的条件。可是，如果有一种方法，在SQL的内部就直接证明，的确存在5*N的摆法，那么，就可以理直气壮的使用上=:N的条件了。

这时候，灵感突然来了，如果我在SQL里嵌入一段，在求solution结果的运算变的很慢之前，就发现有存在5*N的摆法，不就解决了吗？
用rownum 来限制，应该可以在性能变糟之前就得到吧？

Tips: 特定的时候，使用rownum限定结果集，有助于提高性能，但是仅限于“只获取部分数据”
………………


经过尝试，发现N=2时，N*5出现在199, N=3,发生在1916, N=4发生在 17638。
而如果用了where rownum < :max_rows, 性能非常的好。
这时候，又有一个问题，怎么把这个:max_rows里写进去了，有两个写法，一是直接取最大，大家都按N=4的时候的50000来算，但是，就是当N=2/3是有点亏。
最后选择了Power(16,:N), 正好都cover. (其实 2*power(10,:N) 更合适).

  

最后部分既是亮点也是弱点，正如你现在自己说的“(其实 2*power(10,:N) 更合适)”
这个值合适不合适，到底取多少合适？其实是有点从答案倒推过程了

rollingpig

我也想给这个数据找一个现实意义，比如说，总数据量的千分之一之类的，但是那又更复杂了。

原帖由 lastwinner 于 2011-3-29 17:32 发表


最后部分既是亮点也是弱点，正如你现在自己说的“(其实 2*power(10,:N) 更合适)”
这个值合适不合适，到底取多少合适？其实是有点从答案倒推过程了

newkid

原帖由 lastwinner 于 2011-3-29 17:32 发表


最后部分既是亮点也是弱点，正如你现在自己说的“(其实 2*power(10,:N) 更合适)”
这个值合适不合适，到底取多少合适？其实是有点从答案倒推过程了

确实，如果不是这个“倒推”法就更完美了。SQL和过程线代码不同，一般都是穷尽的思路，非穷尽的情况下要按最悲观的情形来做假设。

rollingpig

穷尽就失去了性能的优势。
还有就是用找出first 5*N的行，但是，那也相当于预先推测存在5*N的行。

另外，从逻辑上来说，妙的是，我最后用的条件是

Balls >= max_ball - :N*4 and ball <=:N

并没有要求max_ball 一定就等于5*N, 在 max_ball =5*N-1(比如说是，N=4时，max_balls=19),同样能获得正确结果和很好的性能。

也就是说，不需要“穷尽”，假设我把power(2,:N)改成10000,2000 在N=3，4时同样能够获得很好的性能（这时候，max_balls=19, 运行4 seconds)。
就算我把power(2,:N)改为100, 只是max_ball 取得一个很差的值，结果也并不受影响，只是性能没有获得提升。

就像Oracle在执行SQL时有时候有的dynantic sampling的做法，这个sample 该是多少，也仅仅是Oracle设计的时的一个经验值。

原帖由 newkid 于 2011-3-29 21:51 发表


确实，如果不是这个“倒推”法就更完美了。SQL和过程线代码不同，一般都是穷尽的思路，非穷尽的情况下要按最悲观的情形来做假设。