ITPUB第3届“盛拓传媒杯”SQL数据库编程大赛第1题参考解题思路

newkid

udfrog 发表于 2015-12-19 13:32
第一题最快的速度是多久？我现在能改出1.98秒，但是写法很2
我觉得你还不如直接说牛蛙，说什么某人嘛

不同环境没有可比性，反正OO那个版本在我机器上用了0.6秒。
我把你的方法用于MNK, 但是比原来的写法还慢，看来字符串操作还不如BITAND。

lastwinner

newkid 发表于 2015-12-20 09:28
不同环境没有可比性，反正OO那个版本在我机器上用了0.6秒。
我把你的方法用于MNK, 但是比原来的写法还慢 ...

字符串操作是慢，位操作应该是计算里最快的，比普通加减法都快

solomon_007

newkid 发表于 2015-12-20 09:27
第一题很好懂的吧！很多人的做法都和我大同小异。
第二题有点费劲，我写这个说明比写SQL用的时间还多，还 ...

乍看上去确实好复杂,真的得好时间慢慢看

〇〇

lastwinner 发表于 2015-12-20 13:24
字符串操作是慢，位操作应该是计算里最快的，比普通加减法都快

我测试的结果好象不是的
Microsoft Windows [版本 6.1.7601]
版权所有 (c) 2009 Microsoft Corporation。保留所有权利。

C:\Users\qiwang>sqlplus hr/hr

SQL*Plus: Release 11.2.0.2.0 Production on 星期日 12月 20 17:17:30 2015

Copyright (c) 1982, 2010, Oracle.  All rights reserved.


连接到:
Oracle Database 11g Express Edition Release 11.2.0.2.0 - Production

SQL> set timi on
SQL> with win_tpl as (
  2     select substr('XXX______;___XXX___;______XXX;X__X__X__;_X__X__X_;__X__X__X;X___X___X;__X_X_X__',level*10-9,9) as tpl
  3       from dual
  4      connect by level<=8
  5     )
  6  ,s as(select '_'c from dual union all select 'X' from dual union all select 'O' from dual)
  7  ,tuples as ( select s.c||a.c||b.c||c.c||d.c||e.c||f.c||g.c||h.c s from s,s a,s b,s c,s d,s e,s f,s g,s h ) --第1步必须在125中,
所以不能全空,where s.c||a.c||d.c<>'___'
  8  ,txo_1 as (
  9  select s,
10        case when exists(select 1 from win_tpl where s like tpl) then 'X'
11             when exists(select 1 from win_tpl where s like replace(tpl,'X','O')) then 'O'
12             else 'D'
13        end as winner
14  from tuples
15  where regexp_count(s,'X')-regexp_count(s,'O') in(0,1) and (s<>'XXXOO----') ---减少1个根本不存在的布局，结果奇怪地快了很多
16        and (regexp_count(s,'X')<3
17             or not exists (select 1
18                             from win_tpl
19                            where s like replace(tpl,'X',decode(regexp_count(s,'X')-regexp_count(s,'O'),0,'X',1,'O'))
20                           )
21             )
22        and (regexp_count(s,'_')=0
23              or exists (select 1 from win_tpl where s like tpl or s like replace(tpl,'X','O'))
24            )
25  )
26  select count(*) from txo_1;

  COUNT(*)
----------
       958

已用时间:  00: 00: 00.56
SQL> with win_tpl as (select tpl,power(2,instr(tpl,'X',1,1)-1)+power(2,instr(tpl,'X',1,2)-1)+power(2,instr(tpl,'X',1,3)-1)bpl from(
  2     select substr('XXX______;___XXX___;______XXX;X__X__X__;_X__X__X_;__X__X__X;X___X___X;__X_X_X__',level*10-9,9) as tpl
  3       from dual
  4      connect by level<=8
  5     ))
  6  ,s as(select '_'c ,0 x,0 o from dual union all select 'X',1,0 from dual union all select 'O',0,1 from dual)
  7  ,tuples as ( select s.c||a.c||b.c||c.c||d.c||e.c||f.c||g.c||h.c s ,
  8  s.x+a.x*2+b.x*4+c.x*8+d.x*16+e.x*32+f.x*64+g.x*128+h.x*256 x,
  9  s.o+a.o*2+b.o*4+c.o*8+d.o*16+e.o*32+f.o*64+g.o*128+h.o*256 o
10  from s,s a,s b,s c,s d,s e,s f,s g,s h ) --第1步必须在125中,所以不能全空,where s.c||a.c||d.c<>'___'
11  ,txo_1 as (
12  select s,
13        case when exists(select 1 from win_tpl where /*s like tpl*/bitand(x,bpl)=bpl) then 'X'
14             when exists(select 1 from win_tpl where s like replace(tpl,'X','O')) then 'O'
15             else 'D'
16        end as winner
17  from tuples
18  where regexp_count(s,'X')-regexp_count(s,'O') in(0,1) and (s<>'XXXOO----') ---减少1个根本不存在的布局，结果奇怪地快了很多
19        and (regexp_count(s,'X')<3
20             or not exists (select 1
21                             from win_tpl
22                            where s like replace(tpl,'X',decode(regexp_count(s,'X')-regexp_count(s,'O'),0,'X',1,'O'))
23                           )
24             )
25        and (regexp_count(s,'_')=0
26              or exists (select 1 from win_tpl where s like tpl or s like replace(tpl,'X','O'))
27            )
28  )
29  select count(*) from txo_1;

  COUNT(*)
