Гость
Войти | Профиль | Очистить
Целевая тема:
Создать новую тему:
Автор:
Действия ...
Форумы / Oracle [игнор отключен] [закрыт для гостей] / Объединить списки по общим элементам / 9 сообщений из 9, страница 1 из 1
28.09.2017, 01:53
    #39527373
Lexi-227
Lexi-227
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Объединить списки по общим элементам
Привет, мож кто в нужное русло направит )

Есть исходные данные

a,b
a,c
d,e
c,f

Для каждой строки нужно вернуть список, состоящий из общих элементов:
Код: plaintext
1.
2.
3.
4.
5.
6.
lst  res
--- --------
a,b  a,b,c,f     <--- потому что 'a' связан с 'c' (вторая строчка), 'c' связан с 'f' (последняя строчка)
a,c  a,b,c,f     <--- аналогично, 'a' связан с 'b' (первая строчка), 'c' связан с 'f' (последняя строчка) 
d,e  d,e         <--- ни 'd', ни 'e' ни с кем не связаны
c,f  a,b,c,f     <--- аналогично 1 и 2: 'c' связан 'a' (вторая строчка), 'a' связан с 'b' (первая строчка).

В реальности кол-во строк измеряется сотней тысяч, кол-во элементов в строке от 1 до 300 (элементы в строке уникальны).

Исходные данные -

Код: plsql
1.
2.
3.
4.
5.
6.
7.
8.
with ds as 
     (
       select 'a,b' as lst from dual union all
       select 'a,c' from dual union all
       select 'd,e' from dual union all
       select 'c,f' from dual
     )
select * from ds
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
28.09.2017, 02:49
    #39527376
Sayan Malakshinov
Sayan Malakshinov
Модератор форума
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Объединить списки по общим элементам
Lexi-227,

 
connected components: quick find quick union algorithm
Код: plsql
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
65.
66.
67.
68.
69.
70.
71.
72.
73.
74.
75.
76.
77.
78.
79.
80.
81.
82.
83.
84.
85.
86.
87.
88.
89.
90.
91.
92.
93.
94.
95.
96.
97.
98.
99.
100.
101.
declare
   type char_array   is table of varchar2(1) index by varchar2(1);
   type arr_elems    is table of sys.ku$_vcnt index by varchar2(1);
   root              char_array;
   root_elems        arr_elems;

   n        varchar2(1);

    l integer:=dbms_utility.get_time();

    procedure print(v in varchar2) is
    begin
      dbms_output.put_line(to_char((dbms_utility.get_time-l)/100,'0999.99')||' '||v);
      l:=dbms_utility.get_time();
    end;

   
   function get_root(n varchar2) return varchar2 is
   begin
      if root.exists(n) then 
         return root(n);
      else 
         return null;
      end if;
   end;
   
   procedure update_root(old_root varchar2,new_root varchar2) is
      i pls_integer;
   begin
      if old_root!=new_root then 
         root_elems(new_root):=root_elems(new_root) multiset union all root_elems(old_root);
         for i in 1..root_elems(old_root).count
         loop
            root(root_elems(old_root)(i)):=new_root;
         end loop;
         root_elems(old_root).delete;
       end if;
   end;
   
   procedure add_elem(p_root varchar2, p_elem varchar2) is
   begin
      if not root_elems.exists(p_root) then
         root_elems(p_root):=sys.ku$_vcnt(p_elem);
      else
         root_elems(p_root).extend();
         root_elems(p_root)(root_elems(p_root).count):=p_elem;
      end if;
   end;
   
   procedure add_link(p varchar2,q varchar2) is
      r1       varchar2(1);
      r2       varchar2(1);
      new_root varchar2(1);
   begin
      r1:=get_root(p);
      r2:=get_root(q);
      
      if r1 is null or r2 is null then
         new_root := coalesce(r1,r2,p);
         if r1 is null then add_elem(new_root,p); root(p):=new_root; end if;
         if r2 is null then add_elem(new_root,q); root(q):=new_root; end if;
      else
         new_root:=least(r1,r2);
         root(p) :=new_root;
         root(q) :=new_root;
         update_root(greatest(r1,r2),new_root);
      end if;
      
   end;

