樂在 Coding 愛上 MVC - twMVC

最新回應

案列分享:T-SQL 分配計算

有個滿常見的應用,例如連鎖店的存貨撥補系統,每家分店的需求量彙總後報請總公司配給,但可能旺季時總公司存量不足以滿足所有分店的需求,此時應該如何分配?如果希望利用 T-SQL 在資料庫裡計算出結果,你會如何求解呢?

小舖上有這樣的提問,個人覺得頗有挑戰性,因此花了點時間研究,利用本文做個記錄並請大家指點,提問內容整理如下:

## 問題

假設有 3 家店的訂購資料如下表一,可用庫存數只有 20 個,分配時以訂購量大者優先逐次加一的方式,希望得到的結果如表二,隱含條件是配給量不應超出訂購量

assignment

問:如何寫出「以訂購數分配庫存數」的 T-SQL?


我們先切換到暫存資料庫準備樣本資料供測試之用,並將問題稍做延伸,加入了「產品」資料讓案例更加接近真實世界:
USE tempdb;
GO

-- 分店訂購資料
CREATE TABLE StoreOrders 
(
	Store NVARCHAR(1) NOT NULL,
	Product NVARCHAR(10) NOT NULL,
	OrderQuantity INT
)

INSERT INTO StoreOrders
SELECT 'A', 'Apple', 7
UNION ALL SELECT 'B', 'Apple', 10
UNION ALL SELECT 'C', 'Apple', 8
UNION ALL SELECT 'A', 'Lemon', 12
UNION ALL SELECT 'B', 'Lemon', 10
UNION ALL SELECT 'C', 'Lemon', 24
UNION ALL SELECT 'A', 'Orange', 8
UNION ALL SELECT 'B', 'Orange', 32;
GO

-- 在庫商品存量
CREATE TABLE Products
(
	Product NVARCHAR(10) NOT NULL,
	QuantityInStock INT NOT NULL
)

INSERT INTO Products
SELECT 'Apple', 20
UNION ALL SELECT 'Lemon', 38
UNION ALL SELECT 'Orange', 32
GO

最直觀的做法是利用迴圈逐一分配,已達到需求者將略過,否則繼續配給,直到所有需求都已滿足或可用存量到 0 為止,這對具備 T-SQL 開發能力的人應該不難寫出:
-- ================
-- ## 迴圈計算法 ## 
-- ================
USE tempdb;
GO

-- 依訂購量遞減排序
SELECT 
	[No] = ROW_NUMBER() OVER(PARTITION BY Product ORDER BY OrderQuantity DESC), 
	Store, Product, Orderquantity, 
	0 AS RealQuantity, 
	0 AS [Skip] 
INTO #tmp 
FROM StoreOrders;

DECLARE @Product NVARCHAR(100), @CurProduct NVARCHAR(10);

-- 取出所有產品
SET @Product = ''
SELECT @Product = @Product + Product + ',' FROM Products;

