ReSQL.ru
     
powered by simpleCommunicator - 2.0.61     © 2026 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / Oracle [игнор отключен] [закрыт для гостей] / Объединить списки по общим элементам
9 сообщений из 9, страница 1 из 1
Объединить списки по общим элементам
    #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, 01:53
| Ответить | Цитировать | Написать  
Объединить списки по общим элементам
    #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, 02:49
| Ответить | Цитировать | Написать  
Объединить списки по общим элементам
    #39527493
Lexi-227
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Lexi-227
Гость
xtender,

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

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


Lexi-227В реальности кол-во строк измеряется сотней тысяч, кол-во элементов в строке от 1 до 300а на таком кол-ве?
...
Рейтинг: 0 / 0
28.09.2017, 15:05
| Ответить | Цитировать | Написать  
Объединить списки по общим элементам
    #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, 15:20
| Ответить | Цитировать | Написать  
Объединить списки по общим элементам
    #39527784
Lexi-227
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Lexi-227
Гость
Ребята, спасибо большое за примеры и ссылки!
Взял за основу вариант предложенный xtender, решение вполне устраивает.

Был свой вариант – в цикле по каждому элементу, который встречался более одного раза собирал новый ключ через like ‘%’||elem||’%’ к этой же таблице.
На больших объемах работало неприемлемо долго.
...
Рейтинг: 0 / 0
28.09.2017, 16:27
| Ответить | Цитировать | Написать  
Объединить списки по общим элементам
    #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
28.09.2017, 16:45
| Ответить | Цитировать | Написать  
9 сообщений из 9, страница 1 из 1
Форумы / Oracle [игнор отключен] [закрыт для гостей] / Объединить списки по общим элементам
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение   Полит. конфиден.  
NoSQL.ru       Кролег: Проекты, Новости, Чат       РЕД ФОРУМ       Фотоальбом: Участники, Встречи
Закрыть
start [/forum/topic.php?fid=52&msg=39527721&tid=1885182]:
 0ms
get settings:
 11ms
get forum list:
 15ms
check forum access:
 3ms
check topic access:
 3ms
track hit:
 32ms
get topic data:
 8ms
get forum data:
 2ms
get page messages:
 44ms
get tp. blocked users:
 2ms
others: 232ms
total:  352ms
созд. / загр.: 352ms
x
x
Закрыть


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