SQL Serverでループせずに固定サイズのバケットにコンテンツを割り当てる

Question

コンテンツ指定値を達成するためにバケットセットに割り当てる必要がある優先順位の高いコンテンツセットでSQL Server 2008 R2を使用しています。コンテンツリストの各アイテムは、不揃いなツリー階層内のノード（バケット）に関連しています。各バケットには値が割り当てられており、一定量のコンテンツを保持できます。

私は、関連するバケット（または関連コンテンツのツリー上の親/祖父母）にコンテンツを優先順位で割り当てようとしています。私は最高のバケット値（空白を含む）から始め、バケット値が自分のコンテンツ値と一致するか超えている場合にのみ停止する必要があります。

うまくいけば、私の粗悪な例が助けになると思います。 Bがそれぞれ2つのコンテンツを保持することができるバケットであり、Cのコンテンツはコンテンツであると仮定します。カッコで囲まれた数字は、バケット値と必須のコンテンツ値です。

C1は現在だけ残りの1つのスロットを有する両B1にそれをB4を7の合計値を与えるためにB1（B1のツリー内の最高値）及びB4に割り当てられることになります。

C2にはB1とB5が割り当てられ、B1にはスロットは残さず、B2には1つのスロットしか残されません。

C3は利用可能なスロットがないためB1を使用できないため、B2、B5、B9はB5にはスロットを残さず、B2/B5には1つのスロットを残します。私はすべてのバケットのリストとすべての子/孫バケットとの関係を作成することによって、反復的にこれを実現する方法を見ることができます

のように...。コンテンツを一度に1つずつループし、そのバケットを割り当て、残りのバケットスペースを減らす。私はそれがループである必要があると感じる理由は、すべてのより高い優先度のコンテンツを処理することに基づいて各バケットに残っている未知のスペースの数に起因します。

しかし、時間本質的に間違って感じていると、この配分問題を解決するためのより効率的な方法が存在しなければならない時に、コンテンツ1をループする - 理想的な1回のパスで...

（上の図と一致するように）例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完全な問題であり、したがって、一般的には1回のパスでは解くことができません。この特定のビンパッキングは、オーダーされたパッキングなので異なる場合がありますが、問題の複雑さの問題は残ります。それは確かにO（1）ではないので、何があってもループが必要な場合があります。

これに対しては、1パスのループではない解決策が考えられます。セットベースのソリューションではない問題のように見えます。テーブル値のCLR関数を作成すると、各アイテムが収まるバケットを見つけることができます。さもなければ、ルーピングソリューションを維持することは問題ありません。