begin
   print('start');
   for r in (
      with ds as 
        (
          select 'a,b,x,y,z' as lst from dual union all
          select 'a,c' from dual union all
          select 'd,e' from dual union all
          select 'c,f' from dual
        )
      select substr(lst,1,instr(lst,',')-1) p
            ,regexp_substr(lst,'([^,])',1,n+1)  q
      from ds
          ,(select level n from dual connect by level<=300) g
      where g.n<=regexp_count(lst,'[^,]')-1
   )
   loop
      add_link(r.p, r.q);
   end loop;
   print('processed');
   print('groups:');
   
   n:= root_elems.first();
   while n is not null loop
      for i in 1..root_elems(n).count loop
         dbms_output.put(','||root_elems(n)(i));
      end loop;
      dbms_output.put_line(' ');
      n:=root_elems.next(n);
   end loop;
end;


В выделенном должен быть твой запрос
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
28.09.2017, 10:05
    #39527493
Lexi-227
Lexi-227
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Объединить списки по общим элементам
xtender,

Спасибо большое!

А на чистом SQL, интересно, это возможно решить?
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
28.09.2017, 11:13
    #39527540
Elic
Elic
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Объединить списки по общим элементам
Lexi-227А на чистом SQL, интересно, это возможно решить? объединение групп, у которых есть пересекающиеся элементы (пятничная задача ?)
Реализация множеств
Количество груп связей в many to many
Нейро связи
Группировка типа "или" - не могу придумать как реализовать
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
28.09.2017, 14:26
    #39527670
MaximaXXL
MaximaXXL
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Объединить списки по общим элементам
Lexi-227,

Вот набросал на коленках
Код: plsql
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
with ds as 
     (
       select 'a,b' as lst from dual union all
       select 'a,c' from dual union all
       select 'd,e' from dual union all
       select 'c,f' lst from dual
     )

select Root, listagg(Result_,'/') within group (order by Result_) Re
from (
        select distinct connect_by_root lst Root, lst Result_
              from (
                     select regexp_substr(lst,'[^,]+',1,level) Symb
                             ,lag(regexp_substr(lst,'[^,]+',1,level),1, substr(lst, instr(lst, ',', -1)+1)) over (partition by lst order by level) Symb2
                             ,lst  
                        from ds 
                     connect by level <= length(regexp_replace(lst,'[^,]+'))+1
                         and prior lst = lst
                         and prior dbms_random.value IS NOT NULL
                   ) T1
        where Symb != Symb2
        connect by NOCYCLE Symb = prior Symb2 and lst != prior lst 
      ) T2
group by Root


только лень переразбирать Re для дистинкта значений

Наверно не оптимально, но быстро получилось
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
28.09.2017, 15:05
    #39527703
Sayan Malakshinov
Sayan Malakshinov
Модератор форума
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Объединить списки по общим элементам
MaximaXXL,


Lexi-227В реальности кол-во строк измеряется сотней тысяч, кол-во элементов в строке от 1 до 300а на таком кол-ве?
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
28.09.2017, 15:20
    #39527721
MaximaXXL
MaximaXXL
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Объединить списки по общим элементам
xtender,

До 300 не добивал ... 3 и 4 тестил, а вот при 1 символе - увидел потерю . Спасибо.
Вот исправил:
Код: plsql
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
with ds as 
     (
       select 'a,b' as lst from dual union all
       select 'a,c' from dual union all
       select 'd,e' from dual union all
       select 'c,f' lst from dual
     )

select Root, listagg(Result_,'/') within group (order by Result_) Re
from (
        select distinct connect_by_root lst Root, lst Result_
              from (
                     select regexp_substr(lst,'[^,]+',1,level) Symb
                             ,lag(regexp_substr(lst,'[^,]+',1,level),1, substr(lst, instr(lst, ',', -1)+1)) over (partition by lst order by level) Symb2
                             ,lst  
                        from ds 
                     connect by level <= length(regexp_replace(lst,'[^,]+'))+1
                         and prior lst = lst
                         and prior dbms_random.value IS NOT NULL
                   ) T1
        --where Symb != Symb2
        connect by NOCYCLE Symb = prior Symb2 and lst != prior lst 
      ) T2
group by Root
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
28.09.2017, 16:27
    #39527784
Lexi-227
Lexi-227
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Объединить списки по общим элементам
Ребята, спасибо большое за примеры и ссылки!
Взял за основу вариант предложенный xtender, решение вполне устраивает.

Был свой вариант – в цикле по каждому элементу, который встречался более одного раза собирал новый ключ через like ‘%’||elem||’%’ к этой же таблице.
На больших объемах работало неприемлемо долго.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
28.09.2017, 16:45
    #39527804
