求一SQL算法【找团伙】

nyfor

原帖由 chen222246lei 于 2009-11-4 13:49 发表
WITH TEMP AS
(
SELECT 'a1'  COL_A,'a4' COL_B FROM DUAL UNION
SELECT 'a1'  COL_A,'a3' COL_B FROM DUAL UNION
SELECT 'a4'  COL_A,'a2' COL_B FROM DUAL UNION
SELECT 'a3'  COL_A,'a6' COL_B FROM DUAL UNION
SELECT 'a4'  COL_A,'a1' COL_B FROM DUAL UNION
SELECT 'a4'  COL_A,'a8' COL_B FROM DUAL UNION
SELECT 'a10' COL_A,'a5' COL_B FROM DUAL UNION
SELECT 'a5'  COL_A,'a9' COL_B FROM DUAL
)
SELECT MAX(TEXT1) TEXT FROM
(SELECT WMSYS.WM_CONCAT(TEXT) OVER(PARTITION BY GROP ORDER BY RN1) TEXT1,T.* FROM
  (SELECT TEXT,RN1,SUM(GROP) OVER(ORDER BY RN1) GROP,ROW_NUMBER() OVER(PARTITION BY TEXT ORDER BY RN1) RN2 FROM
    (SELECT COL_B TEXT,ROWNUM RN1,DECODE(LEVEL,1,1,0) GROP FROM
      (SELECT NULL COL_A,COL_A COL_B FROM TEMP GROUP BY COL_A
       UNION
       SELECT * FROM TEMP
      ) CONNECT BY NOCYCLE COL_A = PRIOR COL_B START WITH COL_A IS NULL
    ) T ORDER BY RN1
  ) T WHERE RN2 = 1
  ) GROUP BY GROP

1        a1,a3,a6,a4,a2,a8
2        a10,a5,a9

  
我也來一個:
with test as (
select 'a1' l,'a4' r from dual union all
select 'a1','a3' from dual union all
select 'a4','a2' from dual union all
select 'a3','a6' from dual union all
select 'a4','a1' from dual union all
select 'a4','a8' from dual union all
select 'a10','a5' from dual union all
select 'a5','a9' from dual)
select wm_concat(l)
  from (select l, sum(dbms_utility.get_hash_value(r, 100000000, 10000)) sm /* 假定值最多有10000個 */
          from (select distinct connect_by_root l l, r
                  from (select l, r
                          from test
                        union
                        select r, l from test)
                connect by nocycle l = prior r)
         group by l)
group by sm;

WM_CONCAT(L)
--------------------------------------------------------------------------------
a10,a9,a5
a1,a8,a6,a2,a4,a3

[ 本帖最后由 nyfor 于 2009-11-4 15:01 编辑 ]

nyfor

我的 dbms_utility.get_hash_value(r, 1, 100000) 這個使用似乎有點問題. 會導致結果不正確.
修改一下, 假設值最多有10000個不同的值, 則改成:
dbms_utility.get_hash_value(r, 100000000, 10000) 這可能就對了.

gkl0818

MARK下

〇〇

强手如云啊

water1108

真是高手如云呀，小弟在此深表感谢，以后可能还有问题请教各位高手，希望不吝赐教！

newkid

原帖由 chen222246lei 于 2009-11-4 13:49 发表
WITH TEMP AS
(
SELECT 'a1'  COL_A,'a4' COL_B FROM DUAL UNION
SELECT 'a1'  COL_A,'a3' COL_B FROM DUAL UNION
SELECT 'a4'  COL_A,'a2' COL_B FROM DUAL UNION
SELECT 'a3'  COL_A,'a6' COL_B FROM DUAL UNION
SELECT 'a4'  COL_A,'a1' COL_B FROM DUAL UNION
SELECT 'a4'  COL_A,'a8' COL_B FROM DUAL UNION
SELECT 'a10' COL_A,'a5' COL_B FROM DUAL UNION
SELECT 'a5'  COL_A,'a9' COL_B FROM DUAL
)
SELECT MAX(TEXT1) TEXT FROM
(SELECT WMSYS.WM_CONCAT(TEXT) OVER(PARTITION BY GROP ORDER BY RN1) TEXT1,T.* FROM
  (SELECT TEXT,RN1,SUM(GROP) OVER(ORDER BY RN1) GROP,ROW_NUMBER() OVER(PARTITION BY TEXT ORDER BY RN1) RN2 FROM
    (SELECT COL_B TEXT,ROWNUM RN1,DECODE(LEVEL,1,1,0) GROP FROM
      (SELECT NULL COL_A,COL_A COL_B FROM TEMP GROUP BY COL_A
       UNION
       SELECT * FROM TEMP
      ) CONNECT BY NOCYCLE COL_A = PRIOR COL_B START WITH COL_A IS NULL
    ) T ORDER BY RN1
  ) T WHERE RN2 = 1
  ) GROUP BY GROP

