Использование CTE-рекурсии для STACKING разбиваемых элементов в контейнеры - PullRequest
Новая
       41

Использование CTE-рекурсии для STACKING разбиваемых элементов в контейнеры

0 голосов
/ 09 июля 2019

Я создал минималистичные выборочные данные с целью изучения и представления этой интересной задачи. Ниже приведен код для настройки тестовых таблиц. Задача состоит в том, чтобы распределить элементы в заранее заданные корзины , а:

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

Upper chart shows stacked items, bottom shows matching pre-set bins Верхняя диаграмма показывает сложенные элементы, нижняя показывает совпадающие заданные ячейки. Результаты взяты из раствора с КУРСОРАМИ

Bellow - это законченное рабочее решение, использующее CURSORS, но этот вопрос касается использования CTE recursion для решения этой задачи. Очевидно, я изучаю CTE и ищу прирост производительности, который в моих предыдущих приложениях рекурсии CTE был очень значительным.

Вот неправильный код CTE, который я создал, это не большая помощь, я думаю. Это далеко от включения всей необходимой логики, такой как разделение элемента или перемещение в предыдущую корзину с доступной емкостью.
Я допускаю, что имею небольшой опыт работы с рекурсией CTE и изо всех сил пытаюсь использовать ее в этой задаче. 

DECLARE @MinDate Date
SELECT @MinDate = MIN(BinDateTime) FROM Test_Bins;

WITH CTEfill (DueBinID,BinDate,ItemID,Duration) AS (
    -- Anchor
    SELECT --TI.DueBinID, 
           -- (SELECT DATEADD(MINUTE,TI.Duration,MAX(BI.BinDateTime)) FROM Test_BinItems as BI WHERE BI.BinID = TI.DueBinID) as DueBinID, 
           (SELECT MAX(TB1.BinID) FROM Test_Bins as TB1 WHERE TB1.BinID <= TI.DueBinID AND TB1.BinCapacity - (SELECT SUM(TBI.Duration) FROM Test_BinItems as TBI WHERE TBI.BinID = TB1.BinID) > 0) as DueBinID,
           (SELECT MAX(TB1.BinDateTime) FROM Test_Bins as TB1 WHERE TB1.BinID <= TI.DueBinID AND TB1.BinCapacity - (SELECT SUM(TBI.Duration) FROM Test_BinItems as TBI WHERE TBI.BinID = TB1.BinID) > 0) as BinDate,
           TI.ItemID,
           CASE -- Get remaining (usually whole) item duration if enough capacity in selected bin is available, otherwise space left in selected bin
                WHEN TI.Duration - (SELECT SUM(BI1.Duration) FROM Test_BinItems as BI1)
                   < (SELECT BinCapacity FROM Test_Bins as BI2 WHERE BI2.BinID = TI.DueBinID) - (SELECT SUM(Duration) FROM Test_Items as TI2 WHERE TI2.DueBinID = TI.DueBinID) 
                THEN TI.Duration - (SELECT SUM(BI1.Duration) FROM Test_BinItems as BI1)
                ELSE (SELECT BinCapacity FROM Test_Bins as BI2 WHERE BI2.BinID = TI.DueBinID) - (SELECT SUM(Duration) FROM Test_Items as TI2 WHERE TI2.DueBinID = TI.DueBinID)
           END as Duration
    FROM Test_Items as TI

    UNION ALL   -- Add recursion to the initial elements

    SELECT DueBinID - 1, 
           (SELECT BinDate FROM Test_Bins as TB3 WHERE TB3.BinID = CTE.DueBinID - 1), 
           CTE.ItemID,
    --     CASE -- Get remaining (usually whole) item duration if enough capacity in selected bin is available, otherwise space left in selected bin
    --          WHEN (SELECT Duration FROM Test_Items as TI3 WHERE TI3.ItemID = CTE.ItemID) - (SELECT SUM(BI1.Duration) FROM Test_BinItems as BI1)
    --             < (SELECT BinCapacity FROM Test_Bins as BI2 WHERE BI2.BinID = CTE.DueBinID - 1) - (SELECT SUM(Duration) FROM Test_Items as TI2 WHERE TI2.DueBinID = CTE.DueBinID - 1) 
    --          THEN (SELECT Duration FROM Test_Items as TI3 WHERE TI3.ItemID = CTE.ItemID) - (SELECT SUM(BI1.Duration) FROM Test_BinItems as BI1)
    --          ELSE (SELECT BinCapacity FROM Test_Bins as BI2 WHERE BI2.BinID = CTE.DueBinID - 1) - (SELECT SUM(Duration) FROM Test_Items as TI2 WHERE TI2.DueBinID = CTE.DueBinID - 1)
    --     END as Duration
           CTE.Duration
    FROM CTEfill as CTE
    WHERE BinDate > @MinDate AND DueBinID > 0 -- AND Duration > 0           
)

