Wählen Sie Daten aus, die in Gruppen unterteilt sind, die gleichmäßig nach Wert verteilt sind

Ich möchte die Daten aus einer Tabelle mit der Summe der Werte in den Gruppen so gleichmäßig wie möglich in 4 Gruppen auswählen. Ich bin sicher, dass ich es nicht klar genug erkläre, also werde ich versuchen, ein Beispiel zu geben.

Hier verwende ich NTILE (4), um die 4 Gruppen zu erstellen:

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

In der obigen Abfrage und im obigen Ergebnis wurden die anderen Spalten der Kürze halber weggelassen.

Sie können die Gruppen also auch wie folgt sehen:

  1    2    3    4
---  ---  ---  ---
 10    9    8    7
  6    5    4    3
  2    1    
---  ---  ---  ---
 18   15   12   10  Sum Totals of Time

Beachten Sie, dass die Gesamtsumme der Zeit mit NTile nicht wirklich zwischen den Gruppen ausgeglichen ist. Eine bessere Verteilung der Zeitwerte wäre zum Beispiel:

  1    2    3    4
---  ---  ---  ---
 10    9    8    7
  3    5    4    6
  1         2
---  ---  ---  ---
 14   14   14   13  Sum Totals of Time

Hier ist die Gesamtsumme der Zeit gleichmäßiger auf die 4 Gruppen verteilt.

Wie kann ich dies über eine TSQL-Anweisung durchführen?

Außerdem muss ich sagen, dass ich SQL Server 2012 verwende. Wenn Sie etwas haben, das mir helfen kann, lassen Sie es mich wissen.

Ich wünsche Ihnen einen schönen Tag.

Stan

Hier ist ein Stich in einen Algorithmus. Es ist nicht perfekt und je nachdem, wie viel Zeit Sie damit verbringen möchten, es zu verfeinern, müssen wahrscheinlich einige weitere kleine Gewinne erzielt werden.

Angenommen, Sie haben eine Tabelle mit Aufgaben, die von vier Warteschlangen ausgeführt werden sollen. Sie kennen den Arbeitsaufwand für die Ausführung der einzelnen Aufgaben und möchten, dass alle vier Warteschlangen fast gleich viel Arbeit erledigen, sodass alle Warteschlangen ungefähr zur gleichen Zeit abgeschlossen werden.

Zunächst würde ich die Aufgaben mit einem modularen, nach Größe geordneten, von klein nach groß aufteilen.

SELECT [time], ROW_NUMBER() OVER (ORDER BY [time])%4 AS grp, 0

Die ROW_NUMBER()ordnet jede Zeile nach Größe und weist dann ab 1 eine Zeilennummer zu. Dieser Zeilennummer wird grpim Round-Robin-Verfahren eine "Gruppe" (die Spalte) zugewiesen . Die erste Reihe ist Gruppe 1, die zweite Reihe ist Gruppe 2, dann 3, die vierte erhält Gruppe 0 und so weiter.

time ROW_NUMBER() grp
---- ------------ ---
   1            1   1
  10            2   2
  12            3   3
  15            4   0
  19            5   1
  22            6   2
...

Zur Vereinfachung der Verwendung speichere ich die Spalten timeund grpin einer Tabellenvariablen namens @work.

Jetzt können wir einige Berechnungen für diese Daten durchführen:

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

Die Spalte _grpoffsetgibt an, um wie viel sich die Summe timepro grpvom "idealen" Durchschnitt unterscheidet. Wenn die Gesamtzahl timealler Aufgaben 1000 beträgt und es vier Gruppen gibt, sollte es idealerweise insgesamt 250 in jeder Gruppe geben. Wenn eine Gruppe insgesamt 268 enthält, ist diese Gruppe _grpoffset=18.

Die Idee ist, die zwei besten Zeilen zu identifizieren, eine in einer "positiven" Gruppe (mit zu viel Arbeit) und eine in einer "negativen" Gruppe (mit zu wenig Arbeit). Wenn wir Gruppen in diesen beiden Zeilen austauschen können, können wir das Absolut _grpoffsetbeider Gruppen reduzieren .

Beispiel:

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

Mit einer Gesamtsumme von 727 sollte jede Gruppe eine Punktzahl von ungefähr 182 haben, damit die Verteilung perfekt ist. Der Unterschied zwischen der Punktzahl der Gruppe und 182 ist das, was wir in die _grpoffsetSpalte eintragen.

Wie Sie jetzt sehen können, sollten wir in den besten Welten Zeilen im Wert von etwa 40 Punkten von Gruppe 1 zu Gruppe 2 und etwa 24 Punkte von Gruppe 3 zu Gruppe 0 verschieben.

Hier ist der Code zum Identifizieren dieser Kandidatenzeilen:

    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);

Ich verbinde mich selbst mit dem allgemeinen Tabellenausdruck, den wir zuvor erstellt haben cte: Auf der einen Seite Gruppen mit positiven _grpoffset, auf der anderen Seite Gruppen mit negativen. Um weiter herauszufiltern, welche Zeilen zueinander passen sollen, muss der Austausch der Zeilen der positiven und negativen Seite verbessert werden _grpoffset, dh näher an 0 gebracht werden.

Das TOP 1und ORDER BYwählt das "beste" Match aus, das zuerst getauscht werden soll.

Jetzt müssen wir nur noch ein hinzufügen UPDATEund es schleifen, bis keine Optimierung mehr zu finden ist.

TL; DR - hier ist die Abfrage

Hier ist der vollständige Code:

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);