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

Question

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

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

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

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

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

Answer 1

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

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

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

Answer 2

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