INSERT INTO [dbo].[Test_BinItems]  -- create new item assignment to bin
            ([BinID]
            ,[BinDateTime]
            ,[ItemID]
            ,[Duration])
SELECT DueBinID, BinDate, ItemID, Duration FROM CTEfill;

ОБРАЗЕЦ ДАННЫХ 

CREATE TABLE Test_Bins(
    BinID INT,
    BinDateTime DateTime, 
    BinCapacity INT
)

-- Sample bins
INSERT INTO Test_Bins(BinID,BinDateTime,BinCapacity) VALUES (1,'2001-01-01 00:00', 9999);    -- **overflow** bin 
INSERT INTO Test_Bins(BinID,BinDateTime,BinCapacity) VALUES (2,'2019-07-15 06:45', 270);     -- new pre-set bin
INSERT INTO Test_Bins(BinID,BinDateTime,BinCapacity) VALUES (3,'2019-07-16 10:00', 540);     -- new pre-set bin
INSERT INTO Test_Bins(BinID,BinDateTime,BinCapacity) VALUES (4,'2019-07-17 00:30', 120);     -- new pre-set bin
INSERT INTO Test_Bins(BinID,BinDateTime,BinCapacity) VALUES (5,'2019-07-19 06:00', 480);     -- new pre-set bin
INSERT INTO Test_Bins(BinID,BinDateTime,BinCapacity) VALUES (6,'2019-07-22 07:15', 270);     -- new pre-set bin


CREATE TABLE Test_Items(
    DueBinID INT,
    ItemID INT,
    DueDate DateTime, 
    Duration INT
);

-- Sample items
INSERT INTO Test_Items(DueBinID,ItemID,DueDate,Duration) VALUES (5,418050,'2019-07-21',23); 
INSERT INTO Test_Items(DueBinID,ItemID,DueDate,Duration) VALUES (5,418053,'2019-07-19',183); 
INSERT INTO Test_Items(DueBinID,ItemID,DueDate,Duration) VALUES (5,418066,'2019-07-19',56); 
INSERT INTO Test_Items(DueBinID,ItemID,DueDate,Duration) VALUES (5,418077,'2019-07-19',32); 
INSERT INTO Test_Items(DueBinID,ItemID,DueDate,Duration) VALUES (5,418087,'2019-07-19',80); 
INSERT INTO Test_Items(DueBinID,ItemID,DueDate,Duration) VALUES (5,418091,'2019-07-19',38); 
INSERT INTO Test_Items(DueBinID,ItemID,DueDate,Duration) VALUES (5,418101,'2019-07-19',101); 
INSERT INTO Test_Items(DueBinID,ItemID,DueDate,Duration) VALUES (4,418113,'2019-07-18',125); 
INSERT INTO Test_Items(DueBinID,ItemID,DueDate,Duration) VALUES (4,418116,'2019-07-18',12); 
INSERT INTO Test_Items(DueBinID,ItemID,DueDate,Duration) VALUES (4,418124,'2019-07-18',6); 
INSERT INTO Test_Items(DueBinID,ItemID,DueDate,Duration) VALUES (4,418131,'2019-07-18',48); 
INSERT INTO Test_Items(DueBinID,ItemID,DueDate,Duration) VALUES (4,418134,'2019-07-18',70); 
INSERT INTO Test_Items(DueBinID,ItemID,DueDate,Duration) VALUES (4,418139,'2019-07-17',20); 
INSERT INTO Test_Items(DueBinID,ItemID,DueDate,Duration) VALUES (4,418156,'2019-07-17',80); 
INSERT INTO Test_Items(DueBinID,ItemID,DueDate,Duration) VALUES (4,418158,'2019-07-17',5); 
INSERT INTO Test_Items(DueBinID,ItemID,DueDate,Duration) VALUES (3,418168,'2019-07-16',18); 
INSERT INTO Test_Items(DueBinID,ItemID,DueDate,Duration) VALUES (3,418177,'2019-07-16',13); 
INSERT INTO Test_Items(DueBinID,ItemID,DueDate,Duration) VALUES (3,418179,'2019-07-16',45); 
INSERT INTO Test_Items(DueBinID,ItemID,DueDate,Duration) VALUES (3,418183,'2019-07-16',20); 
INSERT INTO Test_Items(DueBinID,ItemID,DueDate,Duration) VALUES (3,418294,'2019-07-16',20); 
INSERT INTO Test_Items(DueBinID,ItemID,DueDate,Duration) VALUES (2,418296,'2019-07-15',123); 
INSERT INTO Test_Items(DueBinID,ItemID,DueDate,Duration) VALUES (2,418298,'2019-07-15',242); 
INSERT INTO Test_Items(DueBinID,ItemID,DueDate,Duration) VALUES (2,418299,'2019-07-15',55); 
INSERT INTO Test_Items(DueBinID,ItemID,DueDate,Duration) VALUES (2,418301,'2019-07-15',74); 
INSERT INTO Test_Items(DueBinID,ItemID,DueDate,Duration) VALUES (1,418303,'2019-07-14',145); 
INSERT INTO Test_Items(DueBinID,ItemID,DueDate,Duration) VALUES (1,418305,'2019-07-13',88); 
INSERT INTO Test_Items(DueBinID,ItemID,DueDate,Duration) VALUES (1,418313,'2019-07-02',29); 
INSERT INTO Test_Items(DueBinID,ItemID,DueDate,Duration) VALUES (1,418414,'2019-06-21',17); 