----------
       958

已用时间:  00: 00: 00.60
SQL> 29
29* select count(*) from txo_1
SQL> c/select count(*) from txo_1/select * from txo_1 where rownum<=4
29* select * from txo_1 where rownum<=4
SQL> /

S                  WI
------------------ --
XXXOO____          X
OO_XXX___          X
O_OXXX___          X
_OOXXX___          X

已用时间:  00: 00: 00.14
SQL>

〇〇

魔数法对于判断棋盘没有优势
with magic as(select '00000000;00000111;00001001;10100001;00010010;00111100;10010000;01100010;01001000;11000100'm from dual)
,s as(select '_'c from dual union all select 'X' from dual union all select 'O' from dual)
,tuples as ( select s.c||a.c||b.c||c.c||d.c||e.c||f.c||g.c||h.c s from s,s a,s b,s c,s d,s e,s f,s g,s h ) --第1步必须在125中,所以不能全空,where s.c||a.c||d.c<>'___'
,txo_1 as (
select s,
      case when instr(substr(m,instr(s,'X',1,1)*9+1,8)+substr(m,instr(s,'X',1,2)*9+1,8)+substr(m,instr(s,'X',1,3)*9+1,8)+substr(m,instr(s,'X',1,4)*9+1,8)+substr(m,instr(s,'X',1,5)*9+1,8),3)>0 then 'X'
           when instr(substr(m,instr(s,'O',1,1)*9+1,8)+substr(m,instr(s,'O',1,2)*9+1,8)+substr(m,instr(s,'O',1,3)*9+1,8)+substr(m,instr(s,'O',1,4)*9+1,8)+substr(m,instr(s,'O',1,5)*9+1,8),3)>0 then 'O'
           else 'D'
      end as winner
from tuples,magic
where regexp_count(s,'X')-regexp_count(s,'O') in(0,1) and (s<>'XXXOO----') ---减少1个根本不存在的布局，结果奇怪地快了很多
      and (regexp_count(s,'X')<3
           or decode(regexp_count(s,'X')-regexp_count(s,'O'),0,instr(substr(m,instr(s,'X',1,1)*9+1,8)+substr(m,instr(s,'X',1,2)*9+1,8)+substr(m,instr(s,'X',1,3)*9+1,8)+substr(m,instr(s,'X',1,4)*9+1,8)+substr(m,instr(s,'X',1,5)*9+1,8),3)
,1,instr(substr(m,instr(s,'O',1,1)*9+1,8)+substr(m,instr(s,'O',1,2)*9+1,8)+substr(m,instr(s,'O',1,3)*9+1,8)+substr(m,instr(s,'O',1,4)*9+1,8)+substr(m,instr(s,'O',1,5)*9+1,8),3))=0
           )
      and (regexp_count(s,'_')=0
            or instr(substr(m,instr(s,'X',1,1)*9+1,8)+substr(m,instr(s,'X',1,2)*9+1,8)+substr(m,instr(s,'X',1,3)*9+1,8)+substr(m,instr(s,'X',1,4)*9+1,8)+substr(m,instr(s,'X',1,5)*9+1,8),3)>0
            or instr(substr(m,instr(s,'O',1,1)*9+1,8)+substr(m,instr(s,'O',1,2)*9+1,8)+substr(m,instr(s,'O',1,3)*9+1,8)+substr(m,instr(s,'O',1,4)*9+1,8)+substr(m,instr(s,'O',1,5)*9+1,8),3)>0
          )
)
select count(*) from txo_1;
  COUNT(*)
----------
       958

已用时间:  00: 00: 00.74
SQL> /

  COUNT(*)
----------
       958

已用时间:  00: 00: 00.50

lastwinner

我直觉也是这样，不过这帖的测试和上一帖一样，时间太短看不出优劣

〇〇

写得不那么难看,但速度慢了
SQL> with magic as(select '00000000;00000111;00001001;10100001;00010010;00111100;10010000;01100010;01001000;11000100'm from dual)
  2  ,s as(select '_'c from dual union all select 'X' from dual union all select 'O' from dual)
  3  ,tuples as ( select s.c||a.c||b.c||c.c||d.c||e.c||f.c||g.c||h.c s from s,s a,s b,s c,s d,s e,s f,s g,s h )
  4  ,txo_1 as (
  5  select s,
  6        case when instr((select sum(substr(m,instr(s,'X',1,level)*9+1,8)) from dual connect by level<=5),3)>0 then 'X'
  7             when instr((select sum(substr(m,instr(s,'O',1,level)*9+1,8)) from dual connect by level<=5),3)>0 then 'O'
  8             else 'D'
  9        end as winner
10  from tuples,magic
11  where regexp_count(s,'X')-regexp_count(s,'O') in(0,1) and (s<>'XXXOO----') ---减少1个根本不存在的布局，结果奇怪地快了很多
12        and (regexp_count(s,'X')<3
13             or decode(regexp_count(s,'X')-regexp_count(s,'O'),
14   0,instr((select sum(substr(m,instr(s,'X',1,level)*9+1,8)) from dual connect by level<=5),3)
15  ,1,instr((select sum(substr(m,instr(s,'O',1,level)*9+1,8)) from dual connect by level<=5),3))=0
16             )
17        and (regexp_count(s,'_')=0
18              or instr((select sum(substr(m,instr(s,'X',1,level)*9+1,8)) from dual connect by level<=5),3)>0
19              or instr((select sum(substr(m,instr(s,'O',1,level)*9+1,8)) from dual connect by level<=5),3)>0
20            )
21  )select count(*) from txo_1;

  COUNT(*)
----------
       958

已用时间:  00: 00: 00.57
SQL> with magic as(select '00000000;00000111;00001001;10100001;00010010;00111100;10010000;01100010;01001000;11000100'm from dual)
  2  ,s as(select '_'c from dual union all select 'X' from dual union all select 'O' from dual)
  3  ,tuples as (select s,regexp_count(s,'X')xc,regexp_count(s,'O')oc from
  4        ( select s.c||a.c||b.c||c.c||d.c||e.c||f.c||g.c||h.c s from s,s a,s b,s c,s d,s e,s f,s g,s h ))
  5  ,txo_1 as (
  6  select s,
  7        case when instr((select sum(substr(m,instr(s,'X',1,level)*9+1,8)) from dual connect by level<=xc),3)>0 then 'X'
  8             when instr((select sum(substr(m,instr(s,'O',1,level)*9+1,8)) from dual connect by level<=oc),3)>0 then 'O'
  9             else 'D'
10        end as winner
11  from tuples,magic
12  where xc-oc in(0,1) and (s<>'XXXOO----') ---减少1个根本不存在的布局，结果奇怪地快了很多
13        and (xc<3
14             or decode(regexp_count(s,'X')-regexp_count(s,'O'),
15   0,instr((select sum(substr(m,instr(s,'X',1,level)*9+1,8)) from dual connect by level<=xc),3)
16  ,1,instr((select sum(substr(m,instr(s,'O',1,level)*9+1,8)) from dual connect by level<=oc),3))=0
17             )
18        and (9-xc-oc=0
19              or instr((select sum(substr(m,instr(s,'X',1,level)*9+1,8)) from dual connect by level<=xc),3)>0
20              or instr((select sum(substr(m,instr(s,'O',1,level)*9+1,8)) from dual connect by level<=oc),3)>0
21            )
22  )select count(*) from txo_1;

  COUNT(*)
----------
       958

已用时间:  00: 00: 00.67

uc_jmh

高明的bitand和翻转呀。

minWe

做个记号，慢慢看

〇〇

newkid_ITPUB第3届“盛拓传媒杯”SQL数据库编程大赛第1题参考解题思路.pdf (103 KB, 下载次数: 102)

2015-12-25 13:35 上传

点击文件名下载附件