Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / Oracle Новый топик    Ответить
 Рекурсивное слияние дискретных пересекающихся множеств  [new]
publexus
Member

Откуда: Москва
Сообщений: 955
Задача следующая: есть набор сущностей, которые могут быть разбиты на группы различными способами.
Задача - объединить эти группы. Группы объединяются, если они пересекаются хотя бы одним элементом. Например (9 элементов, 3 варианта группировки):
create table testtt as 
		select	1 div,	1 grp,	1 id	from dual union all
		select	1,	1,	2	from dual union all
		select	1,	1,	3	from dual union all
		select	1,	2,	4	from dual union all
		select	1,	2,	5	from dual union all
		select	1,	3,	6	from dual union all
		select	1,	4,	7	from dual union all
		select	1,	5,	8	from dual union all
		select	1,	6,	9	from dual union all

		select	2,	1,	1	from dual union all
		select	2,	1,	6	from dual union all
		select	2,	2,	2	from dual union all
		select	2,	3,	3	from dual union all
		select	2,	4,	4	from dual union all
		select	2,	5,	5	from dual union all
		select	2,	6,	7	from dual union all
		select	2,	7,	8	from dual union all

		select	3,	1,	1	from dual union all
		select	3,	1,	2	from dual union all
		select	3,	2,	3	from dual union all
		select	3,	3,	4	from dual union all
		select	3,	4,	5	from dual union all
		select	3,	5,	6	from dual union all
		select	3,	5,	9	from dual union all
		select	3,	6,	7	from dual union all
		select	3,	6,	8	from dual
	 ;
Где div - порядковый номер варианта группировки, grp - идентификатор группы в данном варианте разбиения, id - идентификатор сущности.

В результате должны получить:
grpid
11
12
13
16
19
24
25
37
38

Видно, что группы (1,2,3), (1,6) и (6,9) в пересеклись и слились в одну.
Результирующий номер группы не имеет значения, главное - правильная группировка.

Решил через PL/SQL, примерно так:
begin
	-- создаем раздел с индексом 0, где будем аггрегировать результат
	insert into testtt(div,grp,id) select 0 div,grp,id from testtt where div=1;

	-- последовательно для каждого раздела(начиная со второго) сливаем множества
	for rec in (select distinct div from testtt where div>1) loop
		merge into testtt d
			using (select distinct min(t1.grp) over(partition by t2.id) grp, t2.id
				from testtt t1 join testtt t2
					on exists(	select 1 from testtt n1 join testtt n2 on n1.id=n2.id
							where n1.div=t1.div and n1.grp=t1.grp
								and n2.div=t2.div and n2.grp=t2.grp
							)
				where t1.div=0 and t2.div=rec.div
				) s
			on (d.div=0 and d.id=s.id)
			when matched then update set d.grp=s.grp;
	end loop;
end;
select grp,id from testtt where div=0 order by grp,id;

       GRP         ID
---------- ----------
         1          1
         1          2
         1          3
         1          6
         1          9
         2          4
         2          5
         4          7
         4          8

9 rows selected.

Вот интересно мне, можно ли запросом сделать такое?
Я сначала пытался через connect by, выделял самые длинные цепочки для каждого элемента, получал через sys_connect_by_path список идентификаторов как текст, далее обрабатывал как xml - через xmltransform сортировал, сливал, и в конце концов из полученного текста извлекал списки группировок. Большой и запутанный вопрос получался, причем были ограничения (длина строки в sys_connect_by_path и т.д.).
Решал кто такую задачу?
6 сен 11, 12:02    [11233242]     Ответить | Цитировать Сообщить модератору
 Re: Рекурсивное слияние дискретных пересекающихся множеств  [new]
publexus
Member

Откуда: Москва
Сообщений: 955
Пардон в примере не хватает одной строчки:
create table testtt as 
		select	1 div,	1 grp,	1 id	from dual union all
		select	1,	1,	2	from dual union all
		select	1,	1,	3	from dual union all
		select	1,	2,	4	from dual union all
		select	1,	2,	5	from dual union all
		select	1,	3,	6	from dual union all
		select	1,	4,	7	from dual union all
		select	1,	5,	8	from dual union all
		select	1,	6,	9	from dual union all

		select	2,	1,	1	from dual union all
		select	2,	1,	6	from dual union all
		select	2,	2,	2	from dual union all
		select	2,	3,	3	from dual union all
		select	2,	4,	4	from dual union all
		select	2,	5,	5	from dual union all
		select	2,	6,	7	from dual union all
		select	2,	7,	8	from dual union all
		select	2,	8,	9	from dual union all

		select	3,	1,	1	from dual union all
		select	3,	1,	2	from dual union all
		select	3,	2,	3	from dual union all
		select	3,	3,	4	from dual union all
		select	3,	4,	5	from dual union all
		select	3,	5,	6	from dual union all
		select	3,	5,	9	from dual union all
		select	3,	6,	7	from dual union all
		select	3,	6,	8	from dual
	 ;
