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

Откуда: London
Сообщений: 22285
Такая вот задачка:

Есть таблица:

create table dbo.Allocations (ID int primary key, Amount money not null default 0.00)

Таблица содержит некоторое количество N (в общем случае переменное) записей:


ID            Amount 

1             289.78
2             45.07
3             234.09
...

Надо получить суммы всех возможных комбинаций значений Amount, в примерно таков вот виде:


1             289.78
2             45.07
3             234.09
1,2           334.85
1,3           523.87
2,3           279.16
1,2,3        568.94


В идеале хотелось бы это на SQL сделать для произвольного количества записей (записей в реальной жизни не больше 30)
6 июн 07, 19:36    [4239290]     Ответить | Цитировать Сообщить модератору
 Re: SQL и комбинаторика - ломаю голову  [new]
ChA
Member

Откуда: Москва
Сообщений: 10354
Alexander_Chepack
(записей в реальной жизни не больше 30)
Смутные воспоминания говорят мне о том, что раньше потухнет солнце, чем вы успеете перебрать все возможные комбинации для 30 элементов.
6 июн 07, 19:46    [4239311]     Ответить | Цитировать Сообщить модератору
 Re: SQL и комбинаторика - ломаю голову  [new]
Alexander_Chepack
Member

Откуда: London
Сообщений: 22285
ChA
Alexander_Chepack
(записей в реальной жизни не больше 30)
Смутные воспоминания говорят мне о том, что раньше потухнет солнце, чем вы успеете перебрать все возможные комбинации для 30 элементов.


Мда .. но мне-то надо :) Например, cross join'ы довольно быстро генерятся, а это ведь тоже комбинаторика...
6 июн 07, 19:49    [4239314]     Ответить | Цитировать Сообщить модератору
 Re: SQL и комбинаторика - ломаю голову  [new]
Alexander_Chepack
Member

Откуда: London
Сообщений: 22285
Собственно, количество подмножеств множества из N элементов (включая пустое подмножество), это 2 в степени N.

Т.е. для 20 записей имеем чуть больше миллиона вариантов :)
6 июн 07, 20:05    [4239349]     Ответить | Цитировать Сообщить модератору
 Re: SQL и комбинаторика - ломаю голову  [new]
Crimean
Member

Откуда:
Сообщений: 13143
да... для 30 как-то уж сильно тяжковато будет... ИМХО
беда в том, что sql не сильно для этого предусмотрен
выбрать просто числа просто
select id, amount from a
выбрать пары:
select a.id, b.id, a.amount + b.amount from a cross join b
выбрать тройки:
select a.id, b.id, c.id, a.amount + b.amount + c.amount from a cross join b cross join c
и т.д.
то есть, разумеется, сгенерить такой запрос можно...
как-то так, что ли:

set nocount on

declare @n int
select @n = 4

declare @i int
select @i = 0
while @i < @n begin
select @i = @i + 1

declare @fields varchar(8000)
select @fields = ''

declare @sum varchar(8000)
select @sum = ''

declare @tables varchar(8000)
select @tables = ''

declare @j int
select @j = 0
while @j < @i begin
select @j = @j + 1

-- print str( @i ) + str( @j )

select @fields = @fields + ' ' + 'ltrim(_str(_a' + ltrim( str( @j )) + '.Id_))'
select @sum = @sum + ' ' + 'a' + ltrim( str( @j )) + '.Amount'
select @tables = @tables + ' ' + 'mytable_a'+ ltrim( str( @j ))

end

select @fields	= replace( replace( ltrim( rtrim( @fields )), ' ', '+'',''+' ), '_', ' ' )
select @sum	= replace( replace( ltrim( rtrim( @sum )), ' ', '+' ), '_', ' ' )
select @tables	= replace( replace( ltrim( rtrim( @tables )), ' ', ',' ), '_', ' ' )

print 'select ' + @fields + ' as Fields,' + @sum + ' as Total'
print 'from ' + @tables

if @j <> @n begin
print ''
print 'union all'
print ''
end

end

но вот при @n = 30 его размерчик будет уже "того" - что-то около 25К

и даже для простого примера:

create table mytable( id int primary key , amount money )

insert into mytable select 0, 10
insert into mytable select 1, 11
insert into mytable select 2, 12
insert into mytable select 3, 13
insert into mytable select 4, 14
insert into mytable select 5, 15

такой запросец из 5 позиций выдает уже (9330 row(s) affected)...
что будет для 30 - страшно представить
но, тем не менее, запрос скомпилился и что-то начал отдавать, однако...
6 июн 07, 20:05    [4239350]     Ответить | Цитировать Сообщить модератору
 Re: SQL и комбинаторика - ломаю голову  [new]
ChA
Member

