Я работаю в SQL Server 2008 R2 с упорядоченным по приоритету набором контента, который должен быть назначен набору сегментов для достижения заданного значения контента. Каждый элемент в списке содержимого связан с узлами в иерархии рваного дерева (сегменты). Каждое ведро имеет присвоенное ему значение и может содержать фиксированное количество контента.
Я пытаюсь распределить контент в порядке приоритета по тем корзинам, к которым они относятся (или любому родителю / дедушке вверх по дереву из связанного контента). Я должен начать с самого высокого значения сегмента (с пустыми пробелами) и останавливаться только тогда, когда значения сегмента соответствуют или превышают мое значение содержимого.
Надеюсь, мой грубый пример поможет. Предполагая, что B - это корзины, каждый из которых может содержать 2 фрагмента контента, а C - контент. Числа в скобках - это значение сегмента и требуемое значение содержимого.
C1 приведет к тому, что B1 будет выделено (самое высокое значение в дереве B1) и B4, что даст ему общее значение 7. У обоих B1 и B4 теперь остается только один слот.
C2 будет выделен B1 и B5, не оставляя слотов в B1 и 1 слот в B2.
C3 не сможет использовать B1, так как нет доступных слотов, поэтому в результате B2, B5 и B9 не оставят слотов в B5 и одного слота в B2 / B5.
И так далее ...
Я могу видеть, как этого добиться итеративно, создав список всех сегментов и их взаимосвязь со всеми сегментами дочерних / больших дочерних элементов. Зацикливание содержимого по одному, назначение его сегментов и уменьшение оставшегося пространства сегментов. Причина, по которой я чувствую, что это должен быть цикл, связана с тем, что в каждом сегменте остается неизвестное количество пробелов на основе обработки всего содержимого с более высоким приоритетом.
Но зацикливание контента по одному кажется по сути неправильным, и должен быть более эффективный способ решения этой проблемы распределения - в идеале за один проход ...
Пример кода SQL Server (для соответствия приведенной выше диаграмме)
--core table/fields
CREATE TABLE Bucket
(
Id int,
Name varchar(3),
BucketValue int,
SlotRemaining int --only required for my solution to hold number of slots left to fill
)
CREATE TABLE BucketParent
(
ChildBucketId int,
ParentBucketId int
)
CREATE TABLE Content
(
Id int,
Name varchar(3),
ContentValue int,
AllocationState int, --only required for my solution to identify content that still needs processing
--1=unprocessed, 2=Complete
Priority int --order to work through content 1=most imnportant
)
CREATE TABLE ContentBucket
(
ContentId int,
BucketId int
)
Go
CREATE TABLE ContentPriorityBucket -- table to record my allocation of content to the most valuable bucket
(
ContentId int,
BucketId int
)
Go
--test data to match example (wish id made it smaller now :)
INSERT INTO Bucket Values (1,'B1', 4, null)
INSERT INTO Bucket Values (2,'B2', 5, null)
INSERT INTO Bucket Values (3,'B3', 4, null)
INSERT INTO Bucket Values (4,'B4', 3, null)
INSERT INTO Bucket Values (5,'B5', 3, null)
INSERT INTO Bucket Values (6,'B6', 3, null)
INSERT INTO Bucket Values (7,'B7', 4, null)
INSERT INTO Bucket Values (8,'B8', 2, null)
INSERT INTO Bucket Values (9,'B9', 1, null)
INSERT INTO Bucket Values (10,'B10', 2, null)
INSERT INTO Bucket Values (11,'B11', 1, null)
INSERT INTO BucketParent Values (8, 4)
INSERT INTO BucketParent Values (4, 1)
INSERT INTO BucketParent Values (9, 5)
INSERT INTO BucketParent Values (5, 1)
INSERT INTO BucketParent Values (5, 2)
INSERT INTO BucketParent Values (10, 5)
INSERT INTO BucketParent Values (10, 6)
INSERT INTO BucketParent Values (6, 2)
INSERT INTO BucketParent Values (6, 3)
INSERT INTO BucketParent Values (11, 6)
INSERT INTO BucketParent Values (11, 7)
INSERT INTO BucketParent Values (7, 3)
INSERT INTO Content Values (1,'C1', 5, null, 1)
INSERT INTO Content Values (2,'C2', 8, null, 2)
INSERT INTO Content Values (3,'C3', 9, null, 3)
INSERT INTO Content Values (4,'C4', 10, null, 4)
INSERT INTO ContentBucket Values (1,8)
INSERT INTO ContentBucket Values (1,4)
INSERT INTO ContentBucket Values (2,9)
INSERT INTO ContentBucket Values (3,9)
INSERT INTO ContentBucket Values (4,10)
INSERT INTO ContentBucket Values (4,7)
GO
--Iterative solution that I am trying to improve on
UPDATE Bucket
SET SlotRemaining = 2 --clear previous run and allocate maximum bucket size
UPDATE Content
SET AllocationState = 1 --set state to unprocessed
--Clear last run
TRUNCATE Table ContentPriorityBucket
GO
DECLARE @ContentToProcess int = 0
DECLARE @CurrentContent int
DECLARE @CurrentContentValue int
SELECT @ContentToProcess = COUNT(id) FROM Content WHERE AllocationState =1
WHILE (@ContentToProcess > 0)
BEGIN
-- get next content to process
SELECT Top(1) @CurrentContent = ID,
@CurrentContentValue = ContentValue
FROM Content
WHERE AllocationState =1
ORDER BY Priority;
WITH BucketList (Id, BucketValue, SlotRemaining)
as
(
-- list buckets related to content
SELECT b.Id
,b.BucketValue
,b.SlotRemaining
FROM ContentBucket cb
INNER JOIN Bucket b on cb.BucketId = b.Id
WHERE cb.ContentId = @CurrentContent
-- need to pull back all buckets (even those that are full as they may have empty parents)
UNION ALL
SELECT b.Id
,b.BucketValue
,b.SlotRemaining
FROM BucketList bl
INNER JOIN BucketParent bp on bl.Id = bp.ChildBucketId
INNER JOIN Bucket b on bp.ParentBucketId = b.Id
),
DistinctBucketList (Id, BucketValue, SlotRemaining)
as
(
--dedupe buckets
SELECT distinct Id
, BucketValue
, SlotRemaining
FROM BucketList
),
BucketListOrdered (Id, BucketValue, RowOrder)
as
(
--order buckets
SELECT Id
,BucketValue
,ROW_NUMBER() OVER (ORDER BY BucketValue desc, Id)-- added id to get consistant result if two buckets have same value
FROM DistinctBucketList
WHERE SlotRemaining >0
),
CulmativeBucketListWithinRequiredValue (Id, RowOrder, CulmativeBucketValue, RequiredBucket)
as
(
-- this will mark all buckets up to the bucket value, but will be 1 bucket short
SELECT blo.Id
,blo.RowOrder
,SUM(blc.BucketValue) CulmativeBucketValue
,CASE
WHEN SUM(blc.BucketValue) <=@CurrentContentValue THEN 1
ELSE 0
END RequiredBucket
FROM BucketListOrdered blo
LEFT JOIN BucketListOrdered blc ON blc.RowOrder <= blo.RowOrder
GROUP BY blo.Id, blo.RowOrder
)
-- this will identify all buckets required to top content value
INSERT INTO ContentPriorityBucket
SELECT @CurrentContent
,b.Id
FROM CulmativeBucketListWithinRequiredValue b
WHERE b.RowOrder <= (SELECT Max(RowOrder) + 1 FROM CulmativeBucketListWithinRequiredValue WHERE RequiredBucket =1)
--reduce all used bucket sizes by 1 (could alternatively determine this from ContentPriorityBucket)
UPDATE Bucket
SET SlotRemaining = SlotRemaining -1
WHERE id in (SELECT BucketId FROM ContentPriorityBucket WHERE ContentId = @CurrentContent)
-- update processed bucket
UPDATE Content
SET AllocationState = 2
WHERE @CurrentContent = Id
SELECT @ContentToProcess = COUNT(id) FROM Content WHERE AllocationState =1
END
SELECT ContentId, BucketId FROM ContentPriorityBucket
/*
DROP TABLE Bucket
DROP TABLE BucketParent
DROP TABLE Content
DROP TABLE ContentBucket
DROP TABLE ContentPriorityBucket
*/