选择按值均匀分布的分组数据

Question

我想将表中的数据选择为 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。如果您有什么可以帮助我的，请告诉我。

祝你今天愉快。

斯坦

Answer 1

这是一个算法的尝试。它并不完美，取决于你想花多少时间来完善它，可能还有一些进一步的小收获。

假设您有一个由四个队列执行的任务表。您知道与执行每个任务相关的工作量，并且您希望所有四个队列获得几乎相等的工作量，因此所有队列将在大约同一时间完成。

首先，我会使用模数对任务进行分区，按大小排序，从小到大。

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 并且有 4 个组，那么理想情况下每组应有 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);