查看: 2058|回复: 5

第2届“盛拓传媒杯”SQL数据库编程大赛解题思路分享(demonat)

[复制链接]
论坛徽章:
289
蛋疼蛋
日期:2013-03-29 13:46:58优秀写手
日期:2013-12-24 06:00:12福特
日期:2014-02-17 17:30:59生肖徽章:兔
日期:2012-05-24 19:03:36SQL极客
日期:2013-12-09 14:13:35ITPUB季度 技术新星
日期:2014-02-24 11:00:06IT宝贝
日期:2014-08-27 10:32:17马上加薪
日期:2014-08-05 09:18:33SQL数据库编程大师
日期:2016-01-13 10:30:43玉石琵琶
日期:2014-03-04 16:46:07
发表于 2013-12-23 17:15 | 显示全部楼层 |阅读模式
依葫芦画瓢写一个
第一题解得比较烂,bug太多就不贴了,总体思路是
1.将其他用户的徽章和自己要出的徽章放在一个视图里,做成一个in 和一个out的列的视图里,id为0的行是自己,且in为空
例如
user_id    in       out
0                      德国
2             德国   虎
2.递归找出所有能换到所缺徽章的路径(不关心徽章个数)
3.最后检查用户id,个数是否正确。


第二题(偷懒直接copy评委的评语了)

先找出所有雷的坐标,然后在算出雷周围的坐标,分组后计数。这些坐标中可能也包括了雷点。
    最后用所有坐标集合和上述两个做外连接算出要拼接的字符(数字或地雷或空格),用Wm_Concat拼成一串。
    Wm_Concat里面的顺序是不受控制的,应该用LISTAGG更好。
    在计算地雷邻居坐标的时候,和8行的小集合做了笛卡尔积,比起和所有坐标的集合做笛卡尔积的方法更加高效。

这一题如果去掉正则,用LISTAGG代替wm_concat效率会更好。


附加题
思路(继续copy):
本解法试图将连续的空位分片,找出其中可以确定的,遍历剩下的成片空位的组合,如果组合中的空位总数=未分配雷数,则可能为答案, 对其进行校验。

步骤:
1.求出连续的空格
2.根据数字找出能够确定是雷的空格
3.根据第2步和第1步结果求出确定的连续的雷
4.根据第3步结果求出确定的不是雷的空格
5.根据第4步和第一步结果求出确定的连续的不是雷的空格
6.遍历并校验剩下的不确定的连续空格的组合



求连续空格的部分之前连9*9的都弄不出来,后来做了一些优化:
posn 为pos的相邻空格
例如
1 2 3
4 5 6
都是空格
对于5的话有(5,1) , (5,2), (5,3), (5,4), (5,6)
用min或max函数将数据量减到最小留下 (5,1) 或者(5,6)


Rl AS
(SELECT Pos, MIN(Ps) Posn  /*减少递归路径*/
    FROM (SELECT *
            FROM Ra
           WHERE Vn = ' '
              OR Ps IS NULL)
   WHERE v = ' '
   GROUP BY Pos),
Rg AS
(SELECT Pos, MAX(Ps) Posn /*减少递归路径*/
    FROM (SELECT *
            FROM Ra
           WHERE Vn = ' '
              OR Ps IS NULL)
   WHERE v = ' '
   GROUP BY Pos),
Re AS
( /* 求出相关联的块的集合*/
  SELECT DISTINCT Connect_By_Root(Pos) Root, Pos
    FROM Rl
   START WITH Sign((SELECT COUNT(*) FROM Rl WHERE Pos < Posn) -
              (SELECT COUNT(*) FROM Rg WHERE Pos > Posn)) IN (1, 0) /*判断从左上角还是右下角开始*/
              AND (Pos < Posn /*从左上角的块或者单独的块开始*/
           OR Posn IS NULL)  
  CONNECT BY PRIOR Pos = Posn
         AND Pos > PRIOR Pos
  UNION ALL
  SELECT DISTINCT Connect_By_Root(Pos) Root, Pos
    FROM Rg
   START WITH Sign((SELECT COUNT(*) FROM Rl WHERE Pos < Posn) -
              (SELECT COUNT(*) FROM Rg WHERE Pos > Posn)) = -1 /*判断从左上角还是右下角开始*/
              AND (Pos > Posn /*从右下角的块或者单独的块开始*/
           OR Posn IS NULL)
  CONNECT BY PRIOR Pos = Posn
         AND Pos < PRIOR Pos)

示例图
4*4的连续空格,矩形是比较理想的情况
Rl
































Rg

































然后判断顶点(箭头方向唯一的那个)的个数,哪个少走哪条分支,一样多走Rl

稍微变一下,X是数字
Rl

X


X






X


X






















pos<posn(箭头向右)有2个

Rg

X


X





X

X





















pos>posn(箭头向左)有1个
这种就是走的Rg的分支

但这个思路是不能解决所有阵型的
下面这个就被划成了红色和黑色2个集合。效率就没那么好了
Rl

X


X






X


X


X


X






X


X


























X


X






X


X


X


X






X


X


