Статьи

Время для некоторого Прикольного SQL: Расчет суммы префикса

Декабрь 12, 2018

Этот вопрос переполнения стека снова обнажил меня :

[найти] максимальный элемент в массиве, который может возникнуть в результате выполнения всех M операций

Вот вопрос Джона, который искал решение 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 .
41
Share: