Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / Microsoft SQL Server Новый топик    Ответить
 Пересечение множеств.  [new]
b9594
Member

Откуда:
Сообщений: 14
Здравствуйте.
Есть таблица с данными:
DECLARE @Table TABLE(id1 int, id2 int) 
INSERT INTO @Table VALUES
( 1 , 2 ),
( 1 , 9 ),
( 1 , 6 ),
( 1 , 4 ),
( 2 , 8 ),
( 2 , 5 ),
( 2 , 1 ),
( 3 , 9 ),
( 3 , 6 ),
( 3 , 4 ),
( 3 , 6 ),
( 3 , 8 ),
( 3 , 5 )
Надо найти номера множеств id1 и их совпадающие последовательности id2 по заданной длине последовательностей (параметр k).

Например:
Для k=3
id1 id2
1-3 9-6-4

Для k=2
id1 id2
1-3 9-6
1-3 6-4
2-3 8-5

Подскажите как это реализовать? Спасибо.
2 май 11, 19:36    [10595811]     Ответить | Цитировать Сообщить модератору
 Re: Пересечение множеств.  [new]
step_ks
Member

Откуда:
Сообщений: 936
b9594
Например:
Для k=3
id1 id2
1-3 9-6-4

почему не 6-9-4 ?

b9594
Для k=2
id1 id2
1-3 9-6
1-3 6-4
2-3 8-5


почему нет 1-3, 9-4?
2 май 11, 20:57    [10596022]     Ответить | Цитировать Сообщить модератору
 Re: Пересечение множеств.  [new]
b9594
Member

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

Потому как последовательность должна быть строго задана.
2 май 11, 22:26    [10596355]     Ответить | Цитировать Сообщить модератору
 Re: Пересечение множеств.  [new]
step_ks
Member

Откуда:
Сообщений: 936
Предлагаете участникам форума самим догадываться, чем определяется порядок вашей последовательности в id2?
Попытка 1: убыванием id2?
2 май 11, 23:13    [10596485]     Ответить | Цитировать Сообщить модератору
 Re: Пересечение множеств.  [new]
b9594
Member

Откуда:
Сообщений: 14
Может я путано объяснил задачу:
В таблице @Table поле id1 содержит номер множества, id2 - элементы множества.
Чтобы обозначить последовательность, можно ввести нумерацию записей (поле sn).
Множества могут пересекаться. k - количество общих последовательно идущих элементов.
Если k=3, то надо найти все множества, которые пересекаются по трем последовательно идущим элементам. В данном примере этому условию удовлетворяют только 1-е и 3-е множества, которые пересеклись по элементам 9, 6 и 4.

DECLARE @Table TABLE(sn int, id1 int, id2 int) 
INSERT INTO @Table VALUES
(1, 1 , 2 ),
(2, 1 , 9 ),
(3, 1 , 6 ),
(4, 1 , 4 ),
(5, 2 , 8 ),
(6, 2 , 5 ),
(7, 2 , 1 ),
(8, 3 , 9 ),
(9, 3 , 6 ),
(10, 3 , 4 ),
(11, 3 , 6 ),
(12, 3 , 8 ),
(13, 3 , 5 )
Можно ли решить эту задачу средствами T-SQL или лучше все сделать на клиенте?
3 май 11, 19:31    [10600505]     Ответить | Цитировать Сообщить модератору
 Re: Пересечение множеств.  [new]
iljy
Member

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

declare @k int =2
declare @t table (id1 int, s varchar(max))

insert @t
select t1.id1, s from @Table t1
	cross apply
(
	select CAST(id2 as varchar) +'-'
	from(
		select *, COUNT(*) over() as cnt
		from(
			select top(@k) id2
			from @Table t
			where t.id1 = t1.id1 and t.sn >= t1.sn
			order by sn
		)t
	)t
	where cnt = @k
	for xml path('')
)t2(s)
where s is not null

select CAST(t1.id1 as varchar) + '-' + CAST(t2.id1 as varchar) ids, LEFT(t1.s, len(t1.s)-1) s
from @t t1 join @t t2
	on t1.id1 < t2.id1 and t1.s = t2.s
3 май 11, 20:00    [10600584]     Ответить | Цитировать Сообщить модератору
 Re: Пересечение множеств.  [new]
b9594
Member

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