CREATE TABLE Test_BinItems(
    BinID INT,
    BinDateTime DateTime, 
    ItemID INT,
    Duration INT
);

РЕШЕНИЕ С КУРСОРАМИ 

DELETE FROM Test_BinItems   -- clear the assignment table

DECLARE @i INT
DECLARE @iDuration INT
DECLARE @iBinCapacity INT
DECLARE @iDueDate DATE
DECLARE @iItemID INT
DECLARE @iBinID INT
DECLARE @BinAvailableCapacity INT
DECLARE ItemCursor CURSOR FOR SELECT TI.ItemID FROM Test_Items as TI ORDER BY DueDate DESC -- create cursor

SET @i = 0

OPEN ItemCursor
FETCH NEXT FROM ItemCursor INTO @iItemID   -- get first item

PRINT CONCAT('STARTING @iItemID=',@iItemID)

WHILE @@FETCH_STATUS = 0
BEGIN
    SELECT @iDuration = Duration,   -- start with whole duration of an item
           @iDueDate = DueDate,     -- set due date of iterated item
           @iBinID = DueBinID       -- set starting bin as the due bin of iterated item
    FROM Test_Items WHERE ItemID = @iItemID   -- set variables for iterated item
    PRINT CONCAT('iITEM:   @iDuration=',@iDuration,'    @iDueDate=',@iDueDate,'    @iBinID=',@iBinID)

    WHILE @iDuration > 0  AND @i < 500           -- until we allocate whole duration of iterated item to bins (with safety limit of 500 iterations)
    BEGIN
        SET @BinAvailableCapacity = 
              (SELECT BinCapacity FROM Test_Bins WHERE BinID = @iBinID)                   -- whole bin capcacity
            - ISNULL((SELECT SUM(Duration) FROM Test_BinItems WHERE BinID = @iBinID),0)   -- minus already filled capacity
        PRINT CONCAT('INSETING @BinAvailableCapacity=',@BinAvailableCapacity)
        IF @BinAvailableCapacity > 0 -- if there is capacity to be used
        BEGIN
            -- Used duration in this iteration
            DECLARE @iUsedDuration INT
            IF @iDuration < @BinAvailableCapacity  -- if the item fits remaining bin capacity
            BEGIN 
                SET @iUsedDuration = @iDuration
                SET @iDuration = 0
            END
            ELSE  -- if the item does not fit remaining bin capacity, put only part of the item in
            BEGIN
                SET @iUsedDuration = @BinAvailableCapacity
                SET @iDuration = @iDuration - @iUsedDuration
            END

            -- Item date-time assigned in the bin
            DECLARE @iItemBinDateTime DateTime        -- stack date-TIME - where the item will start
            DECLARE @LastBinItemDTInBin DateTime      -- where the last inserted item starts
            SET @LastBinItemDTInBin = (SELECT MAX(BinDateTime) FROM Test_BinItems WHERE BinID = @iBinID)
            SET @iItemBinDateTime = ISNULL(DATEADD(MINUTE,(SELECT Duration FROM Test_BinItems WHERE BinDateTime = @LastBinItemDTInBin),@LastBinItemDTInBin),(SELECT BinDateTime FROM Test_Bins WHERE BinID = @iBinID))

            INSERT INTO [dbo].[Test_BinItems]  -- create new item assignment to bin
                       ([BinID]
                       ,[BinDateTime]
                       ,[ItemID]
                       ,[Duration])
                 VALUES
                       (@iBinID
                       ,@iItemBinDateTime
                       ,@iItemID
                       ,@iUsedDuration)
            PRINT CONCAT('INSETING @iBinID=',@iBinID,'    @iItemBinDateTime=',@iItemBinDateTime,'    @iItemID=',@iItemID,'    @iUsedDuration=',@iUsedDuration)

        END
        ELSE    -- if there's no capacity to be used, move to previous bin
        BEGIN 
            SET @iBinID = @iBinID - 1 
        END
    SET @i = @i + 1
    END

FETCH NEXT FROM ItemCursor INTO @iItemID
END

CLOSE ItemCursor
DEALLOCATE ItemCursor
...