Ответ 1
Возвращаемые комбинации
Используя таблицу чисел или число-генерирующий CTE, выберите 0 - 2 ^ n - 1. Используя позиции бит, содержащие 1s в этих числах, чтобы указать присутствие или отсутствие относительных членов в комбинации и устранить те, которые не У вас есть правильное количество значений, вы должны иметь возможность возвращать результирующий набор со всеми комбинациями, которые вы хотите.
WITH Nums (Num) AS (
SELECT Num
FROM Numbers
WHERE Num BETWEEN 0 AND POWER(2, @n) - 1
), BaseSet AS (
SELECT ind = Power(2, Row_Number() OVER (ORDER BY Value) - 1), *
FROM @set
), Combos AS (
SELECT
ComboID = N.Num,
S.Value,
Cnt = Count(*) OVER (PARTITION BY N.Num)
FROM
Nums N
INNER JOIN BaseSet S ON N.Num & S.ind <> 0
)
SELECT
ComboID,
Value
FROM Combos
WHERE Cnt = @k
ORDER BY ComboID, Value;
Этот запрос работает очень хорошо, но я подумал о том, как его оптимизировать, вырезая из Nifty Parallel Bit Count, чтобы сначала получить правильное количество предметов, взятых за раз. Это выполняется в 3 - 3,5 раза быстрее (как процессор, так и время):
WITH Nums AS (
SELECT Num, P1 = (Num & 0x55555555) + ((Num / 2) & 0x55555555)
FROM dbo.Numbers
WHERE Num BETWEEN 0 AND POWER(2, @n) - 1
), Nums2 AS (
SELECT Num, P2 = (P1 & 0x33333333) + ((P1 / 4) & 0x33333333)
FROM Nums
), Nums3 AS (
SELECT Num, P3 = (P2 & 0x0f0f0f0f) + ((P2 / 16) & 0x0f0f0f0f)
FROM Nums2
), BaseSet AS (
SELECT ind = Power(2, Row_Number() OVER (ORDER BY Value) - 1), *
FROM @set
)
SELECT
ComboID = N.Num,
S.Value
FROM
Nums3 N
INNER JOIN BaseSet S ON N.Num & S.ind <> 0
WHERE P3 % 255 = @k
ORDER BY ComboID, Value;
Я пошел и прочитал страницу подсчета бит и подумал, что это может сработать лучше, если я не сделаю% 255, но полностью перейду с битовой арифметикой. Когда я получу шанс, я попробую это и посмотрю, как он складывается.
Мои требования к производительности основаны на запросах, запущенных без предложения ORDER BY. Для ясности, что этот код делает, является подсчет числа установленных 1-бит в Num из таблицы Numbers. Это потому, что номер используется в качестве своего рода индексатора для выбора того, какие элементы набора находятся в текущей комбинации, поэтому количество 1-бит будет одинаковым.
Надеюсь, вам понравится!
Для записи этот метод использования битовой диаграммы целых чисел для выбора элементов набора - это то, что я придумал "Vertical Cross Join". Это эффективно приводит к перекрестному объединению нескольких наборов данных, где количество множеств и кросс-соединений произвольно. Здесь количество наборов - это количество элементов, взятых за раз.
Фактически крест-соединение в обычном горизонтальном смысле (добавление большего количества столбцов в существующий список столбцов с каждым соединением) будет выглядеть примерно так:
SELECT
A.Value,
B.Value,
C.Value
FROM
@Set A
CROSS JOIN @Set B
CROSS JOIN @Set C
WHERE
A.Value = 'A'
AND B.Value = 'B'
AND C.Value = 'C'
Мои запросы выше эффективно "перекрестно соединяются" столько раз, сколько необходимо, только с одним соединением. Результаты не считаются по сравнению с фактическими кросс-соединениями, конечно, но это незначительное дело.
Критика вашего кода
Во-первых, могу ли я предложить это изменение вашему факториальному UDF:
ALTER FUNCTION dbo.Factorial (
@x bigint
)
RETURNS bigint
AS
BEGIN
IF @x <= 1 RETURN 1
RETURN @x * dbo.Factorial(@x - 1)
END
Теперь вы можете рассчитать гораздо более крупные комбинации комбинаций, плюс это более эффективно. Вы даже можете рассмотреть возможность использования decimal(38, 0), чтобы позволить более крупные промежуточные вычисления в ваших расчетах комбинации.
Во-вторых, ваш заданный запрос не возвращает правильные результаты. Например, используя мои тестовые данные из теста производительности, приведенного ниже, значение 1 совпадает с набором 18. Похоже, что ваш запрос занимает скользящую полосу, которая обертывается: каждый набор всегда имеет 5 смежных элементов, выглядя примерно так (я поворачивал чтобы было легче видеть):
1 ABCDE
2 ABCD Q
3 ABC PQ
4 AB OPQ
5 A NOPQ
6 MNOPQ
7 LMNOP
8 KLMNO
9 JKLMN
10 IJKLM
11 HIJKL
12 GHIJK
13 FGHIJ
14 EFGHI
15 DEFGH
16 CDEFG
17 BCDEF
18 ABCDE
19 ABCD Q
Сравните шаблон с моими запросами:
31 ABCDE
47 ABCD F
55 ABC EF
59 AB DEF
61 A CDEF
62 BCDEF
79 ABCD G
87 ABC E G
91 AB DE G
93 A CDE G
94 BCDE G
103 ABC FG
107 AB D FG
109 A CD FG
110 BCD FG
115 AB EFG
117 A C EFG
118 BC EFG
121 A DEFG
...
Просто для того, чтобы вести бит-шаблон → индекс комбинированной вещи домой для всех, кто интересуется, обратите внимание, что 31 в двоичном формате = 11111, а шаблон - ABCDE. 121 в двоичном формате - 1111001, а шаблон - A__DEFG (обратный рисунок).
Результаты работы с таблицей реальных чисел
Я выполнил некоторое тестирование производительности с большими наборами в моем втором запросе выше. В настоящее время у меня нет записи на используемой серверной версии. Здесь мои тестовые данные:
DECLARE
@k int,
@n int;
DECLARE @set TABLE (value varchar(24));
INSERT @set VALUES ('A'),('B'),('C'),('D'),('E'),('F'),('G'),('H'),('I'),('J'),('K'),('L'),('M'),('N'),('O'),('P'),('Q');
SET @n = @@RowCount;
SET @k = 5;
DECLARE @combinations bigint = dbo.Factorial(@n) / (dbo.Factorial(@k) * dbo.Factorial(@n - @k));
SELECT CAST(@combinations as varchar(max)) + ' combinations', MaxNumUsedFromNumbersTable = POWER(2, @n);
Питер показал, что это "вертикальное крест-соединение" не выполняется, а просто пишет динамический SQL, чтобы фактически использовать CROSS JOINs, которые он избегает. При тривиальной стоимости еще нескольких чтений его решение имеет метрику в 10-17 раз лучше. Производительность его запроса уменьшается быстрее, чем моя, поскольку количество работы увеличивается, но недостаточно быстро, чтобы никто не мог ее использовать.
Второй набор чисел ниже - это коэффициент, разделенный на первую строку в таблице, чтобы показать, как он масштабируется.
Erik
Items CPU Writes Reads Duration | CPU Writes Reads Duration
----- ------ ------ ------- -------- | ----- ------ ------ --------
17•5 7344 0 3861 8531 |
18•9 17141 0 7748 18536 | 2.3 2.0 2.2
20•10 76657 0 34078 84614 | 10.4 8.8 9.9
21•11 163859 0 73426 176969 | 22.3 19.0 20.7
21•20 142172 0 71198 154441 | 19.4 18.4 18.1
Петр
Items CPU Writes Reads Duration | CPU Writes Reads Duration
----- ------ ------ ------- -------- | ----- ------ ------ --------
17•5 422 70 10263 794 |
18•9 6046 980 219180 11148 | 14.3 14.0 21.4 14.0
20•10 24422 4126 901172 46106 | 57.9 58.9 87.8 58.1
21•11 58266 8560 2295116 104210 | 138.1 122.3 223.6 131.3
21•20 51391 5 6291273 55169 | 121.8 0.1 613.0 69.5
Экстраполяция, в конечном итоге мой запрос будет дешевле (хотя с самого начала в чтениях), но не надолго. Для использования 21 элемента в наборе уже требуется таблица с номерами до 2097152...
Вот комментарий, который я изначально сделал, прежде чем понять, что мое решение будет работать значительно лучше с помощью таблицы "на лету":
Мне нравятся решения с одним запросом на такие проблемы, но если вы ищете лучшую производительность, лучше всего использовать перекрестное соединение, если только вы не начнете иметь дело с огромным количеством комбинаций. Но что хочет кто-то с сотнями тысяч или даже миллионов строк? Даже растущее число чтений не кажется слишком большой проблемой, хотя 6 миллионов - это много, и это становится все быстрее...
В любом случае. Динамический SQL выигрывает. У меня все еще был прекрасный запрос.:)
Результаты работы с таблицей чисел на лету
Когда я изначально написал этот ответ, я сказал:
Обратите внимание, что вы можете использовать таблицу "на лету" , но я ее не пробовал.
Ну, я попробовал, и результаты заключались в том, что он выполнялся намного лучше! Вот запрос, который я использовал:
DECLARE @N int = 16, @K int = 12;
CREATE TABLE #Set (Value char(1) PRIMARY KEY CLUSTERED);
CREATE TABLE #Items (Num int);
INSERT #Items VALUES (@K);
INSERT #Set
SELECT TOP (@N) V
FROM
(VALUES ('A'),('B'),('C'),('D'),('E'),('F'),('G'),('H'),('I'),('J'),('K'),('L'),('M'),('N'),('O'),('P'),('Q'),('R'),('S'),('T'),('U'),('V'),('W'),('X'),('Y'),('Z')) X (V);
GO
DECLARE
@N int = (SELECT Count(*) FROM #Set),
@K int = (SELECT TOP 1 Num FROM #Items);
DECLARE @combination int, @value char(1);
WITH L0 AS (SELECT 1 N UNION ALL SELECT 1),
L1 AS (SELECT 1 N FROM L0, L0 B),
L2 AS (SELECT 1 N FROM L1, L1 B),
L3 AS (SELECT 1 N FROM L2, L2 B),
L4 AS (SELECT 1 N FROM L3, L3 B),
L5 AS (SELECT 1 N FROM L4, L4 B),
Nums AS (SELECT Row_Number() OVER(ORDER BY (SELECT 1)) Num FROM L5),
Nums1 AS (
SELECT Num, P1 = (Num & 0x55555555) + ((Num / 2) & 0x55555555)
FROM Nums
WHERE Num BETWEEN 0 AND Power(2, @N) - 1
), Nums2 AS (
SELECT Num, P2 = (P1 & 0x33333333) + ((P1 / 4) & 0x33333333)
FROM Nums1
), Nums3 AS (
SELECT Num, P3 = (P2 & 0x0F0F0F0F) + ((P2 / 16) & 0x0F0F0F0F)
FROM Nums2
), BaseSet AS (
SELECT Ind = Power(2, Row_Number() OVER (ORDER BY Value) - 1), *
FROM #Set
)
SELECT
@Combination = N.Num,
@Value = S.Value
FROM
Nums3 N
INNER JOIN BaseSet S
ON N.Num & S.Ind <> 0
WHERE P3 % 255 = @K;
Обратите внимание, что я выбрал значения в переменных, чтобы уменьшить время и память, необходимые для тестирования всего. Сервер все равно работает. Я изменил версию Peter, чтобы быть похожим, и удалил ненужные дополнения, чтобы они были как можно более тонкими. Версия сервера, используемая для этих тестов, - Microsoft SQL Server 2008 (RTM) - 10.0.1600.22 (Intel X86) Standard Edition on Windows NT 5.2 <X86> (Build 3790: Service Pack 2) (VM) работает на виртуальной машине.
Ниже приведены графики, показывающие кривые производительности для значений N и K до 21. Базовые данные для них находятся в другом ответе на этой странице. Значения являются результатом 5 прогонов каждого запроса при каждом значении K и N, а затем выбрасывают наилучшие и худшие значения для каждой метрики и усредняют оставшиеся 3.
В принципе, моя версия имеет "плечо" (в крайнем левом углу диаграммы) при высоких значениях N и низких значениях K, что делает его хуже, чем динамическая версия SQL. Однако это остается довольно низким и постоянным, а центральный пик вокруг N = 21 и K = 11 намного ниже для Duration, CPU и Reads, чем для динамической версии SQL.
Я включил диаграмму количества строк, из которых каждый элемент должен возвращаться, чтобы вы могли видеть, как выполняется выполнение запроса в зависимости от того, насколько велика работа, которую он должен выполнять.
Подробнее о результатах работы см. мой дополнительный ответ на этой странице. Я попал в лимит персонажей и не мог включить его здесь. (Любые идеи, где еще это можно сказать?) Чтобы перенести вещи в будущее на мои результаты производительности первой версии, здесь тот же формат, что и раньше:
Erik
Items CPU Duration Reads Writes | CPU Duration Reads
----- ----- -------- ------- ------ | ----- -------- -------
17•5 354 378 12382 0 |
18•9 1849 1893 97246 0 | 5.2 5.0 7.9
20•10 7119 7357 369518 0 | 20.1 19.5 29.8
21•11 13531 13807 705438 0 | 38.2 36.5 57.0
21•20 3234 3295 48 0 | 9.1 8.7 0.0
Петр
Items CPU Duration Reads Writes | CPU Duration Reads
----- ----- -------- ------- ------ | ----- -------- -------
17•5 41 45 6433 0 |
18•9 2051 1522 214021 0 | 50.0 33.8 33.3
20•10 8271 6685 864455 0 | 201.7 148.6 134.4
21•11 18823 15502 2097909 0 | 459.1 344.5 326.1
21•20 25688 17653 4195863 0 | 626.5 392.3 652.2
Выводы
- Таблицы "на лету" лучше, чем реальная таблица, содержащая строки, так как чтение одного на огромных количествах строк требует большого количества операций ввода-вывода. Лучше использовать небольшой процессор.
- Мои начальные тесты были недостаточно широкими, чтобы действительно показать характеристики производительности двух версий.
- Версия Peter может быть улучшена за счет того, что каждый JOIN не только больше, чем предыдущий элемент, но также ограничивает максимальное значение в зависимости от того, сколько еще предметов должно быть вписано в набор. Например, в 21 пункте, взятом по 21 за раз, есть только один ответ из 21 строки (все 21 элемент, один раз), но промежуточные ряды в динамической версии SQL на ранней стадии выполнения содержат комбинации, такие как "AU" на шаге 2, хотя это будет отменено при следующем соединении, так как нет значения выше, чем "U". Аналогично, промежуточный набор строк на шаге 5 будет содержать "ARSTU", но единственной действующей комбо в этой точке является "ABCDE". Эта улучшенная версия не имела бы более низкого пика в центре, поэтому, возможно, не улучшила бы ее достаточно, чтобы стать явным победителем, но она, по крайней мере, стала бы симметричной, чтобы диаграммы не оставались максимумом за середину региона, но отступали до около 0, как моя версия (см. верхний угол пиков для каждого запроса).
Анализ продолжительности
- Между версиями в длительности ( > 100 мс) нет существенной разницы до 14 пунктов, взятых по 12 за раз. До этого момента моя версия выигрывает 30 раз, а динамическая версия SQL выигрывает 43 раза.
- Начиная с 14 • 12, моя версия была быстрее 65 раз (59 > 100 мс), динамическая SQL-версия 64 раза (60 > 100 мс). Тем не менее, все время, когда моя версия была быстрее, она сохраняла общую усредненную продолжительность в 256,5 секунд, а когда динамическая версия SQL была быстрее, она сохраняла 80,2 секунды.
- Общая усредненная продолжительность для всех испытаний была Эрик 270,3 секунды, Питер 446,2 секунды.
- Если была создана таблица поиска, чтобы определить, какую версию использовать (выбор более быстрой для входов), все результаты могут быть выполнены за 188,7 секунды. Используя самый медленный каждый раз, потребуется 527,7 секунды.
Считывает анализ
Анализ продолжительности показал, что мой запрос выиграл значительную, но не слишком большую сумму. Когда метрика переключается на чтение, появляется совсем другое изображение - мой запрос использует в среднем 1/10 чтения.
- Между версиями в reads ( > 1000) не существует существенной разницы, пока 9 предметов не будут взяты 9 за раз. До этого момента моя версия выигрывает 30 раз, а динамическая версия SQL выигрывает 17 раз.
- Начиная с 9 • 9, моя версия использовала меньше 118 раз (113 > 1000), динамическую версию SQL 69 раз (31 > 1000). Тем не менее, все время, когда моя версия использовала меньшее количество просмотров, она сохраняла средние среднестатистические 75.9M-чтения, а когда динамическая версия SQL была быстрее, она сохраняла 380K.
- Общее усредненное чтение для всех испытаний было Erik 8.4M, Peter 84M.
- Если для определения используемой версии (выбор лучшего для входов) была создана таблица поиска, все результаты могут быть выполнены в 8M-чтениях. Используя худшее, каждый раз будет читаться 84.3M.
Мне было бы очень интересно увидеть результаты обновленной динамической версии SQL, которая добавляет дополнительный верхний предел для элементов, выбранных на каждом шаге, как описано выше.
Добавление
Следующая версия моего запроса достигает улучшения примерно на 2,25% по сравнению с результатами, приведенными выше. Я использовал метод подсчета бит MIT HAKMEM и добавил Convert(int) в результат row_number(), так как он возвращает bigint. Конечно, мне жаль, что это версия, которую я использовал для всех тестов производительности и диаграмм и данных выше, но вряд ли я когда-нибудь переделаю ее, поскольку это было трудоемким.
WITH L0 AS (SELECT 1 N UNION ALL SELECT 1),
L1 AS (SELECT 1 N FROM L0, L0 B),
L2 AS (SELECT 1 N FROM L1, L1 B),
L3 AS (SELECT 1 N FROM L2, L2 B),
L4 AS (SELECT 1 N FROM L3, L3 B),
L5 AS (SELECT 1 N FROM L4, L4 B),
Nums AS (SELECT Row_Number() OVER(ORDER BY (SELECT 1)) Num FROM L5),
Nums1 AS (
SELECT Convert(int, Num) Num
FROM Nums
WHERE Num BETWEEN 1 AND Power(2, @N) - 1
), Nums2 AS (
SELECT
Num,
P1 = Num - ((Num / 2) & 0xDB6DB6DB) - ((Num / 4) & 0x49249249)
FROM Nums1
),
Nums3 AS (SELECT Num, Bits = ((P1 + P1 / 8) & 0xC71C71C7) % 63 FROM Nums2),
BaseSet AS (SELECT Ind = Power(2, Row_Number() OVER (ORDER BY Value) - 1), * FROM #Set)
SELECT
N.Num,
S.Value
FROM
Nums3 N
INNER JOIN BaseSet S
ON N.Num & S.Ind <> 0
WHERE
Bits = @K
И я не мог удержаться от показа еще одной версии, которая выполняет поиск, чтобы получить количество бит. Это может быть даже быстрее, чем другие версии:
DECLARE @BitCounts binary(255) =
0x01010201020203010202030203030401020203020303040203030403040405
+ 0x0102020302030304020303040304040502030304030404050304040504050506
+ 0x0102020302030304020303040304040502030304030404050304040504050506
+ 0x0203030403040405030404050405050603040405040505060405050605060607
+ 0x0102020302030304020303040304040502030304030404050304040504050506
+ 0x0203030403040405030404050405050603040405040505060405050605060607
+ 0x0203030403040405030404050405050603040405040505060405050605060607
+ 0x0304040504050506040505060506060704050506050606070506060706070708;
WITH L0 AS (SELECT 1 N UNION ALL SELECT 1),
L1 AS (SELECT 1 N FROM L0, L0 B),
L2 AS (SELECT 1 N FROM L1, L1 B),
L3 AS (SELECT 1 N FROM L2, L2 B),
L4 AS (SELECT 1 N FROM L3, L3 B),
L5 AS (SELECT 1 N FROM L4, L4 B),
Nums AS (SELECT Row_Number() OVER(ORDER BY (SELECT 1)) Num FROM L5),
Nums1 AS (SELECT Convert(int, Num) Num FROM Nums WHERE Num BETWEEN 1 AND Power(2, @N) - 1),
BaseSet AS (SELECT Ind = Power(2, Row_Number() OVER (ORDER BY Value) - 1), * FROM ComboSet)
SELECT
@Combination = N.Num,
@Value = S.Value
FROM
Nums1 N
INNER JOIN BaseSet S
ON N.Num & S.Ind <> 0
WHERE
@K =
Convert(int, Substring(@BitCounts, N.Num & 0xFF, 1))
+ Convert(int, Substring(@BitCounts, N.Num / 256 & 0xFF, 1))
+ Convert(int, Substring(@BitCounts, N.Num / 65536 & 0xFF, 1))
+ Convert(int, Substring(@BitCounts, N.Num / 16777216, 1))