Affectation de contenu à des compartiments de taille fixe sans bouclage dans SQL Server

Question

Je travaille dans SQL Server 2008 R2 avec un ensemble de contenu ordonné par priorité qui doit être affecté à un ensemble de compartiments pour obtenir une valeur spécifiée par le contenu. Chaque élément de la liste de contenu est lié aux nœuds d'une hiérarchie arborescente déchiquetée (les compartiments). Chaque compartiment a une valeur qui lui est assignée et peut contenir une quantité fixe de contenu. J'essaye d'allouer le contenu dans l'ordre de priorité aux compartiments auxquels ils se rapportent (ou n'importe quel parent/grandparent en haut de l'arbre du contenu relatif). Je dois commencer avec la valeur de compartiment la plus élevée (avec des espaces vides) et arrêter uniquement lorsque les valeurs de compartiment correspondent ou dépassent la valeur de mon contenu.

J'espère que mon exemple brut aidera. En supposant que les B sont des seaux qui peuvent chacun contenir 2 morceaux de contenu et C sont contenu. Les nombres entre crochets sont la valeur du compartiment et la valeur du contenu requis.

C1 entraînerait étant alloué à B1 (valeur la plus élevée dans l'arbre de B1) et B4 pour lui donner une valeur totale de 7. Les deux B1 B4 maintenant une seule possède une fente restant. C212 se verrait attribuer B1 et B5 ne laissant aucun créneau dans B1 et 1 créneau dans B2.

C3 ne serait pas en mesure d'utiliser B1 car il n'y a pas de créneaux disponibles, de sorte que B2, B5 et B9 ne laisseraient aucun créneau dans B5 et un créneau dans B2/B5.

Et ainsi de suite ...

Je peux voir comment y parvenir itérativement en créant une liste de tous les seaux et leurs relations avec tous les enfants/grands seaux enfants. Boucler le contenu un à la fois, en affectant ses 'buckets' et en réduisant les espaces de baquets restants. La raison pour laquelle je pense qu'il doit s'agir d'une boucle est due au nombre inconnu d'espaces restants dans chaque compartiment basé sur le traitement de tout le contenu à priorité plus élevée.

Mais en boucle grâce à un contenu un à la fois se sent intrinsèquement mauvais et il doit y avoir un moyen plus efficace pour résoudre ce problème d'allocation - idéalement dans une passe ...

Exemple de code SQL Server (pour correspondre au schéma ci-dessus)

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

Il y a quelques points à faire à propos de ce problème. Tout d'abord, le regroupement de conteneurs généralisé est un problème NP-Complet, et ne peut donc pas être résolu en général en un seul passage. Ce bin-packing spécifique, puisqu'il s'agit d'un emballage ordonné, peut être différent, mais la question de la complexité du problème demeure; ce n'est certainement pas O (1), donc il peut avoir besoin d'une boucle quoi qu'il arrive.

Les solutions non-bouclées en une seule passe semblent ne pas être possibles; Cela ressemble à un problème qui n'est pas fait pour les solutions basées sur des ensembles. Vous pouvez créer une fonction CLR de type table, qui pourrait trouver le compartiment dans lequel chaque élément se situe. Sinon, garder la solution en boucle serait bien. (Si vous postez le code, il sera peut-être plus facile de voir s'il y a des améliorations possibles.)