6 сен 11, 12:54    [11233745]     Ответить | Цитировать Сообщить модератору
 Re: Рекурсивное слияние дискретных пересекающихся множеств  [new]
Вячеслав Банкет
Member

Откуда: NY (Нефтеюганск)
Сообщений: 139
publexus,

так и не понял, как объединяются группы.

publexus
Группы объединяются, если они пересекаются хотя бы одним элементом.


Есть группы:
grp1 id = {1, 2, 3, 6}
grp2 id = {2, 3, 4, 5}
grp3 id = {3, 4, 6}
grp4 id = {4, 5, 7}
grp5 id = {5, 6, 8, 9}
grp6 id = {7, 8, 9}
grp7 id = {8}
grp8 id = {9}

Пересечения вижу такие:
grp'1 {grp1, grp2, grp3} (по id = {3})
grp'2 {grp1, grp2} (по id = {2, 3})
grp'3 {grp1, grp3} (по id = {3})
grp'4 {grp2, grp3} (по id = {3, 4})
grp'5 {grp1, grp5} (по id = {6})
grp'6 {grp2, grp4, grp5} (по id = {5})
grp'7 {grp2, grp4} (по id = {4, 5})
grp'8 {grp2, grp5} (по id = {5})
grp'9 {grp4, grp5} (по id = {5})
grp'10 {grp5, grp6, grp8} (по id = {9})
grp'11 {grp5, grp6} (по id = {8, 9})
grp'12 {grp5, grp8} (по id = {9})
grp'13 {grp6, grp8} (по id = {9})
grp'14 {grp5, grp6, grp7} (по id = {8})
grp'15 {grp5, grp7} (по id = {8})
grp'16 {grp6, grp7} (по id = {8})

publexus
Видно, что группы (1,2,3), (1,6) и (6,9) в пересеклись и слились в одну.

Вижу слияние (1,2,3). У меня это grp'1. А вот как сливаются 1 и 6? И откуда взялась группа 9?
6 сен 11, 14:46    [11234842]     Ответить | Цитировать Сообщить модератору
 Re: Рекурсивное слияние дискретных пересекающихся множеств  [new]
Ramin Hashimzade
Member

Откуда: Азербайджан, Баку
Сообщений: 9979
Блог
publexus
В результате должны получить:
grpid
11
12
13
16
19
24
25
37
38

99% это можно делать запросом просто понять точьно....

откуда вышло

1,9
3,7
3,8

почему нету в ответе

2,3
6 сен 11, 14:58    [11234934]     Ответить | Цитировать Сообщить модератору
 Re: Рекурсивное слияние дискретных пересекающихся множеств  [new]
publexus
Member

Откуда: Москва
Сообщений: 955
Вячеслав Банкет
так и не понял, как объединяются группы.
publexus
Группы объединяются, если они пересекаются хотя бы одним элементом.

publexus
Видно, что группы (1,2,3), (1,6) и (6,9) в пересеклись и слились в одну.

Вижу слияние (1,2,3). У меня это grp'1. А вот как сливаются 1 и 6? И откуда взялась группа 9?

Чтобы понятнее надо было написать так:
1. при div=1, grp=1 множество ID=(1,2,3)
2. при div=2, grp=1 множество ID=(1,6)
3. при div=3, grp=5 множество ID=(6,9)
Эти множества сливаются в одно, т.к. в 1-м и 2-м вариантах множества пересекаются по ID=1, а во 2-м и 3-м вариантах также есть общий элемент ID=6. Поэтому результатирующее множество ID=(1,2,3,6,9).
6 сен 11, 15:58    [11235648]     Ответить | Цитировать Сообщить модератору
 Re: Рекурсивное слияние дискретных пересекающихся множеств  [new]
_Nikotin
Member

Откуда: СПб
Сообщений: 2965
select dense_rank()over(order by min(rt)) grp, id
from
(
  select id, connect_by_root id rt
  from 
  (
    select a1.id, a2.id id2
    from testtt a1, testtt a2
    where a1.grp = a2.grp
      and a1.div = a2.div
    union
    select id, null
    from testtt
  )
  connect by nocycle id = prior id2
)
group by id
order by 1, 2
6 сен 11, 17:58    [11236840]     Ответить | Цитировать Сообщить модератору
 Re: Рекурсивное слияние дискретных пересекающихся множеств  [new]