Откуда: Москва
Сообщений: 10354
Alexander_Chepack
Мда .. но мне-то надо :)
Уверены, что доживете ?
6 июн 07, 20:40    [4239443]     Ответить | Цитировать Сообщить модератору
 Re: SQL и комбинаторика - ломаю голову  [new]
iap
Member

Откуда: Москва
Сообщений: 44568
Crimean
что будет для 30 - страшно представить
Ничего страшного - всего лишь (1 073 741 824 row(s) affected)
6 июн 07, 20:50    [4239461]     Ответить | Цитировать Сообщить модератору
 Re: SQL и комбинаторика - ломаю голову  [new]
Crimean
Member

Откуда:
Сообщений: 13143
iap
Crimean
что будет для 30 - страшно представить
Ничего страшного - всего лишь (1 073 741 824 row(s) affected)


не, у меня терпения хватило только запрос написать :)
6 июн 07, 20:59    [4239479]     Ответить | Цитировать Сообщить модератору
 Re: SQL и комбинаторика - ломаю голову  [new]
LR
Member

Откуда: 8P8C
Сообщений: 2142
А у меня хватило терпения получить аж 1% результата :)
Ушло на это 15 мин., умножаем на 100, получаем 25 часов (для получения всего результата)...
declare @t table(ID int identity primary key, Amount money not null default 0.00)
insert @t(Amount)
select 10 union all
select 11 union all
select 12 union all
select 13 union all
select 14 union all
select 15 union all
select 16 union all
select 17 union all
select 18 union all
select 19 union all
select 20 union all
select 21 union all
select 22 union all
select 23 union all
select 24 union all
select 25 union all
select 26 union all
select 27 union all
select 28 union all
select 29 union all
select 30 union all
select 31 union all
select 32 union all
select 33 union all
select 34 union all
select 35 union all
select 36 union all
select 37 union all
select 38 union all
select 39

declare @res table (bits int, rsum money)
declare @i int; set @i=0

while @i<1000*10737 --42
begin
	insert @res
	select n.num, sum(Amount)
	from @t t 
	inner join (
		select number+@i as num from master..spt_values where type='P' and number between 1 and 1000
	 ) n on n.num & power(2,id-1)>0
	group by n.num

	set @i=@i+1000
end
select count(*) from @res
7 июн 07, 00:26    [4239855]     Ответить | Цитировать Сообщить модератору
 Re: SQL и комбинаторика - ломаю голову  [new]
VladRUS.ca
Member

Откуда: Toronto
Сообщений: 1172
Alexander_Chepack
Собственно, количество подмножеств множества из N элементов (включая пустое подмножество), это 2 в степени N.

Т.е. для 20 записей имеем чуть больше миллиона вариантов :)

Для 20 записей - 25 секунд:

use tempdb
go
set nocount on
go
if object_id('Allocations', 'U') > 0 drop table Allocations
go
create table Allocations (ID int primary key, Amount money not null default 0.00)
go
if object_id('Allocations2', 'U') > 0 drop table Allocations2
go
create table Allocations2(ID int identity primary key, IDs varchar(100), Amount money not null default 0.00 )
go

/*
truncate table Allocations
insert into Allocations(ID, Amount)
    select 1, 289.78 union all
    select 2, 45.07 union all
    select 3, 234.09
*/
truncate table Allocations
declare @i int 
set @i = 1
while @i <= 20
begin
    insert into Allocations(ID, Amount)
        select @i, rand()*100

    set @i = @i + 1    
end
go
-- select * from Allocations

truncate table Allocations2
declare @ID int, @IDs varchar(200), @Amount money

select @ID = ID, @Amount = Amount from Allocations where ID = (select min(ID) from Allocations) 
while @@rowcount = 1
begin

    insert into Allocations2(IDs, Amount) 
        select IDs, Amount
        from (       
            select 0 as ID, cast(@ID as varchar(10)) as IDs, @Amount as Amount
            union            
            select ID, IDs + ',' + cast(@ID as varchar(10)), Amount + @Amount
            from Allocations2 ) t
        order by ID
        
    select @ID = ID, @Amount = Amount from Allocations where ID = (select min(ID) from Allocations where ID > @ID) 
end
go

select sum(Amount) from Allocations
select top 100 * from Allocations2 order by ID desc
7 июн 07, 01:12    [4239890]     Ответить | Цитировать Сообщить модератору
 Re: SQL и комбинаторика - ломаю голову  [new]
Alexander_Chepack
Member

Откуда: London
Сообщений: 22285
VladRUS.ca
Для 20 записей - 25 секунд:


Класс! Красиво выглядит и работает. :)
7 июн 07, 15:47    [4243259]     Ответить | Цитировать Сообщить модератору
 Re: SQL и комбинаторика - ломаю голову  [new]
