Разделение списка чисел на приблизительно равные суммы

Question

Я знаю, что, вероятно, не существует "идеального" решения моего вопроса (это звучит как изменение рюкзака или проблемы с упаковкой в ​​мусорное ведро), но вот мой сценарий:

Я хочуразделить список таблиц базы данных SQL на n (скажем, 7) стопок примерно одинакового размера (чтобы я мог распределить некоторые задачи обслуживания примерно одинаково по всей неделе).

Допустим, у меня есть 100 таблиц (это может быть выше или ниже, но, вероятно, не выше 5000), в диапазоне от 1 до 10 000 000 (большие таблицы, конечно, встречаются гораздо реже).

Моя первоначальная идея состояла в том, чтобы отсортировать таблицы в алфавитном порядке (псевдослучайно), а затем перейти от начала к началу и перейти к следующей группе, когда сумма превысит сумму (размер) / 7.Для некоторых баз данных это, вероятно, будет работать нормально, но если две гигантские таблицы расположены рядом друг с другом, то это создает очень неравные группы.(Это не так уж маловероятно, как кажется, рассмотрим две огромные таблицы: Account_History и Account_History_Archive).

Существуют ли общепринятые методы для этого, которые дают "хорошие" результаты с различными исходными данными?Я бы предпочел более простую технику, чем более точную группировку (если обслуживание выполняется в некоторые дни несколько дольше, чем в другие, это не , что важно).

Answer 1

Как насчет сортировки таблиц по размеру, а затем для каждой таблицы поместить их в день, в котором в настоящее время содержится наименьшее общее количество строк?Это означает, что самые большие 7 таблиц будут сначала распределяться по дням.Затем восьмой по величине будет идти с наименьшим из первых 7 и т. Д. Вы продолжите заполнять день наименьшим количеством запланированной работы.

Где, наконец, окончательно заканчиваются маленькие справочные таблицыне имеет большого значения.

Вы можете придумать сценарии, где это не хорошо, но я ожидаю, что это будет работать на практике, не будучи слишком сложным.

Answer 2

Просто для справки, так я и поступил.Я хотел положить «Ведра» в постоянную таблицу и только «пересчитывать» их каждые 2 недели.В противном случае я боялся, что, если бы я вычислял эти сегменты каждый день, таблица могла бы перейти от одного сегмента к другому.Но я хотел пересчитать время от времени для модификации схемы и DDL.Вот этот фрагмент.

-------------------------------------------------------------------------------------
--Get the total table size (by rows)
-------------------------------------------------------------------------------------


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

SELECT 
    TableName = t.NAME,
    Schem = s.name,
    Pages = sum(a.total_pages),
    Grp = row_number() over (order by sum(a.total_pages) desc)
INTO #Space
FROM 
    sys.tables t
INNER JOIN      
    sys.indexes i ON t.OBJECT_ID = i.object_id
INNER JOIN 
    sys.partitions p ON i.object_id = p.OBJECT_ID AND i.index_id = p.index_id
INNER JOIN 
    sys.allocation_units a ON p.partition_id = a.container_id
LEFT OUTER JOIN 
    sys.schemas s ON t.schema_id = s.schema_id
WHERE 
    t.NAME NOT LIKE 'dt%' 
    AND t.is_ms_shipped = 0
    AND i.OBJECT_ID > 255 
GROUP BY 
    t.Name, s.name


-------------------------------------------------------------------------------------
--split the tables into 7 buckets by:
    --updating the Grp to the Grp with the lowest cumulative sum of all members by
    --ordering by the current cumulative sum of all members
-------------------------------------------------------------------------------------

declare @ct int = 8


while @ct <= (select max(Grp) from #Space)
begin

    update S
    set Grp = (select top 1 Grp from #Space where Grp < 8 order by sum(Pages) over (partition by Grp) asc)
    from #Space S
    where S.Grp = @ct

    set @ct = @ct + 1

end


insert into AdminTools..TableSpace (TableName
                                    ,Schem
                                    ,Pages
                                    ,Grp
                                    ,GrpPages
                                    ,LoadDate)
select 
    TableName
    ,Schem
    ,Pages
    ,Grp
    ,GrpPages = sum(Pages) over (partition by Grp)
    ,LoadDate = getdate()
from #Space
end

Answer 3

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