Этот вопрос переполнения стека снова обнажил меня :
Вот вопрос Джона, который искал решение Java:
С массивом из N элементов, которые инициализированы в 0. Нам дана последовательность из M операций сортировки
(p; q; r)
. Операция(p; q; r)
означает, что целое число r следует добавить ко всем элементам массиваA[p];A[p + 1]; : : : ;A[q]
A[p];A[p + 1]; : : : ;A[q]
. Вы должны вывести максимальный элемент в массиве, который будет получен в результате выполнения всех M операций. Существует наивное решение, которое просто выполняет все операции и затем возвращает максимальное значение, которое занимает времяO(MN)
. Мы ищем более эффективный алгоритм.
Интересный. Действительно, наивное решение будет просто выполнять все операции в соответствии с просьбой. Другое наивное, но менее наивное решение преобразовало бы операции в сигналы вида (x; y)
для всех (p; r)
и для всех (q + 1; -r)
. Другими словами, мы могли бы реализовать решение, которое я представил тривиально, как таковое:
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
|
// This is just a utility class to model the ops class Operation { final int p; final int q; final int r; Operation( int p, int q, int r) { this .p = p; this .q = q; this .r = r; } } // These are some example ops Operation[] ops = { new Operation( 4 , 12 , 2 ), new Operation( 2 , 8 , 3 ), new Operation( 6 , 7 , 1 ), new Operation( 3 , 7 , 2 ) }; // Here, we're calculating the min and max // values for the combined values of p and q IntSummaryStatistics stats = Stream .of(ops) .flatMapToInt(op -> IntStream.of(op.p, op.q)) .summaryStatistics(); // Create an array for all the required elements using // the min value as "offset" int [] array = new int [stats.getMax() - stats.getMin()]; // Put +r and -r "signals" into the array for each op for (Operation op : ops) { int lo = op.p - stats.getMin(); int hi = op.q + 1 - stats.getMin(); if (lo >= 0 ) array[lo] = array[lo] + op.r; if (hi < array.length) array[hi] = array[hi] - op.r; } // Now, calculate the prefix sum sequentially in a // trivial loop int maxIndex = Integer.MIN_VALUE; int maxR = Integer.MIN_VALUE; int r = 0 ; for ( int i = 0 ; i < array.length; i++) { r = r + array[i]; System.out.println((i + stats.getMin()) + ":" + r); if (r > maxR) { maxIndex = i + stats.getMin(); maxR = r; } } System.out.println( "---" ); System.out.println(maxIndex + ":" + maxR); |
Вышеприведенная программа распечатает:
01
02
03
04
05
06
07
08
09
10
11
12
|
2:3 3:5 4:7 5:7 6:8 7:8 8:5 9:2 10:2 11:2 --- 6:8 |
Итак, максимальное значение генерируется в позиции 6, а значение равно 8.
Более быстрый расчет в Java 8
Это можно вычислить быстрее, используя новую операцию Arrays.parallelPrefix () в Java 8. Вместо цикла в конце просто напишите:
1
2
3
|
Arrays.parallelPrefix(array, Integer::sum); System.out.println( Arrays.stream(array).parallel().max()); |
Что удивительно, так как он может работать быстрее, чем последовательное решение O(M+N)
. Читайте о суммах префиксов здесь .
Теперь покажи мне обещанный код SQL
В SQL простое решение для последовательной и линейной сложности может быть легко повторно реализовано, и я покажу решение для PostgreSQL.
Как мы можем сделать это? Мы используем несколько функций здесь. Во-первых, мы используем общие табличные выражения (также известные как предложение WITH
) . Мы используем их для объявления табличных переменных. Первая переменная — это таблица операций, которая содержит наши инструкции по работе, как в Java:
1
2
3
4
5
6
7
8
9
|
WITH op (p, q, r) AS ( VALUES (4, 12, 2), (2, 8, 3), (6, 7, 1), (3, 7, 2) ), ... |
Это тривиально. По сути, мы просто генерируем пару примеров значений.
Вторая переменная таблицы — это таблица сигналов, в которой мы использовали ранее описанную оптимизацию размещения сигнала +r
во всех положениях p
и сигнала -r
во всех положениях q + 1
:
01
02
03
04
05
06
07
08
09
10
|
WITH ..., signal(x, r) AS ( SELECT p, r FROM op UNION ALL SELECT q + 1, -r FROM op ) ... |
Когда вы бежите:
1
|
SELECT * FROM signal ORDER BY x |
вы бы просто получили:
01
02
03
04
05
06
07
08
09
10
|
x r ------ 2 3 3 2 4 2 6 1 8 -2 8 -1 9 -3 13 -2 |
Все, что нам нужно сделать сейчас, это вычислить промежуточную сумму (которая по существу равна сумме префикса) следующим образом:
1
2
3
|
SELECT x, SUM (r) OVER ( ORDER BY x) FROM signal ORDER BY x |
01
02
03
04
05
06
07
08
09
10
|
x r ------ 2 3 3 5 4 7 6 8 8 5 8 5 9 2 13 0 |
Теперь просто найдите максимальное значение для r
, и все готово. Мы возьмем ярлык, используя ORDER BY
и LIMIT
:
1
2
3
4
|
SELECT x, SUM (r) OVER ( ORDER BY x) AS s FROM signal ORDER BY s DESC LIMIT 1 |
И мы вернулись с:
1
2
3
|
x r ------ 6 8 |
Отлично! Вот полный запрос:
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
|
WITH op (p, q, r) AS ( VALUES (4, 12, 2), (2, 8, 3), (6, 7, 1), (3, 7, 2) ), signal(x, r) AS ( SELECT p, r FROM op UNION ALL SELECT q + 1, -r FROM op ) SELECT x, SUM (r) OVER ( ORDER BY x) AS s FROM signal ORDER BY s DESC LIMIT 1 |
Можете ли вы превзойти лаконичность этого решения SQL? Бьюсь об заклад, вы не можете. Претенденты должны написать альтернативы в разделе комментариев.
Ссылка: | Время для забавного SQL: расчет суммы префикса от нашего партнера по JCG Лукаса Эдера из блога JAVA, SQL и JOOQ . |