做了这个优化之后,30*30的那个奇葩还是耗时40s,但至少能搞出来了
但是有个很奇怪的情况就是第二次执行,就只要10多秒了
发现2次的执行计划不同
然后在newkid的指导下,认识了cardinality feedback这玩意儿
加上hint固定住计划,然后去掉了所有的正则表达式,优化到8秒

大赛完了又赶紧学了个model,受益匪浅啊。


q1.sql (4.51 KB, 下载次数: 2)
论坛徽章:
289
蛋疼蛋
日期:2013-03-29 13:46:58优秀写手
日期:2013-12-24 06:00:12福特
日期:2014-02-17 17:30:59生肖徽章:兔
日期:2012-05-24 19:03:36SQL极客
日期:2013-12-09 14:13:35ITPUB季度 技术新星
日期:2014-02-24 11:00:06IT宝贝
日期:2014-08-27 10:32:17马上加薪
日期:2014-08-05 09:18:33SQL数据库编程大师
日期:2016-01-13 10:30:43玉石琵琶
日期:2014-03-04 16:46:07
 楼主| 发表于 2013-12-23 17:20 | 显示全部楼层
向各位牛人学习吧

使用道具 举报

回复
论坛徽章:
401
紫蛋头
日期:2012-05-21 10:19:41迷宫蛋
日期:2012-06-06 16:02:49奥运会纪念徽章:足球
日期:2012-06-29 15:30:06奥运会纪念徽章:排球
日期:2012-07-10 21:24:24鲜花蛋
日期:2012-07-16 15:24:59奥运会纪念徽章:拳击
日期:2012-08-07 10:54:50奥运会纪念徽章:羽毛球
日期:2012-08-21 15:55:33奥运会纪念徽章:蹦床
日期:2012-08-21 21:09:51奥运会纪念徽章:篮球
日期:2012-08-24 10:29:11奥运会纪念徽章:体操
日期:2012-09-07 16:40:00
发表于 2013-12-23 20:16 | 显示全部楼层
还是没理解

使用道具 举报

回复
论坛徽章:
289
蛋疼蛋
日期:2013-03-29 13:46:58优秀写手
日期:2013-12-24 06:00:12福特
日期:2014-02-17 17:30:59生肖徽章:兔
日期:2012-05-24 19:03:36SQL极客
日期:2013-12-09 14:13:35ITPUB季度 技术新星
日期:2014-02-24 11:00:06IT宝贝
日期:2014-08-27 10:32:17马上加薪
日期:2014-08-05 09:18:33SQL数据库编程大师
日期:2016-01-13 10:30:43玉石琵琶
日期:2014-03-04 16:46:07
 楼主| 发表于 2013-12-24 17:25 | 显示全部楼层
〇〇 发表于 2013-12-23 20:16
还是没理解

是我表达得不好么

使用道具 举报

回复
论坛徽章:
289
蛋疼蛋
日期:2013-03-29 13:46:58优秀写手
日期:2013-12-24 06:00:12福特
日期:2014-02-17 17:30:59生肖徽章:兔
日期:2012-05-24 19:03:36SQL极客
日期:2013-12-09 14:13:35ITPUB季度 技术新星
日期:2014-02-24 11:00:06IT宝贝
日期:2014-08-27 10:32:17马上加薪
日期:2014-08-05 09:18:33SQL数据库编程大师
日期:2016-01-13 10:30:43玉石琵琶
日期:2014-03-04 16:46:07
 楼主| 发表于 2013-12-24 17:27 | 显示全部楼层
求相邻空格的部分在优化之前算是一个图的问题,之后简化为树
但没有完美地解决问题

使用道具 举报

回复
招聘 : 系统分析师
论坛徽章:
484
马上有钱
日期:2014-02-19 11:55:14itpub13周年纪念徽章
日期:2014-09-29 01:14:14itpub13周年纪念徽章
日期:2014-10-08 15:15:25itpub13周年纪念徽章
日期:2014-10-08 15:15:25马上有对象
日期:2014-10-12 11:58:40马上有车
日期:2014-11-16 17:11:29慢羊羊
日期:2015-02-09 17:04:38沸羊羊
日期:2015-03-04 14:43:432015年新春福章
日期:2015-03-06 11:57:31ITPUB年度最佳版主
日期:2015-03-18 15:48:48
发表于 2013-12-31 04:28 | 显示全部楼层
写得有点散,楼主再整理修饰下,说明再结合代码清楚一些,精华就给你加上

使用道具 举报

回复

您需要登录后才可以回帖 登录 | 注册

本版积分规则 发表回复

TOP技术积分榜 社区积分榜 徽章 团队 统计 知识索引树 积分竞拍 文本模式 帮助
  ITPUB首页 | ITPUB论坛 | 数据库技术 | 企业信息化 | 开发技术 | 微软技术 | 软件工程与项目管理 | IBM技术园地 | 行业纵向讨论 | IT招聘 | IT文档
  ChinaUnix | ChinaUnix博客 | ChinaUnix论坛
CopyRight 1999-2011 itpub.net All Right Reserved. 北京盛拓优讯信息技术有限公司版权所有 联系我们 
京ICP备09055130号-4  北京市公安局海淀分局网监中心备案编号:11010802021510 广播电视节目制作经营许可证:编号(京)字第1149号
  
快速回复 返回顶部 返回列表