orawish
Member

Откуда: Гадюкино-2 (City)
Сообщений: 15487
publexus,

1:1 stff Получить множество из связанных пар
6 сен 11, 18:05    [11236906]     Ответить | Цитировать Сообщить модератору
 Re: Рекурсивное слияние дискретных пересекающихся множеств  [new]
publexus
Member

Откуда: Москва
Сообщений: 955
_Nikotin,

Красавчик. Спасибо.
Правда, полагаю, скорость будет сильно уменьшаться при увеличении количества элементов во множествах.
7 сен 11, 15:56    [11241991]     Ответить | Цитировать Сообщить модератору
 Re: Рекурсивное слияние дискретных пересекающихся множеств  [new]
publexus
Member

Откуда: Москва
Сообщений: 955
publexus
_Nikotin,

Красавчик. Спасибо.
Правда, полагаю, скорость будет сильно уменьшаться при увеличении количества элементов во множествах.

Да, на практике оказалось, что метод _Nikotin не применим, т.к. при увеличении количества элементов в группах время выполнения увеличивается по экспоненте (уже при нескольких десятках дождаться результата невозможно).
Применил ранее описанный мной метод, но доработанный (предыдущий в некоторых случаях работал некорректно):

declare
	fl	integer; -- флажок для обозначения окончания циклов слияний
	div_max	integer;
begin
	select max(div) into div_max from testtt;

	-- создаем раздел с индексом 0, где будем аггрегировать результат
	insert into testtt(div,grp,id) select 0 div,grp,id from testtt where div=1;

	loop
		fl	:= null;

		-- последовательно для каждого раздела сливаем множества с результатирующим множеством
		for d in 1..div_max loop
			merge into testtt d
				using (select distinct min(t1.grp) over(partition by t2.id) grp, t2.id
					from testtt t1 join testtt t2
						on exists(select 1 from testtt n1 join testtt n2 on n1.id=n2.id
								where n1.div=t1.div and n1.grp=t1.grp
									and n2.div=t2.div and n2.grp=t2.grp)
					where t1.div=0 and t2.div=d
					) s
				on (d.div=0 and d.id=s.id)
				when matched then update set d.grp=s.grp where d.grp<>s.grp;

			fl	:= case when sql%rowcount>0 then 1 else fl end;
		end loop;

		-- если слияний больше нет, то выход из цикла
		exit when fl is null;
	end loop;
end;
/

Работает шустро даже при десятках тысяч элементов.
Может кому пригодится.
13 сен 11, 12:58    [11268730]     Ответить | Цитировать Сообщить модератору
 Re: Рекурсивное слияние дискретных пересекающихся множеств  [new]
orawish
Member

Откуда: Гадюкино-2 (City)
Сообщений: 15487
publexus
..

Работает шустро даже при десятках тысяч элементов.
Может кому пригодится.

спасибо, конечно. но это врядли.
вот метод, на который выше я ссылку давал обрабатывает множества из десятков миллионов элементов (больше - как то не надо было пока ) без (видимой глазом) деградации производительности и со скоростью ~1 минута на каждый 1e6 множества
(и это не на экзадате ни разу, а на вполне себе обычных дровах)
13 сен 11, 13:35    [11269045]     Ответить | Цитировать Сообщить модератору
 Re: Рекурсивное слияние дискретных пересекающихся множеств  [new]
publexus
Member

Откуда: Москва
Сообщений: 955
orawish
publexus
..

Работает шустро даже при десятках тысяч элементов.
Может кому пригодится.

спасибо, конечно. но это врядли.
вот метод, на который выше я ссылку давал обрабатывает множества из десятков миллионов элементов (больше - как то не надо было пока ) без (видимой глазом) деградации производительности и со скоростью ~1 минута на каждый 1e6 множества
(и это не на экзадате ни разу, а на вполне себе обычных дровах)

Ну и что, будем ... мериться?
Твое "идеальное решение" рушится при большом количестве уникальных значений в парах на "ORA-01426: numeric overflow" или "ORA-06500: PL/SQL: storage error", а может и еще на чем.
Сам попробуй измени в своем тесте dbms_random.value(1,5e5) на dbms_random.value(1,5e10), гений.
13 сен 11, 14:52    [11269760]     Ответить | Цитировать Сообщить модератору
 Re: Рекурсивное слияние дискретных пересекающихся множеств  [new]
orawish
Member

Откуда: Гадюкино-2 (City)
Сообщений: 15487
publexus
..
Сам попробуй измени в своем тесте dbms_random.value(1,5e5) на dbms_random.value(1,5e10), гений.

поскромнее бы себя вели, по крайней мере до тех пор, пока узнаете что такое binary_integer
13 сен 11, 16:46    [11270803]     Ответить | Цитировать Сообщить модератору
 Re: Рекурсивное слияние дискретных пересекающихся множеств  [new]
publexus
Member

Откуда: Москва
Сообщений: 955
orawish
publexus
..
Сам попробуй измени в своем тесте dbms_random.value(1,5e5) на dbms_random.value(1,5e10), гений.

поскромнее бы себя вели, по крайней мере до тех пор, пока узнаете что такое binary_integer

А что, ограничение значения binary_integer в дапазоне (-2,147,483,647 to 2,147,483,647) как то связано с:
ORA-06500: PL/SQL: storage error
ORA-04030: out of process memory when trying to allocate 16396 bytes (koh-kghu call ,pmucalm coll)
?
13 сен 11, 17:25    [11271153]     Ответить | Цитировать Сообщить модератору
 Re: Рекурсивное слияние дискретных пересекающихся множеств  [new]
orawish
Member

Откуда: Гадюкино-2 (City)
Сообщений: 15487
publexus
orawish
пропущено...

поскромнее бы себя вели, по крайней мере до тех пор, пока узнаете что такое binary_integer

А что, ограничение значения binary_integer в дапазоне (-2,147,483,647 to 2,147,483,647) как то связано с:
ORA-06500: PL/SQL: storage error
ORA-04030: out of process memory when trying to allocate 16396 bytes (koh-kghu call ,pmucalm coll)
?

прогресс налицо - вы уже выбрали нужную процедуру из двух.
следующий шаг - попробуйте понять что за параметры вы суете в dbms_random.value и что
получается, если разыгрывать пару случайных значений по множеству на пять порядков больше размера множества.
я когда тесткейс делал - (кое как,но таки) думал про то, что делаю.
попробуйте подумать и вы (прежде чем непонятные ручки в приборе крутить)
13 сен 11, 17:46    [11271323]     Ответить | Цитировать Сообщить модератору
 Re: Рекурсивное слияние дискретных пересекающихся множеств  [new]
publexus
Member

Откуда: Москва
Сообщений: 955
orawish
следующий шаг - попробуйте понять что за параметры вы суете в dbms_random.value и что
получается, если разыгрывать пару случайных значений по множеству на пять порядков больше размера множества.
я когда тесткейс делал - (кое как,но таки) думал про то, что делаю.
попробуйте подумать и вы (прежде чем непонятные ручки в приборе крутить)

Я как раз и эмулировал вариант исходных данных, который обрабатывается моим алгоритмом на практике: записей много, пересечений мало.
13 сен 11, 17:55    [11271410]     Ответить | Цитировать Сообщить модератору
 Re: Рекурсивное слияние дискретных пересекающихся множеств  [new]
orawish
Member

Откуда: Гадюкино-2 (City)
Сообщений: 15487
publexus
..
Я как раз и эмулировал вариант исходных данных, который обрабатывается моим алгоритмом на практике: записей много, пересечений мало.

лимиты у pl/sql, разумеется, есть.
и на размер ассоциативного массива тоже (в том смысле, что когда-нибудь память на любой железке и платформе закончится)
SQL> declare
  2    arr dbms_sql.number_table;
  3  begin
  4    for i in 1..1e9 loop
  5  	 arr(i):=null;
  6    end loop;
  7  exception when others then
  8    dbms_output.put_line(arr.count);
  9    raise;
 10  end;
 11  /
28548415                                                                        
declare
*
ошибка в строке 1:
ORA-06500: PL/SQL: Ошибка памяти 
ORA-04030: выход за пределы памяти процесса при попытке выделить 16356 байт 
(koh-kghu call ,pmucalm coll) 
ORA-06512: на  line 9 
это 11gR2 на нотбучем виндовозе7
13 сен 11, 18:31    [11271554]     Ответить | Цитировать Сообщить модератору
 Re: Рекурсивное слияние дискретных пересекающихся множеств  [new]
publexus
Member

Откуда: Москва
Сообщений: 955
orawish
лимиты у pl/sql, разумеется, есть.
и на размер ассоциативного массива тоже (в том смысле, что когда-нибудь память на любой железке и платформе закончится)