спасибо большое, работает.
Но в таблице, где 170 тыс записей, выполнение запроса для k=5 длится больше 30 минут:(
Как можно ускорить? (индексы для id1, id2 построил)
4 май 11, 22:48    [10607042]     Ответить | Цитировать Сообщить модератору
 Re: Пересечение множеств.  [new]
iljy
Member

Откуда:
Сообщений: 8711
b9594
170 тыс записей

Предупреждать надо Попробуйте так.
DECLARE @Table TABLE(sn int, id1 int, id2 int) 
INSERT INTO @Table VALUES
(1, 1 , 2 ),
(2, 1 , 9 ),
(3, 1 , 6 ),
(4, 1 , 4 ),
(5, 2 , 8 ),
(6, 2 , 5 ),
(7, 2 , 1 ),
(8, 3 , 9 ),
(9, 3 , 6 ),
(10, 3 , 4 ),
(11, 3 , 6 ),
(12, 3 , 8 ),
(13, 3 , 5 )

create table #ttt(id1 int, id2 int, RN int, primary key(id1,rn))

insert #ttt
select id1,id2, ROW_NUMBER() over(partition by id1 order by sn) RN from @Table

create index IX_id2 on #ttt(id2, id1)

declare @k int = 2

create table #tt2 (id1_1 int, id1_2 int, RN1 int, RN2 int, primary key(id1_1,id1_2))

insert #tt2
select t1.id1, t2.id1, MIN(t1.RN) mi_n, MAX(t1.RN) ma_n
from #ttt t1 join #ttt t2 on t1.id2 = t2.id2 and t2.id1 > t1.id1
group by t1.id1, t2.id1, t1.RN-t2.RN
having COUNT(*) >= @k

select cast(t1.id1_1 as varchar) +'-' + cast(t1.id1_2 as varchar) ids, left(s, len(s)-1) s from
#tt2 t1 join master..spt_values t2 on t2.type = 'P' and t2.number between t1.RN1 and t1.RN2-@k+1
	cross apply
(
	select CAST(id2 as varchar) + '-'
	from #ttt t
	where t.id1 = t1.id1_1 and t.RN between t2.number and t2.number+@k-1
	order by RN
	for xml path('')
)t(s)

drop table #ttt
drop table #tt2
Можете выложить дамп своих данных (bcp выгрузите, либо в отдельную базу и бакап сюда), тогда попробую еще пооптимизировать.
5 май 11, 13:04    [10609358]     Ответить | Цитировать Сообщить модератору
 Re: Пересечение множеств.  [new]
b9594
Member

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

Выполнение запроса закончилось ошибкой:

Нарушение "PK__#tt2______59AE98380AD2A005" ограничения PRIMARY KEY. Невозможно вставить повторяющийся ключ в объект "dbo.#tt2".
11 май 11, 23:10    [10638724]     Ответить | Цитировать Сообщить модератору
 Re: Пересечение множеств.  [new]
iljy
Member

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

это значит у вас в данных множества несколькими цепочками независимыми могут пересекаться. Уберите оттуда ПК, он там по идее не особо нужен.
11 май 11, 23:25    [10638766]     Ответить | Цитировать Сообщить модератору
 Re: Пересечение множеств.  [new]
b9594
Member

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

Можете выложить дамп своих данных

Данные можно сгенерировать. Мои значения находятся примерно в этих диапазонах:
CREATE TABLE #tbl(sn int PRIMARY KEY IDENTITY(1,1) NOT NULL, id1 int, id2 int)
CREATE INDEX ix_id on #tbl(id1, id2)
DECLARE @j INT = 0
DECLARE @i INT
DECLARE @n INT
DECLARE @id1 INT
WHILE (@j < 170000)
BEGIN
	SET @id1 = FLOOR(RAND()*10000)
	SET @n = FLOOR(RAND()*10)
	SET @i = 0
	WHILE (@i < @n)
	BEGIN
		INSERT INTO #tbl(id1, id2) VALUES (@id1, FLOOR(RAND()*2000))
		SET @i = @i + 1
	END
	SET @j = @j + @i
END
--

--
DROP TABLE #tbl

Спасибо.
11 май 11, 23:38    [10638800]     Ответить | Цитировать Сообщить модератору
 Re: Пересечение множеств.  [new]
iljy
Member

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

на таких данных на моем рабочем компе (4 головы, 4 гига памяти) для к=2 выполнилось за 24 секунды, получилось порядка 130т множеств, для к=3 выполнилось за 7 секунд, получилось 512, для к=4-5 множеств не получилось ни одного. Не знаю, можно ли еще что-нибудь оптимизить, а главное - нужно ли.
12 май 11, 00:29    [10638954]     Ответить | Цитировать Сообщить модератору
 Re: Пересечение множеств.  [new]
b9594
Member

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

Не нужно. Благодарю.
12 май 11, 00:33    [10638971]     Ответить | Цитировать Сообщить модератору
Все форумы / Microsoft SQL Server Ответить