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

newkid

f_find_parent写成递归了，代码确实少一些。rankX+1的bug也改过来了：

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
       parent int;
    BEGIN
       parent := parents(p_cur_cust);
       IF parent <> p_cur_cust THEN
          parent := f_find_parent(parent);
          parents(p_cur_cust) := parent;
       END IF;
       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+1;
        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;
/

lugionline

newkid 发表于 2014-3-24 03:01
f_find_parent写成递归了，代码确实少一些。rankX+1的bug也改过来了：

DECLARE

cool，最后一个回写，oracle支持这么写么

UPDATE cust SET gid=parents(id);

这样就不用循环了

lugionline

或者 UPDATE cust SET gid=f_find_parent(id); 这样可以把上面那个循环也可以去掉
另外刚才想到 rank 其实不会超过32 （平衡二叉树），所以用byte数组就够了，这样可以节省些内存

不过无论SQL中如何优化都做不过C的，刚才看了个PDF说是10^9个点，10^10个union，总共时间大概1分钟

dcllj

这些我都不懂，我是来看热闹的。

newkid

再改写一下，就不要求CUST_ID是连续的了：

DECLARE
    i int;

    TYPE t_num IS TABLE OF NUMBER INDEX BY PLS_INTEGER;
    parents t_num;
    ranks t_num;
    lv_id t_num;
    lv_gid 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
       parent int;
    BEGIN
       parent := parents(p_cur_cust);
       IF parent <> p_cur_cust THEN
          parent := f_find_parent(parent);
          parents(p_cur_cust) := parent;
       END IF;
       RETURN parent;
    END f_find_parent;
   
BEGIN
    SELECT id BULK COLLECT INTO lv_id from cust ORDER BY id;
    FOR i IN 1..lv_id.COUNT LOOP
        ranks(lv_id(i)) := 0;
        parents(lv_id(i)):=lv_id(i);
    END LOOP;
   
    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+1;
        END CASE;

    END LOOP;

    -- find for each cust
    FOR i IN 1..lv_id.count LOOP
        lv_gid(i) := f_find_parent(lv_id(i));
    END LOOP;

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

END;
/

newkid

lugionline 发表于 2014-3-24 07:20
cool，最后一个回写，oracle支持这么写么

UPDATE cust SET gid=parents(id);

这样更糟糕，每行UPDATE的时候都会调用一次PLSQL函数，有大量的上下文切换。
FORALL UPDATE是一次性将整个数组写回表中。
PL/SQL没有byte数组，我以前试过即使是BOOLEAN也不会节省内存。这个当然和C不能相比了。

tanzuwen

newkid 发表于 2014-3-24 23:02
再改写一下，就不要求CUST_ID是连续的了：

DECLARE

目前也遇到这个问题，是直接采用的connect by 做递归，测试时，数据根本就出不来。

跪求大神用文字注释一下这段逻辑！

newkid

tanzuwen 发表于 2014-11-21 16:37
目前也遇到这个问题，是直接采用的connect by 做递归，测试时，数据根本就出不来。

跪求大神用文字注释 ...

按照提问的智慧给出一个例子。

tanzuwen

newkid 发表于 2014-11-22 00:52
按照提问的智慧给出一个例子。

  FOR i IN 1..lv_id.COUNT LOOP
        ranks(lv_id(i)) := 0;             ----  这个地方好像是有问题吧，lv_id(i)这个应该是一个数组中的值，能把它当作一个下标用么！
        parents(lv_id(i)):=lv_id(i);
    END LOOP;

tanzuwen

tanzuwen 发表于 2014-11-24 11:02
FOR i IN 1..lv_id.COUNT LOOP
        ranks(lv_id(i)) := 0;             ----  这个地方好像是有问 ...

肯定会报下标溢出错识吧！