Sql-Server

選擇按值均勻分佈的分組數據

  • October 1, 2021

我想將表中的數據選擇為 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
...

為了便於使用,我將timegrp列儲存在一個名為@work.

現在,我們可以對這些數據進行一些計算:

WITH cte AS (
   SELECT *, SUM([time]) OVER (PARTITION BY grp)
            -SUM([time]) OVER (PARTITION BY (SELECT NULL))/4 AS _grpoffset
   FROM @work)
...

該列_grpoffsettime每個總數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);

引用自:https://dba.stackexchange.com/questions/127920