WHILE (LEN(@Product) > 0)
BEGIN
	-- 擷取單一商品
	SET @CurProduct = SUBSTRING(@Product, 1, CHARINDEX(',', @Product, 1) - 1);
	
	DECLARE 
		@QuantityInStock INT,	-- 在庫數量
		@No INT					-- 分配順位

	SELECT @QuantityInStock = QuantityInStock FROM Products WHERE (Product = @CurProduct);
	SET @No = 0;

	WHILE (@QuantityInStock > 0)
	BEGIN
		SET @No = @No + 1;
		
		-- 項次大於最高項則重設為 1
		IF(@No > (SELECT MAX([No]) FROM #tmp WHERE (Product = @CurProduct))) SET @No = 1;
		
		IF EXISTS(SELECT 1 FROM #tmp WHERE ([No] = @No) AND (Product = @CurProduct) AND (RealQuantity < OrderQuantity))
		BEGIN
			-- 配額小於訂購量逐次加 1
			UPDATE #tmp SET RealQuantity = RealQuantity + 1 WHERE ([No] = @No) AND (Product = @CurProduct) AND ([Skip] = 0);
			SET @QuantityInStock = @QuantityInStock - 1;
		END
		ELSE
			-- 配額已達需求則標記略過
			UPDATE #tmp SET [Skip] = 1 WHERE ([No] = @No) AND (Product = @CurProduct);
	End

	-- 剃除分配完成商品
	SET @Product = RIGHT(@Product, LEN(@Product) - CHARINDEX(',', @Product, 1));
END

SELECT Store, Product, OrderQuantity, RealQuantity
FROM #tmp
ORDER BY Product, Store;

DROP TABLE #tmp;
GO

喜歡用 Cursor 去做的人也可以自行嘗試看看,道理是一樣的,不過之前的案例曾經分享過 SQL Server 逐筆運算的效能不會很好,若能朝批次處理去設計較為理想,底下是改良的寫法:
-- ================
-- ## 遞迴式 CTE ## 
-- ================
USE tempdb;
GO

;WITH ext AS (
	SELECT so.Store, so.Product, so.OrderQuantity, 0 AS RealQuantity, p.QuantityInStock 
	FROM StoreOrders so INNER JOIN Products p ON so.Product = p.Product
	UNION ALL
	SELECT Store, Product, OrderQuantity, RealQuantity + 1, QuantityInStock 
	FROM ext
	WHERE (RealQuantity < OrderQuantity)
), tmp AS (
	SELECT Store, Product, OrderQuantity, RealQuantity,
		QuantityInStock = QuantityInStock - ROW_NUMBER() OVER (PARTITION BY Product ORDER BY RealQuantity, OrderQuantity DESC) 
	FROM ext
	WHERE (RealQuantity > 0)
)
SELECT Store, Product, OrderQuantity, RealQuantity = MAX(RealQuantity)
FROM tmp
WHERE (QuantityInStock >= 0)
GROUP BY Store, Product, OrderQuantity
ORDER BY Product, Store;
GO

程式碼相當精簡,精簡到給總務小姐看到可能誤以為寫程式很輕鬆,這就是遞迴 (Recursive) 的絕妙之處了,無怪乎「遞迴只應天上有,凡人該當用迴圈」這句話高居 Google 搜尋榜第八名!

recursive_google

要提醒的是遞迴式 CTE 有其限制,其預設最大遞迴數 MAXRECURISON 是 100,這是避免設計不良造成無窮迴圈的安全措施,以前例來說任一訂購量若大於 100,分配次數將超過 100 次,就會出現『最大遞迴 100 已在陳述式完成之前用盡』的錯誤,要解除可以考慮使用查詢提示指定 MAXRECURSION 的上限,這是一個介於 0 和 32,767 之間的值,0 代表不會套用任何限制,當然啦,放寬遞迴層級對於效能的負面影響一定是有的,所以應當審慎評估才是。

《2010-08-02 補充》

網友 Jed 回覆可以用加權的方式計算,也就是「比例分配原則」。其實一開始我的想法是認為比例分配與原本逐步分配其實是兩種不同的計算模式,該採哪一種原則也是青菜蘿蔔各有所好、見仁見智的問題,加上試了幾次比例分配計算一直沒有寫出滿意的 SQL 語法,原本想暫且擱下不提,沒想到很快就被發現避重就輕…。

好啦,還是出來面對一下,『比例分配原則』的作法即是將每個需求依據佔比乘以實際可用量,小數點之後則四捨五入到整位數,好處是可以將分配次數減至最低,但萬一產生了差額也是很頭痛,例如十塊錢三個人分,每人三塊之後剩一塊要給誰的問題…,還好依稀記得黑大發過一篇文:CODE - 分贓程式的寫法,可以順利弭平分贓不均的後遺症,底下則是改寫為 T-SQL 版的例子:
-- ================
-- ## 比例分配法 ## 
-- ================
USE tempdb;
GO

-- 依訂量排順位
SELECT 
	[No] = ROW_NUMBER() OVER(PARTITION BY Product ORDER BY OrderQuantity DESC), 
	Store, Product, Orderquantity, 
	0 AS RealQuantity 
INTO #tmp 
FROM StoreOrders;

DECLARE @Product NVARCHAR(100), @CurProduct NVARCHAR(10);

-- 取出所有產品
SET @Product = ''
SELECT @Product = @Product + Product + ',' FROM Products;

WHILE (LEN(@Product) > 0)
BEGIN
	-- 擷取單一商品
	SET @CurProduct = SUBSTRING(@Product, 1, CHARINDEX(',', @Product, 1) - 1);
	
	DECLARE 
		@QuantityInStock INT,	-- 在庫數量
		@TotalOrders DECIMAL,	-- 總訂購量
		@No INT					-- 分配順位

	SELECT @QuantityInStock = QuantityInStock FROM Products WHERE (Product = @CurProduct);
	SELECT @TotalOrders = SUM(OrderQuantity) FROM StoreOrders WHERE (Product = @CurProduct);
	SET @No = 0;
		
	WHILE (@QuantityInStock > 0)
	BEGIN
		SET @No = @No + 1;
		
		DECLARE @CurRealQuantity INT, @CurOrderQuantity INT;
		
		-- 按權重計算配額
		SELECT 
			@CurRealQuantity = @QuantityInStock * (OrderQuantity / @TotalOrders), 
			@CurOrderQuantity = OrderQuantity
		FROM #tmp WHERE (Product = @CurProduct) AND ([No] = @No);
		
		UPDATE #tmp SET RealQuantity = @CurRealQuantity WHERE (Product = @CurProduct) AND ([No] = @No);
		
		SET @QuantityInStock = @QuantityInStock - @CurRealQuantity;
		SET @TotalOrders = @TotalOrders - @CurOrderQuantity;
	END
	
	-- 剃除分配完成商品
	SET @Product = RIGHT(@Product, LEN(@Product) - CHARINDEX(',', @Product, 1));
END

SELECT Store, Product, OrderQuantity, RealQuantity
FROM #tmp
ORDER BY Product, Store;

DROP TABLE #tmp;
GO

暫時寫不出更滿意的語法,但還是提供出來給大家參考看看,如果你有更好的寫法別忘了留個言讓我知道。


參考資料


關連文章

利用 T-SQL 產生日期清單 (萬年曆) 並測試日期轉民國年函數對效能影響

自訂 SQL Server 日期轉民國年格式函數

案例分享:T-SQL 資料轉置(Transpose Data)

動態 SQL 威力展示 (3) - 進階議題

回應

  • # re: 案列分享:T-SQL 分配計算 by Jed

    可以用加權的方式去算喔,速度應該會更快一點

    2010/8/2 下午 01:48 | 回覆

  • # re: 案列分享:T-SQL 分配計算 by hunterpo

    to Jed :
    嗨,我猜你說的是按比例分配計算,已經在文末做了些補充。

    2010/8/2 下午 06:13 | 回覆

登入後使用進階評論

Please add 1 and 5 and type the answer here: