将内容分配到固定大小的存储桶而不在 SQL Server 中循环

Question

我正在 SQL Server 2008 R2 中使用一组按优先级排序的内容，这些内容必须分配给一组存储桶才能实现内容指定的值。内容列表中的每个项目都与参差不齐的树层次结构（桶）中的节点相关。每个存储桶都有一个分配给它的值，并且可以容纳固定数量的内容。

我正在尝试按优先级顺序将内容分配给与其相关的存储桶（或相关内容中树上的任何父/祖父母）。我必须从最高的存储桶值（带有空格）开始，并且仅当存储桶值匹配或超过我的内容值时才停止。

希望我的粗略例子能有所帮助。假设 B 是每个可以容纳 2 块内容的桶，C 是内容。括号中的数字是桶值和所需的内容值。

C1 将导致分配给 B1（B1 树中的最高值）和 B4 以给出总计值为 7。B1 和 B4 现在都只剩下一个插槽。

C2 将被分配到 B1 和 B5，而 B1 中没有空位，B2 中有 1 个空位。

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 
*/

Answer 1

关于这个问题有几点需要说明。

首先，广义装箱问题是一个 NP 完全问题，因此一般不能一次性解决。这种具体的装箱，由于是有序装箱，可能会有所不同，但问题的复杂性问题仍然存在；它肯定不是 O(1)，所以无论如何它可能需要一个循环。

1-pass 非循环解决方案似乎是不可能的；它看起来像是一个不适合基于集合的解决方案的问题。您可以创建一个表值 CLR 函数，它可以找到每个项目适合的存储桶。否则，保留循环解决方案就可以了。 （如果您发布代码，可能会更容易看出是否有改进的可能。）