選擇按值均勻分佈的分組數據
我想將表中的數據選擇為 4 組,該表中的值的總和盡可能均勻分佈。我確信我解釋得不夠清楚,所以我將嘗試舉一個例子。
這裡我使用 NTILE(4) 創建 4 個組:
SELECT Time, NTILE(4) OVER (ORDER BY Time DESC) AS N FROM TableX Time - N ------------- 10 - 1 9 - 2 8 - 3 7 - 4 6 - 1 5 - 2 4 - 3 3 - 4 2 - 1 1 - 2
在上述查詢和結果中,為簡潔起見,省略了其他列。
因此,您還可以看到這些組,如下所示:
1 2 3 4 --- --- --- --- 10 9 8 7 6 5 4 3 2 1 --- --- --- --- 18 15 12 10 Sum Totals of Time
請注意,使用 NTile 的時間總和在組之間並不是真正平衡的。例如,時間值的更好分佈是:
1 2 3 4 --- --- --- --- 10 9 8 7 3 5 4 6 1 2 --- --- --- --- 14 14 14 13 Sum Totals of Time
在這裡,時間總和更均勻地分佈在 4 個組中。
如何通過 TSQL 語句執行此操作?
此外,我不得不說我正在使用 SQL Server 2012。如果你有什麼可以幫助我的,請告訴我。
祝你今天愉快。
斯坦
這是一個算法的嘗試。它並不完美,取決於你想花多少時間來改進它,可能還有一些進一步的小收穫。
假設您有一個由四個隊列執行的任務表。您知道與執行每項任務相關的工作量,並且您希望所有四個隊列獲得幾乎相等的工作量,因此所有隊列將在大約同一時間完成。
首先,我會使用模數對任務進行分區,按大小排序,從小到大。
SELECT [time], ROW_NUMBER() OVER (ORDER BY [time])%4 AS grp, 0
按大小對
ROW_NUMBER()
每一行進行排序,然後分配一個從 1 開始的行號。此行號以grp
循環方式分配給一個“組”(列)。第一行是第 1 組,第二行是第 2 組,然後是第 3 組,第四行是第 0 組,依此類推。time ROW_NUMBER() grp ---- ------------ --- 1 1 1 10 2 2 12 3 3 15 4 0 19 5 1 22 6 2 ...
為了便於使用,我將
time
和grp
列儲存在一個名為@work
.現在,我們可以對這些數據進行一些計算:
WITH cte AS ( SELECT *, SUM([time]) OVER (PARTITION BY grp) -SUM([time]) OVER (PARTITION BY (SELECT NULL))/4 AS _grpoffset FROM @work) ...
該列
_grpoffset
是time
每個總數grp
與“理想”平均值的差異。如果time
所有任務的總數為 1000,並且有四個組,那麼理想情況下,每組應該有 250 個。如果一個組總共包含 268 個,則該組的_grpoffset=18
.這個想法是確定兩個最好的行,一個在“積極”組(工作太多),一個在“消極”組(工作太少)。如果我們可以在這兩行上交換組,我們可以減少
_grpoffset
兩個組的絕對值。例子:
time grp total _grpoffset ---- --- ----- ---------- 3 1 222 40 46 1 222 40 73 1 222 40 100 1 222 40 6 2 134 -48 52 2 134 -48 76 2 134 -48 11 3 163 -21 66 3 163 -21 86 3 163 -21 45 0 208 24 71 0 208 24 92 0 208 24 ---- =727
總共有 727 分,每個組的分數應該在 182 左右,這樣分佈才算完美。該組的得分與 182 之間的差異是我們在
_grpoffset
列中輸入的。正如您現在所看到的,在最好的情況下,我們應該將大約 40 點的行從第 1 組移動到第 2 組,將大約 24 點從第 3 組移動到第 0 組。
這是辨識這些候選行的程式碼:
SELECT TOP 1 pos._row AS _pos_row, pos.grp AS _pos_grp, neg._row AS _neg_row, neg.grp AS _neg_grp FROM cte AS pos INNER JOIN cte AS neg ON pos._grpoffset>0 AND neg._grpoffset<0 AND --- To prevent infinite recursion: pos.moved<4 AND neg.moved<4 WHERE --- must improve positive side's offset: ABS(pos._grpoffset-pos.[time]+neg.[time])<=pos._grpoffset AND --- must improve negative side's offset: ABS(neg._grpoffset-neg.[time]+pos.[time])<=ABS(neg._grpoffset) --- Largest changes first: ORDER BY ABS(pos.[time]-neg.[time]) DESC ) AS x ON w._row IN (x._pos_row, x._neg_row);
我正在自行加入我們之前創建的公用表表達式
cte
:一方面,帶有正數_grpoffset
的組,另一方面帶有負數的組。為了進一步過濾出哪些行應該相互匹配,正負側行的交換必須改進_grpoffset
,即使其更接近0。
TOP 1
並選擇“ORDER BY
最佳”匹配首先交換。現在,我們需要做的就是添加一個
UPDATE
, 並循環它,直到找不到更多優化。TL;DR - 這是查詢
這是完整的程式碼:
DECLARE @work TABLE ( _row int IDENTITY(1, 1) NOT NULL, [time] int NOT NULL, grp int NOT NULL, moved tinyint NOT NULL, PRIMARY KEY CLUSTERED ([time], _row) ); WITH cte AS ( SELECT 0 AS n, CAST(1+100*RAND(CHECKSUM(NEWID())) AS int) AS [time] UNION ALL SELECT n+1, CAST(1+100*RAND(CHECKSUM(NEWID())) AS int) AS [time] FROM cte WHERE n<100) INSERT INTO @work ([time], grp, moved) SELECT [time], ROW_NUMBER() OVER (ORDER BY [time])%4 AS grp, 0 FROM cte; WHILE (@@ROWCOUNT!=0) WITH cte AS ( SELECT *, SUM([time]) OVER (PARTITION BY grp) -SUM([time]) OVER (PARTITION BY (SELECT NULL))/4 AS _grpoffset FROM @work) UPDATE w SET w.grp=(CASE w._row WHEN x._pos_row THEN x._neg_grp ELSE x._pos_grp END), w.moved=w.moved+1 FROM @work AS w INNER JOIN ( SELECT TOP 1 pos._row AS _pos_row, pos.grp AS _pos_grp, neg._row AS _neg_row, neg.grp AS _neg_grp FROM cte AS pos INNER JOIN cte AS neg ON pos._grpoffset>0 AND neg._grpoffset<0 AND --- To prevent infinite recursion: pos.moved<4 AND neg.moved<4 WHERE --- must improve positive side's offset: ABS(pos._grpoffset-pos.[time]+neg.[time])<=pos._grpoffset AND --- must improve negative side's offset: ABS(neg._grpoffset-neg.[time]+pos.[time])<=ABS(neg._grpoffset) --- Largest changes first: ORDER BY ABS(pos.[time]-neg.[time]) DESC ) AS x ON w._row IN (x._pos_row, x._neg_row);