1        a1,a3,a6,a4,a2,a8
2        a10,a5,a9

这里面有个BUG, 如果加一个SELECT 'a11'  COL_A,'a8' COL_B FROM DUAL UNION...
则A11并不到结果里面。
把最里头的查询改为：
SELECT NULL COL_A,COL_A COL_B FROM (SELECT COL_A,COL_B FROM TEMP UNION ALL SELECT COL_B,COL_A FROM TEMP) GROUP BY COL_A
       UNION
       SELECT * FROM TEMP
       UNION SELECT COL_B,COL_A FROM TEMP
似乎可以解决了，但看起来还是怪怪的，因为有一个ROWNUM没有经过排序……等会有空再看看。

newkid

原帖由 nyfor 于 2009-11-4 14:38 发表

  
我也來一個:
with test as (
select 'a1' l,'a4' r from dual union all
select 'a1','a3' from dual union all
select 'a4','a2' from dual union all
select 'a3','a6' from dual union all
select 'a4','a1' from dual union all
select 'a4','a8' from dual union all
select 'a10','a5' from dual union all
select 'a5','a9' from dual)
select wm_concat(l)
  from (select l, sum(dbms_utility.get_hash_value(r, 100000000, 10000)) sm /* 假定值最多有10000個 */
          from (select distinct connect_by_root l l, r
                  from (select l, r
                          from test
                        union
                        select r, l from test)
                connect by nocycle l = prior r)
         group by l)
group by sm;

WM_CONCAT(L)
--------------------------------------------------------------------------------
a10,a9,a5
a1,a8,a6,a2,a4,a3

你这个比较好懂，但总有点不踏实……
先不说HASH本身碰撞的可能，把不同的HASH值求和，则碰撞的机会大大增加了。除非你事先为每个元素分配二进制的一位？但是这样表达的个数就太少了。

newkid

chen222246lei的思路经简化、改写：
WITH TEMP AS
(
SELECT 'a1'  COL_A,'a4' COL_B FROM DUAL UNION
SELECT 'a1'  COL_A,'a3' COL_B FROM DUAL UNION
SELECT 'a4'  COL_A,'a2' COL_B FROM DUAL UNION
SELECT 'a3'  COL_A,'a6' COL_B FROM DUAL UNION
SELECT 'a4'  COL_A,'a1' COL_B FROM DUAL UNION
SELECT 'a4'  COL_A,'a8' COL_B FROM DUAL UNION
SELECT 'a10' COL_A,'a5' COL_B FROM DUAL UNION
SELECT 'a5'  COL_A,'a9' COL_B FROM DUAL
)
SELECT WMSYS.WM_CONCAT(TEXT) FROM
  (SELECT TEXT,RT,ROW_NUMBER() OVER(PARTITION BY TEXT ORDER BY RN1) RN2 FROM
    (SELECT COL_B TEXT,ROWNUM RN1,CONNECT_BY_ROOT(COL_A) RT --- 这个ROOT的作用和原来的GROP其实是一个道理
       FROM
      (SELECT * FROM TEMP
       UNION SELECT COL_B,COL_A FROM TEMP  --- 加上双向遍历
      ) CONNECT BY NOCYCLE COL_A = PRIOR COL_B
    ) T
  ) T WHERE RN2 = 1
GROUP BY RT;
这个方法依赖于CONNECT BY的输出顺序。


nyfor的HASH方法不是很保险，用wm_concat代替后：
SELECT DISTINCT MAX(res)
  FROM (select l, wmsys.wm_concat(r) OVER(PARTITION BY l ORDER BY r) res  ---GROUP BY中的wm_concat不能排序所以先用分析函数。如果用11GR2的LISTAGG的within group (ORDER BY...)则可以省略这一步
          from (select distinct connect_by_root l l, r
                  from (select l, r
                          from test
                        union
                        select r, l from test)
                connect by nocycle l = prior r
                )
       )
GROUP BY l;

CONNECT BY的方法有不必要的遍历，PLSQL的方法必须反复扫描表，各有优缺点，但数据量大了都吃不消！我记得以前回过一个类似的帖子, 找不到了。

〇〇

nice

nyfor

沒錯,我的Hash法不保險, 昨晚洗澡的時候想到了其中的漏洞.
還是 Newkid 厲害, 一眼就看出問題了.