递归分组问题求解（疑似相似客户分组）

ocpdba591 · 发表于 2014-3-22 16:24

〇〇发表于 2014-3-22 16:21
越来越有意思了

期待被翻译成oracle

newkid · 发表于 2014-3-23 09:27

Oracle 版本：
/*
drop table cust;
drop table phone;

create table cust(id int primary key,name varchar2(30),gid int);

insert into cust(id,name) values(1,'A');
insert into cust(id,name) values(2,'B');
insert into cust(id,name) values(3,'C');
insert into cust(id,name) values(4,'D');
insert into cust(id,name) values(5,'E');

create table phone(id int, phone_num varchar2(40));

insert into phone values(1,3);
insert into phone values(1,4);
insert into phone values(2,4);
insert into phone values(3,6);
insert into phone values(2,6);

insert into phone values(4,1);
insert into phone values(5,1);

-- large test
delete from cust;
delete from phone;

declare
N int := 1000;
M int := 2;
L int := 500;
begin

insert into cust (id, name) SELECT LEVEL, 'cust' ||LEVEL FROM DUAL CONNECT BY LEVEL<=N;

insert into phone (id, phone_num)
SELECT TRUNC(dbms_random.value(1,N+1)),num
   FROM (SELECT LEVEL FROM DUAL CONNECT BY LEVEL<=M),(SELECT LEVEL num FROM DUAL CONNECT BY LEVEL<L);
end;
/

select * from cust;
select * from phone order by phone_num;

*/

------下面代码被我改写过，三个雷同的地方抽出来变成了子函数f_find_parent

DECLARE
cust_count int;

TYPE t_num IS TABLE OF NUMBER INDEX BY PLS_INTEGER;
parents t_num;
ranks t_num;
lv_id t_num;

parentX int;
parentY int;
rankX int;
rankY int;

last_phone int;

FUNCTION f_find_parent(p_cur_cust IN INTEGER) RETURN INTEGER
AS
   stack t_num;
   stack_cnt int;
   cur_cust int := p_cur_cust;
   parent int;
BEGIN
   stack_cnt :=0;

   LOOP
         parent := parents(cur_cust);
         EXIT WHEN parent = cur_cust ;
         stack_cnt := stack_cnt+1;
         stack(stack_cnt):=cur_cust;
         cur_cust := parent;
   end LOOP;

   FOR i IN 1..stack_cnt LOOP
         parents(stack(i)) := parent;
   END LOOP;

   RETURN parent;
END f_find_parent;

BEGIN
SELECT count(*) INTO cust_count from cust;
FOR i IN 1..cust_count LOOP
      parents(i) := i;
      ranks(i) := 0;

END LOOP;
lv_id := parents;

last_phone :=0;

-- union

FOR cur IN (select id, phone_num from phone order by phone_num, id) LOOP
      if cur.phone_num <> last_phone then
         -- find parent for x
         parentX := f_find_parent(cur.id);
         rankX := ranks(parentX);
         last_phone := cur.phone_num;
         CONTINUE;
      END IF;

      -- find parent for y
      parentY := f_find_parent(cur.id);
      rankY := ranks(parentY);

      CASE
      WHEN parentX = parentY THEN
         continue;
      WHEN rankX < rankY THEN
         parents(parentX) := parentY;
      WHEN rankX > rankY THEN
         parents(parentY) := parentX;
      WHEN rankX = rankY THEN
         parents(parentY) := parentX;
         ranks(parentX) := rankX;
      END CASE;

END LOOP;

-- find for each cust
FOR i IN 1..cust_count LOOP
      parentY := f_find_parent(i);
END LOOP;

FORALL i IN 1..cust_count
   UPDATE cust SET gid=parents(i) WHERE id=lv_id(i);

END;
/

该算法的限制是：假定客户号是从1开始的连续整数，这个很容易改写；
另外要求在内存里分配几个大数组，楼主的客户表如果大了很容易撑爆。

newkid · 发表于 2014-3-23 09:30

lugionline 发表于 2014-3-22 13:35
oracle支持数组耶，你说一个集合语言提供数组，这还有没有下限

T-SQL不支持数组所以我只好用字符串模拟， ...

你说的是PL/SQL中的数组吧，它可是一种过程性的语言。对PLSQL的支持是ORACLE的一大优势。

话说我们上回的第二届SQL比赛，你做了没有?

ocpdba591 · 发表于 2014-3-23 11:01

newkid 发表于 2014-3-23 09:27
Oracle 版本：
/*
drop table cust;

我验证了以下几个团伙，完全正确，而且性能比我的好太多了

示例组1：
66
559
3
示例组2：
311
4
示例组3：
1
498
247
423
51
892
408
692
213
475
271
134
194
469
218
534
128
968
807
59
708
21
95
847
210
148
193
622
825
96
609
829
549
801
331
562
592
640
293
698
576
37
277
772
540
773
898
568
871
746
804
824
503
863
414
951
187
630
803
531
127
950
204
855
示例组4：
16
53
61
63
175
382
401
747
832
979

复制代码

〇〇 · 发表于 2014-3-23 11:15

newkid 发表于 2014-3-23 09:27
Oracle 版本：
/*
drop table cust;

welldone

lugionline · 发表于 2014-3-23 18:29

newkid 发表于 2014-3-23 09:27
Oracle 版本：
/*
drop table cust;

如果是把那个函数提取出来了，那其实也没必要用堆栈，直接递归也可以，客户的ID很容易处理的，至于内存，我大致计算过，6千万大概是60M * 4 * 2=500M,的确是有点大，不过对于服务器来说这点内存实在算不了什么，你试过1千万记录大概跑了多少时间吗？这个版本的SQL Server10万记录就跑不出来了，应当是STUFF函数每次都是拷贝整块内存

lugionline · 发表于 2014-3-23 18:32

比赛没参加，哪里有时间啊

lugionline · 发表于 2014-3-23 18:35

ranks(parentX) := rankX; 这里好像翻错了，应当是

ranks(parentX) := rankX + 1;

newkid · 发表于 2014-3-23 21:10

lugionline 发表于 2014-3-23 18:35
ranks(parentX) := rankX; 这里好像翻错了，应当是

ranks(parentX) := rankX + 1;

这个是我看漏了，应该是rankx+1
那个堆栈的翻译是依样画葫芦，我没想过要改成递归。不过循环的效率要优于递归。
PLSQL的数组要加上一些开销的，没试过大的例子真正使用多少内存。

ocpdba591 · 发表于 2014-3-23 21:54

沾lugionline前辈的光，第一个精华

[精华] 递归分组问题求解（疑似相似客户分组）

浏览过的版块