Вот и я про тоже, если мне надо обработать 250 миллионов записей на предмет связывания, придется пользоваться обычными таблицами и "неоптимальными" алгоритмами.
14 сен 11, 09:35    [11273347]     Ответить | Цитировать Сообщить модератору
 Re: Рекурсивное слияние дискретных пересекающихся множеств  [new]
orawish
Member

Откуда: Гадюкино-2 (City)
Сообщений: 15487
publexus
orawish
лимиты у pl/sql, разумеется, есть.
и на размер ассоциативного массива тоже (в том смысле, что когда-нибудь память на любой железке и платформе закончится)

Вот и я про тоже, если мне надо обработать 250 миллионов записей на предмет связывания, придется пользоваться обычными таблицами и "неоптимальными" алгоритмами.

..либо делить задачу на части (числом несколько).
боюсь, неоптимальные алгоритмы на обработке 250e6 записей исполняться будут вечность
14 сен 11, 11:54    [11274272]     Ответить | Цитировать Сообщить модератору
 Re: Рекурсивное слияние дискретных пересекающихся множеств  [new]
Сергей Арсеньев
Member

Откуда:
Сообщений: 4118
publexus,

Помимо экпоненциальной сложности алгоритма, маленький вопрос можно -
исходное множество может измениться за время работы алгоритма?
14 сен 11, 12:20    [11274542]     Ответить | Цитировать Сообщить модератору
 Re: Рекурсивное слияние дискретных пересекающихся множеств  [new]
publexus
Member

Откуда: Москва
Сообщений: 955
Сергей Арсеньев
publexus,

Помимо экпоненциальной сложности алгоритма, маленький вопрос можно -
исходное множество может измениться за время работы алгоритма?

Нет, не изменится. К тому же сложность алгоритма не экспоненциальная, а, по-моему, геометрическая (экспоненциальная была для иерархического запроса). Пока только обрабатывал массив размером ~ 3 млн. записей - отработал примерно за 1 минуту.
14 сен 11, 13:08    [11274922]     Ответить | Цитировать Сообщить модератору
 Re: Рекурсивное слияние дискретных пересекающихся множеств  [new]
orawish
Member

Откуда: Гадюкино-2 (City)
Сообщений: 15487
publexus
Сергей Арсеньев
publexus,

Помимо экпоненциальной сложности алгоритма, маленький вопрос можно -
исходное множество может измениться за время работы алгоритма?

Нет, не изменится. К тому же сложность алгоритма не экспоненциальная, а, по-моему, геометрическая (экспоненциальная была для иерархического запроса). Пока только обрабатывал массив размером ~ 3 млн. записей - отработал примерно за 1 минуту.

попробуйте тесткейс нарисовать, имхо, это не очень сложно - вы же представляете ваше распределение данных
14 сен 11, 13:20    [11275012]     Ответить | Цитировать Сообщить модератору
 Re: Рекурсивное слияние дискретных пересекающихся множеств  [new]
_Nikotin
Member

Откуда: СПб
Сообщений: 2965
publexus
К тому же сложность алгоритма не экспоненциальная, а, по-моему, геометрическая

14 сен 11, 13:23    [11275045]     Ответить | Цитировать Сообщить модератору
 Re: Рекурсивное слияние дискретных пересекающихся множеств  [new]
Сергей Арсеньев
Member

Откуда:
Сообщений: 4118
publexus,

Можно попробовать изврат.


Партиционируете исходные данные по div и grp
Создаете таблицу приёмник с grp и id.

Дальше сравниваете партицию исходной с таблицей приёмником на предмет в каких ее группах присутствуют элементы из партиции исходной.
Если таковых нет -добавляете новую группу и переливаете туда партицию.
Если есть то у первой попавшейся запоминаете номер и перливаете партицию в эту группу. А у остальных (если групп несколько) меняете номер на запомненный.

Переходим к следующей партиции.

По окончании, если требуется, перенумеровываем группы на предмет отсутствия пропусков.
14 сен 11, 13:39    [11275239]     Ответить | Цитировать Сообщить модератору
 Re: Рекурсивное слияние дискретных пересекающихся множеств  [new]
publexus
Member

Откуда: Москва
Сообщений: 955
Сергей Арсеньев,

Так у меня примерно так и организованно, если внимательно присмотреться. Тем более, так как бОльшая часть групп - со всего лишь одним элементом, то их вообще можно исключить из обработки.
14 сен 11, 14:00    [11275420]     Ответить | Цитировать Сообщить модератору
Все форумы / Oracle Ответить