LR
Member

Откуда: 8P8C
Сообщений: 2142
Alexander_Chepack
VladRUS.ca
Для 20 записей - 25 секунд:


Класс! Красиво выглядит и работает. :)

а для 30 записей?
7 июн 07, 16:09    [4243443]     Ответить | Цитировать Сообщить модератору
 Re: SQL и комбинаторика - ломаю голову  [new]
VladRUS.ca
Member

Откуда: Toronto
Сообщений: 1172
LR
Alexander_Chepack
VladRUS.ca
Для 20 записей - 25 секунд:


Класс! Красиво выглядит и работает. :)

а для 30 записей?

Железо и время жалко...

Но это легко считается - при каждой новой итерации время будет удваиваться:
20 - 25 сек
21 - 50 сек
22 - 100 сек
23 - 200 сек
24 - 400 сек
25 - 800 сек
26 - 1600 сек
27 - 3200 сек
28 - 6400 сек
29 - 12800 сек
30 - 25600 сек или 25600 / 60 / 60 = 7 часов
7 июн 07, 17:28    [4244150]     Ответить | Цитировать Сообщить модератору
 Re: SQL и комбинаторика - ломаю голову  [new]
Tracer
Member

Откуда:
Сообщений: 728
Можно значительно ускорить алгоритм, если использовать результаты предыдущих вычислений.

уровень 1
7 июн 07, 17:44    [4244277]     Ответить | Цитировать Сообщить модератору
 Re: SQL и комбинаторика - ломаю голову  [new]
Tracer
Member

Откуда:
Сообщений: 728
1 289.78
2 45.07
3 234.09
7 июн 07, 17:45    [4244283]     Ответить | Цитировать Сообщить модератору
 Re: SQL и комбинаторика - ломаю голову  [new]
Tracer
Member

Откуда:
Сообщений: 728
Сорри, глючит. Итак Первый уровень 1 289.78
2 45.07
3 234.09. Второй = 1 + все столбцы, N = (N-1) + все столбцы. Время дожно быть или линейной или по логарифму.
7 июн 07, 17:48    [4244304]     Ответить | Цитировать Сообщить модератору
 Re: SQL и комбинаторика - ломаю голову  [new]
LR
Member

Откуда: 8P8C
Сообщений: 2142
VladRUS.ca
Железо и время жалко...
...
7 часов

Неплохо, вопреки прогнозам скептиков, "солнце не успеет потухнуть", и пользователь вполне сможет "дожить"
7 июн 07, 17:50    [4244324]     Ответить | Цитировать Сообщить модератору
 Re: SQL и комбинаторика - ломаю голову  [new]
Tracer
Member

Откуда:
Сообщений: 728
Хотя нет, неправ.
7 июн 07, 18:06    [4244434]     Ответить | Цитировать Сообщить модератору
 Re: SQL и комбинаторика - ломаю голову  [new]
ChA
Member

Откуда: Москва
Сообщений: 10354
LR
VladRUS.ca
Железо и время жалко...
...
7 часов

Неплохо, вопреки прогнозам скептиков, "солнце не успеет потухнуть", и пользователь вполне сможет "дожить"
Ну погорячился слегка, не обратил внимание на отсутствие перестановок. Но оптимистические оценки тоже, IMHO, являются умозрительными, пока никто полного эксперимента на 30 элементов не проделал. ;)
7 июн 07, 18:55    [4244683]     Ответить | Цитировать Сообщить модератору
 Re: SQL и комбинаторика - ломаю голову  [new]
Valer
Member

Откуда:
Сообщений: 277
Надо получить суммы всех возможных комбинаций значений Amount, в примерно таков вот виде:

А Зачем ? что дальше с ними делать собираетесь ?
8 июн 07, 14:56    [4248176]     Ответить | Цитировать Сообщить модератору
 Re: SQL и комбинаторика - ломаю голову  [new]
VladRUS.ca
Member

Откуда: Toronto
Сообщений: 1172
Вариант без лога - для 20 записей - 7 секунд:
use master;
go
if db_id (N'my_tempdb') is not null
drop database my_tempdb;
go
create database my_tempdb 
on 
(   name = my_tempdb_dat,
    filename = 'Z:\SQL\DATA\my_tempdbdat.mdf',
    size = 50 MB, -- 1 GB,
    maxsize = unlimited,
    filegrowth = 10 % 
)
go
alter database my_tempdb set recovery bulk_logged
go

use my_tempdb
go
set nocount on
go
if object_id('Allocations', 'U') > 0 drop table Allocations
go
create table Allocations (ID int primary key, Amount money not null default 0.00)
go

truncate table Allocations
declare @i int
set @i = 1
while @i <= 20
begin
    insert into Allocations(ID, Amount)
        select @i, rand()*100
    set @i = @i + 1    