Sayan Malakshinov
Sayan Malakshinov
Модератор форума
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Объединить списки по общим элементам
Lexi-227,

оптимизированная версия:
1) Выделенный case в new_root - важная штука для ускорения работы с большими группами.
2) Запрос перенес повыше, чтобы с логикой не мешать.
 
Код: plsql
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
65.
66.
67.
68.
69.
70.
71.
72.
73.
74.
75.
76.
77.
78.
79.
80.
81.
82.
83.
84.
85.
86.
87.
88.
89.
90.
91.
92.
93.
94.
95.
96.
97.
98.
99.
100.
101.
102.
103.
104.
105.
106.
107.
108.
109.
declare
   type char_array   is table of varchar2(1) index by varchar2(1);
   type arr_elems    is table of sys.ku$_vcnt index by varchar2(1);
   root              char_array;
   root_elems        arr_elems;

   n        varchar2(1);

   cursor cur is 
      with ds as 
        (
          select 'a,b,x,y,z' as lst from dual union all
          select 'a,c' from dual union all
          select 'd,e' from dual union all
          select 'c,f' from dual
        )
      select substr(lst,1,instr(lst,',')-1) p
            ,regexp_substr(lst,'([^,])',1,n+1)  q
      from ds
          ,(select level n from dual connect by level<=300) g
      where g.n<=regexp_count(lst,'[^,]')-1;


    l integer:=dbms_utility.get_time();

    procedure print(v in varchar2) is
    begin
      dbms_output.put_line(to_char((dbms_utility.get_time-l)/100,'0999.99')||' '||v);
      l:=dbms_utility.get_time();
    end;

   
   function get_root(n varchar2) return varchar2 is
   begin
      if root.exists(n) then 
         return root(n);
      else 
         return null;
      end if;
   end;
   
   procedure update_root(old_root varchar2,new_root varchar2) is
      i pls_integer;
   begin
      if old_root!=new_root then 
         root_elems(new_root):=root_elems(new_root) multiset union all root_elems(old_root);
         for i in 1..root_elems(old_root).count
         loop
            root(root_elems(old_root)(i)):=new_root;
         end loop;
         root_elems(old_root).delete;
       end if;
   end;
   
   procedure add_elem(p_root varchar2, p_elem varchar2) is
   begin
      if not root_elems.exists(p_root) then
         root_elems(p_root):=sys.ku$_vcnt(p_elem);
      else
         root_elems(p_root).extend();
         root_elems(p_root)(root_elems(p_root).count):=p_elem;
      end if;
   end;
   
   procedure add_link(p varchar2,q varchar2) is
      r1       varchar2(1);
      r2       varchar2(1);
      new_root varchar2(1);
      old_root varchar2(1);
   begin
      r1:=get_root(p);
      r2:=get_root(q);
      
      if r1 is null or r2 is null then
         new_root := coalesce(r1,r2,p);
         if r1 is null then add_elem(new_root,p); root(p):=new_root; end if;
         if r2 is null then add_elem(new_root,q); root(q):=new_root; end if;
      else
         case when root_elems(r1).count<root_elems(r1).count 
            then new_root:=r1;
                 old_root:=r2;
            else new_root:=r2;
                 old_root:=r1;
         end case;
         root(p) :=new_root;
         root(q) :=new_root;
         update_root(old_root,new_root);
      end if;
      
   end;

begin
   print('start');
   for r in cur
   loop
      add_link(r.p, r.q);
   end loop;
   print('processed');
   print('groups:');
   
   n:= root_elems.first();
   while n is not null loop
      for i in 1..root_elems(n).count loop
         dbms_output.put(','||root_elems(n)(i));
      end loop;
      dbms_output.put_line(' ');
      n:=root_elems.next(n);
   end loop;
end;

...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
Форумы / Oracle [игнор отключен] [закрыт для гостей] / Объединить списки по общим элементам / 9 сообщений из 9, страница 1 из 1
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение  
Полит. конфиден.  
созд. / загр.: 517ms
Закрыть
start [/forum/topic.php?fid=52&mobile=1&tid=1885182]:
 0ms
get settings:
 10ms
get forum list:
 19ms
check forum access:
 3ms
check topic access:
 3ms
track hit:
 172ms
get topic data:
 11ms
get forum data:
 3ms
get page messages:
 56ms
get tp. blocked users:
 1ms
others: 239ms
total:  517ms
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]