end
go
-- select * from Allocations
 
declare @ID int, @Amount money, @StrAmount nvarchar(30), @sql nvarchar(1000) 

exec('if object_id(''Allocations_Result'', ''U'') > 0 drop table Allocations_Result')
exec('if object_id(''Allocations_0'', ''U'') > 0 drop table Allocations_0')
exec ('create table Allocations_0(IDs varchar(100), Amount money not null default 0.00 )')

select @ID = ID, @Amount = Amount, @StrAmount = ltrim(str(@Amount, 30, 4)) from Allocations where ID = (select min(ID) from Allocations) 
while @@rowcount = 1
begin

    set @sql = '
        select IDs, cast(Amount as money) as Amount into Allocations_' + cast(@ID as varchar(10)) + ' 
        from (
            select IDs, Amount as Amount from Allocations_' + cast(@ID-1 as varchar(10)) + ' 
            union all
            select ''' + cast(@ID as varchar(10)) + ''', ' + @StrAmount + ' 
            union all
            select IDs + '',' + cast(@ID as varchar(10)) + ''', Amount + ' + @StrAmount + ' from Allocations_' + cast(@ID-1 as varchar(10)) + ' ) t

        drop table Allocations_' + cast(@ID-1 as varchar(10))

    exec sp_executesql @sql
        
    select @ID = ID, @Amount = Amount, @StrAmount = ltrim(str(@Amount, 30, 4)) from Allocations where ID = (select min(ID) from Allocations where ID > @ID) 
end
set @sql = 'exec sp_rename ''Allocations_' + cast(@ID as varchar(10)) + ''', ''Allocations_Result'', ''OBJECT'''
exec sp_executesql @sql
go
-- 3 sec

create index index_Amount on Allocations_Result(Amount)
go
-- 4 sec

select sum(Amount) from Allocations
select top 100 * from Allocations_Result order by Amount desc

Что интересно на одной и той-же машине и том-же диске - 2005 работает ощутимо быстрее - для 23х записей:

SQL 2000 SP4: 49 сек + 55 сек (индексация )
SQL 2005 SP2: 29 сек + 47 сек (индексация )
8 июн 07, 23:38    [4250301]     Ответить | Цитировать Сообщить модератору
 Re: SQL и комбинаторика - ломаю голову  [new]
*
Guest
Наибыстрейший вариант
Для 23-х записей 48с на 1.6ГГц

if object_id('t') > 0 drop table t
create table t (n int primary key, v money)

declare @i int
set @i = 1
while @i <= 23
begin
    insert into t (n, v) select @i, rand()*100
    set @i = @i + 1
end


declare @t table (s money)

declare @c money
set @i = 1
while @i <= 23
begin
select @c = v from t where n = @i
insert into @t select (s + @c) from @t
insert into @t select @c
set @i = @i + 1
end

select count(*) from @t


8388607
9 июн 07, 10:38    [4251194]     Ответить | Цитировать Сообщить модератору
Между сообщениями интервал более 1 года.
 Re: SQL и комбинаторика - ломаю голову  [new]
Тимур З
Member

Откуда:
Сообщений: 56
if object_id('tempdb..#t') is not null
  drop table #t

if object_id('tempdb..#t2') is not null
  drop table #t2

create table #t( number int not null primary key, value money not null )

create table #t2( [group] int not null, number int not null, value money not null, primary key( [group], number ) )

declare @number table( number char(1) not null )

declare @rc int = 16

insert @number( number )
select 0 union all select 1 union all select 2 union all select 3 union all select 4 union all select 5 union all select 6 union all select 7 union all select 8 union all select 9

insert #t( number, value )
select number, 100.0 * rand()
  from  ( select cast( t1.number + t2.number as int ) as number 
            from @number t1, @number t2
        ) v
  where v.number > 0
    and v.number <= @rc

insert #t2( [group], number, value )
select n.[group], e.number, e.value
	from ( select cast( t1.number + t2.number + t3.number + t4.number + t5.number as int ) as [group] 
  from @number t1, @number t2, @number t3, @number t4, @number t5
  ) n
		join #t e
		on power( 2, e.number - 1 ) | n.[group] = n.[group]
	where n.[group] < power( 2, @rc )
    and n.[group] > 0

select 
  [group], 
  ( select cast( t2.number as varchar(10) ) + ';' as 'data()' 
      from #t2 t2 
      where t1.[group] = t2.[group] 
      for xml path('') 
  ) as numbers, 
  sum( value ) as value
  from #t2 t1
  group by [group]
  order by 1
29 апр 16, 12:37    [19121280]     Ответить | Цитировать Сообщить модератору
Все форумы / Microsoft SQL Server Ответить