В этой челлендж-серии статей попробуем использовать PostgreSQL как среду для решения задач Advent of Code 2024.
Возможно, SQL не самый подходящий для этого язык, зато мы рассмотрим его различные возможности, о которых вы могли и не подозревать.
В этой части рассмотрим некоторые "грабли", на которые можно наступить, реализуя рекурсивные алгоритмы на SQL... Которые иногда можно сделать вовсе нерекурсивными, ускоряя запрос в десятки раз!
Решение Day 1: Historian Hysteria (регулярные выражения и условная агрегация)
Решение Day 5: Print Queue (поиск в словаре и массивах, сортировка "пузырьком")
Решение Day 6: Guard Gallivant (рекурсивные циклы и их контроль)
Решение Day 8: Resonant Collinearity (генерация и подсчет уникальных комбинаций)
Решение Day 11: Plutonian Pebbles (агрегация внутри рекурсии)
Оригинальная постановка задачи и ее перевод:
Advent of Code 2024, Day 9: Disk Fragmenter
--- День 9: Фрагментатор диска ---
Еще одно нажатие кнопки оставляет вас в знакомых коридорах дружелюбных амфипод! Хорошо, что каждый из вас каким-то образом получил свою собственную мини-подводную лодку. Историки улетают на поиски Шефа, в основном врезаясь прямо в стены.
Пока Историки быстро разбираются, как управлять этими штуками, вы замечаете в углу амфипода, который борется со своим компьютером. Он пытается сделать больше непрерывного свободного пространства, сжимая все файлы, но его программа не работает; вы предлагаете помочь.
Он показывает вам карту диска (ваши входные данные для головоломки), которую он уже сгенерировал. Например:
2333133121414131402
Карта диска использует плотный формат для представления расположения файлов и свободного пространства на диске. Цифры попеременно указывают на длину файла и длину свободного пространства.
Итак, карта диска подобная 12345
будет представлять файл из одного блока, два блока свободного пространства, файл из трех блоков, четыре блока свободного пространства и затем файл из пяти блоков. Карта диска подобная 90909
будет представлять три файла из девяти блоков подряд (без свободного пространства между ними).
Каждый файл на диске также имеет идентификационный номер, основанный на порядке файлов, как они появляются до того, как они были переупорядочены, начиная с ID 0
. Таким образом, карта диска 12345
имеет три файла: файл из одного блока с ID 0
, файл из трех блоков с ID 1
и файл из пяти блоков с ID 2
. Используя один символ для каждого блока, где цифры — это идентификатор файла, а .
- свободное пространство, карта диска 12345
представляет такие отдельные блоки:
0..111....22222
Первый пример выше, 2333133121414131402
представляет собой такие отдельные блоки:
00...111...2...333.44.5555.6666.777.888899
Амфипод хотел бы перемещать блоки файлов по одному за раз с конца диска в самый левый блок свободного пространства (пока не останется пробелов между блоками файлов). Для карты диска 12345
процесс выглядит следующим образом:
0..111....22222
02.111....2222.
022111....222..
0221112...22...
02211122..2....
022111222......
Первый пример требует еще нескольких шагов:
00...111...2...333.44.5555.6666.777.888899
009..111...2...333.44.5555.6666.777.88889.
0099.111...2...333.44.5555.6666.777.8888..
00998111...2...333.44.5555.6666.777.888...
009981118..2...333.44.5555.6666.777.88....
0099811188.2...333.44.5555.6666.777.8.....
009981118882...333.44.5555.6666.777.......
0099811188827..333.44.5555.6666.77........
00998111888277.333.44.5555.6666.7.........
009981118882777333.44.5555.6666...........
009981118882777333644.5555.666............
00998111888277733364465555.66.............
0099811188827773336446555566..............
Последним шагом этого процесса сжатия файлов является обновление контрольной суммы файловой системы. Чтобы вычислить контрольную сумму, сложите результат умножения позиции каждого из этих блоков на номер идентификатора файла, который он содержит. Самый левый блок находится в позиции 0
. Если блок содержит свободное пространство, пропустите его.
Продолжая первый пример, позиция первых нескольких блоков, умноженная на номер идентификатора файла, равна 0 * 0 = 0
, 1 * 0 = 0
, 2 * 9 = 18
, 3 * 9 = 27
, 4 * 8 = 32
, и т. д. В этом примере контрольная сумма представляет собой сумму этих значений, 1928
.
Упакуйте жесткий диск амфипода, используя запрошенный им процесс. Какова итоговая контрольная сумма файловой системы? (Будьте осторожны при копировании/вставке входных данных для этой головоломки; это одна очень длинная строка.)
Ваш ответ на головоломку был 6307275788409
.
--- Часть вторая ---
После завершения сразу же становятся ясны две вещи. Во-первых, на диске определенно гораздо больше непрерывного свободного пространства, как и надеялся амфипод. Во-вторых, компьютер работает гораздо медленнее! Может быть, введение всей этой фрагментации файловой системы было плохой идеей?
У предприимчивого амфипода уже есть новый план: вместо того, чтобы перемещать отдельные блоки, он хотел бы попробовать уплотнить файлы на своем диске, перемещая целые файлы.
На этот раз попытайтесь переместить целые файлы в самый левый диапазон блоков свободного пространства, в которые может поместиться файл. Попытайтесь переместить каждый файл ровно один раз в порядке убывания номера идентификатора файла, начиная с файла с самым большим номером идентификатора файла. Если слева от файла нет диапазона свободного пространства, достаточно большого для размещения файла, файл не перемещается.
Первый пример из предыдущего теперь выглядит иначе:
00...111...2...333.44.5555.6666.777.888899
0099.111...2...333.44.5555.6666.777.8888..
0099.1117772...333.44.5555.6666.....8888..
0099.111777244.333....5555.6666.....8888..
00992111777.44.333....5555.6666.....8888..
Процесс обновления контрольной суммы файловой системы тот же самый; теперь контрольная сумма этого примера будет 2858
.
Начать заново, теперь сжимая жесткий диск амфипода, используя этот новый метод. Какова итоговая контрольная сумма файловой системы?
Часть 1
Решение этой задачи достаточно сложно для понимания "сходу", поэтому давайте разберем его детально пошагово.
Для начала получим из входной "карты" занятых блоков. Автонумерацию строк нам поможет получить уже знакомый по решениям предыдущих задач функционал WITH ORDINALITY
, а ID файла - половина номера в каждой нечетной позиции:
WITH map AS (
SELECT
sz::::integer -- размер сегмента
, n -- порядковый номер сегмента
, CASE
WHEN n % 2 = 1 THEN n / 2
END fid -- ID файла
FROM
regexp_split_to_table( -- разбиение в таблицу ...
'2333133121414131402'
, '' -- ... по отдельным символам
)
WITH ORDINALITY T(sz, n)
)
sz | n | fid
2 | 1 | 0
3 | 2 |
3 | 3 | 1
3 | 4 |
1 | 5 | 2
3 | 6 |
3 | 7 | 3
1 | 8 |
2 | 9 | 4
1 | 10 |
4 | 11 | 5
1 | 12 |
4 | 13 | 6
1 | 14 |
3 | 15 | 7
1 | 16 |
4 | 17 | 8
0 | 18 |
2 | 19 | 9
Теперь превратим нашу карту сегментов в две карты-массива отдельных блоков - представления дискового пространства и "файловых" блоков в порядке перемещения (обратном):
, blk AS (
SELECT
array_agg(fid ORDER BY n) blkdsk -- собираем все блоки в прямом порядке
, array_agg(fid ORDER BY n DESC) -- собираем в обратном порядке ...
FILTER(WHERE fid IS NOT NULL) blkfil -- ... только занятые файлами блоки
FROM
map
, unnest(array_fill(NULL::integer, ARRAY[sz::integer])) -- размножим запись sz раз
)
blkdsk : {0,0,NULL,NULL,NULL,1,1,1,NULL,NULL,NULL,2,NULL,NULL,NULL,3,3,3,NULL,4,4,NULL,5,5,5,5,NULL,6,6,6,6,NULL,7,7,7,NULL,8,8,8,8,9,9}
blkfil : {9,9,8,8,8,8,7,7,7,6,6,6,6,5,5,5,5,4,4,3,3,3,2,1,1,1,0,0}
Здесь мы воспользовались array_fill
для формирования заполненного NULL
массива длины sz
для каждой записи сегмента, и тут же "развернули" его в sz
записей, "размножив" исходный сегмент нужное нам число раз.
Собственно, остается лишь вычислить искомую контрольную сумму, используя в рекурсивном (не забываем добавить WITH RECURSIVE
перед map
) "цикле" два указателя на позиции в каждом из массивов:
, r AS (
SELECT
1 posdsk -- позиция блока "на диске"
, 1 posfil -- позиция "перемещаемого" файлового блока
, 0::bigint checksum
UNION ALL
SELECT
posdsk + 1 -- позиция "на диске" увеличивается каждый раз
, posfil + (blkdsk[posdsk] IS NULL)::integer -- позиция "файла" - только если "дисковый" блок пуст
, checksum + (posdsk - 1) * coalesce(blkdsk[posdsk], blkfil[posfil])
FROM
r
, blk
WHERE
posdsk <= array_length(blkfil, 1) -- вычислять надо до исчерпания всех файловых блоков
)
posdsk | posfil | checksum
1 | 1 | 0
2 | 1 | 0
3 | 1 | 0
4 | 2 | 18
5 | 3 | 45
6 | 4 | 77
7 | 4 | 82
8 | 4 | 88
9 | 4 | 95
10 | 5 | 159
11 | 6 | 231
12 | 7 | 311
13 | 7 | 333
14 | 8 | 417
15 | 9 | 508
16 | 10 | 606
17 | 10 | 651
18 | 10 | 699
19 | 10 | 750
20 | 11 | 858
21 | 11 | 934
22 | 11 | 1014
23 | 12 | 1140
24 | 12 | 1250
25 | 12 | 1365
26 | 12 | 1485
27 | 12 | 1610
28 | 13 | 1766
29 | 13 | 1928
Из полученной выборки остается лишь взять "последнее" (с наибольшим posdsk
) значение checksum
. В целом, наш итоговый запрос принимает следующий вид:
WITH RECURSIVE map AS (
SELECT
sz::integer -- размер сегмента
, n -- порядковый номер сегмента
, CASE
WHEN n % 2 = 1 THEN n / 2
END fid -- ID файла
FROM
regexp_split_to_table( -- разбиение в таблицу ...
'2333133121414131402'
, '' -- ... по отдельным символам
)
WITH ORDINALITY T(sz, n)
)
, blk AS (
SELECT
array_agg(fid ORDER BY n) blkdsk
, array_agg(fid ORDER BY n DESC) FILTER(WHERE fid IS NOT NULL) blkfil
FROM
map
, unnest(array_fill(NULL::integer, ARRAY[sz::integer])) -- размножим запись sz раз
)
, r AS (
SELECT
1 posdsk -- позиция блока "на диске"
, 1 posfil -- позиция "перемещаемого" файлового блока
, 0::bigint checksum
UNION ALL
SELECT
posdsk + 1 -- позиция "на диске" увеличивается каждый раз
, posfil + (blkdsk[posdsk] IS NULL)::integer -- позиция "файла" - только если "дисковый" блок пуст
, checksum + (posdsk - 1) * coalesce(blkdsk[posdsk], blkfil[posfil])
FROM
r
, blk
WHERE
posdsk <= array_length(blkfil, 1) -- вычислять надо до исчерпания всех файловых блоков
)
SELECT
checksum
FROM
r
ORDER BY
posdsk DESC
LIMIT 1;
В принципе, этот запрос решает задачу, но при вводе целевой последовательности (а там 20 тысяч цифр-сегментов) уходит считать долго-долго...
Давайте посмотрим на план "маленького" запроса, чтобы заметить причину:
Оказывается, у нас вообще нет никаких промежуточных CTE map
и blk
! Чрезмерно "умный" PostgreSQL "заинлайнил" их вычисление, поскольку они используются по ходу запроса лишь однократно. Только вот из-за этого условие выхода из рекурсии (Join Filter
в узле Nested Loop
(#4)) ему приходится перевычислять на каждом шаге!
А оно ни разу не простое! Приведем его в минимально-читаемый вид:
Join Filter: (
r_1.posdsk <= array_length(
(
array_agg(
CASE WHEN ((t.n % '2'::bigint) = 1) THEN (t.n / 2) ELSE NULL::bigint END
ORDER BY t.n DESC
)
FILTER (
WHERE (
CASE WHEN ((t.n % '2'::bigint) = 1) THEN (t.n / 2) ELSE NULL::bigint END IS NOT NULL
)
)
)
, 1
)
)
Чтобы PostgreSQL не слишком умничал, достаточно лишь добавить MATERIALIZED
у CTE blk
:
WITH RECURSIVE map AS (
SELECT
sz::integer -- размер сегмента
, n -- порядковый номер сегмента
, CASE
WHEN n % 2 = 1 THEN n / 2
END fid -- ID файла
FROM
regexp_split_to_table( -- разбиение в таблицу ...
'2333133121414131402'
, '' -- ... по отдельным символам
)
WITH ORDINALITY T(sz, n)
)
, blk AS MATERIALIZED (
SELECT
array_agg(fid ORDER BY n) blkdsk
, array_agg(fid ORDER BY n DESC) FILTER(WHERE fid IS NOT NULL) blkfil
FROM
map
, unnest(array_fill(NULL::integer, ARRAY[sz::integer])) -- размножим запись sz раз
)
, r AS (
SELECT
1 posdsk -- позиция блока "на диске"
, 1 posfil -- позиция "перемещаемого" файлового блока
, 0::bigint checksum
UNION ALL
SELECT
posdsk + 1 -- позиция "на диске" увеличивается каждый раз
, posfil + (blkdsk[posdsk] IS NULL)::integer -- позиция "файла" - только если "дисковый" блок пуст
, checksum + (posdsk - 1) * coalesce(blkdsk[posdsk], blkfil[posfil])
FROM
r
, blk
WHERE
posdsk <= array_length(blkfil, 1) -- вычислять надо до исчерпания всех файловых блоков
)
SELECT
checksum
FROM
r
ORDER BY
posdsk DESC
LIMIT 1;
Тогда план выправляется, и результат вычисляется всего за 8 с небольшим секунд:
А теперь - без рекурсии!
Давайте задумаемся - нужна ли нам тут рекурсия вообще, что мы с ее помощью делали?..
По сути, мы пронумеровали все блоки диска, а затем поставили соответствие между свободными блоками и занятыми файловыми в обратном порядке - но это можно сделать и без всякой рекурсии!
, blk AS (
SELECT
posdsk
, fid
, CASE
WHEN fid IS NULL THEN
count(*) FILTER(WHERE fid IS NULL) OVER(ORDER BY posdsk)
END posfiln -- "пронумеруем" свободные блоки в прямом порядке
, CASE
WHEN fid IS NOT NULL THEN
count(*) FILTER(WHERE fid IS NOT NULL) OVER(ORDER BY posdsk DESC)
END posfilo -- "пронумеруем" занятые блоки в обратном порядке
FROM
(
SELECT
row_number() OVER() posdsk -- пронумеруем все блоки
, map.*
FROM
map
, unnest(array_fill(NULL::integer, ARRAY[sz::integer])) -- размножим запись sz раз
) T
)
posdsk | fid | posfiln | posfilo
1 | 0 | | 28
2 | 0 | | 27
3 | | 1 |
4 | | 2 |
5 | | 3 |
6 | 1 | | 26
7 | 1 | | 25
8 | 1 | | 24
9 | | 4 |
10 | | 5 |
11 | | 6 |
12 | 2 | | 23
13 | | 7 |
14 | | 8 |
15 | | 9 |
16 | 3 | | 22
17 | 3 | | 21
18 | 3 | | 20
19 | | 10 |
20 | 4 | | 19
21 | 4 | | 18
22 | | 11 |
23 | 5 | | 17
24 | 5 | | 16
25 | 5 | | 15
26 | 5 | | 14
27 | | 12 |
28 | 6 | | 13
29 | 6 | | 12
30 | 6 | | 11
31 | 6 | | 10
32 | | 13 |
33 | 7 | | 9
34 | 7 | | 8
35 | 7 | | 7
36 | | 14 |
37 | 8 | | 6
38 | 8 | | 5
39 | 8 | | 4
40 | 8 | | 3
41 | 9 | | 2
42 | 9 | | 1
Собственно, остается лишь совместить полученную выборку с собой же, стыкуя новую позицию перемещаемого файлового блока к старой через LEFT JOIN
, и вычислить чек-сумму. Не забываем ограничить подсчет количеством занятых блоков:
SELECT
sum((n.posdsk - 1) * coalesce(n.fid, o.fid)) -- не забываем -1!
FROM
blk n
LEFT JOIN
blk o
ON n.posfiln = o.posfilo -- совмещаем новую/старую позицию файлового блока
WHERE
n.posdsk <= (SELECT sum(sz) FILTER(WHERE fid IS NOT NULL) FROM map); -- ограничиваемся только занятыми блоками
Полностью наш запрос теперь выглядит так:
WITH map AS (
SELECT
sz::integer -- размер сегмента
, n -- порядковый номер сегмента
, CASE
WHEN n % 2 = 1 THEN n / 2
END fid -- ID файла
FROM
regexp_split_to_table( -- разбиение в таблицу ...
'2333133121414131402'
, '' -- ... по отдельным символам
)
WITH ORDINALITY T(sz, n)
)
, blk AS (
SELECT
posdsk
, fid
, CASE
WHEN fid IS NULL THEN
count(*) FILTER(WHERE fid IS NULL) OVER(ORDER BY posdsk)
END posfiln -- "пронумеруем" свободные блоки в прямом порядке
, CASE
WHEN fid IS NOT NULL THEN
count(*) FILTER(WHERE fid IS NOT NULL) OVER(ORDER BY posdsk DESC)
END posfilo -- "пронумеруем" занятые блоки в обратном порядке
FROM
(
SELECT
row_number() OVER() posdsk -- пронумеруем все блоки
, map.*
FROM
map
, unnest(array_fill(NULL::integer, ARRAY[sz::integer])) -- размножим запись sz раз
) T
)
SELECT
sum((n.posdsk - 1) * coalesce(n.fid, o.fid)) -- не забываем -1!
FROM
blk n
LEFT JOIN
blk o
ON n.posfiln = o.posfilo -- совмещаем новую/старую позицию файлового блока
WHERE
n.posdsk <= (SELECT sum(sz) FILTER(WHERE fid IS NOT NULL) FROM map); -- ограничиваемся только занятыми блоками
Нельзя сказать, что мы переписали запрос как-то слишком уж сложно, но его быстродействие увеличилось в 25 раз:
Часть 2
Во второй части нас просят перемещать файлы на свободное место уже не отдельными блоками, а целиковыми сегментами.
Добавим вычисление позиции каждого такого сегмента в самое начало нашего запроса:
WITH map AS (
SELECT
sz::integer -- размер сегмента
, n -- порядковый номер сегмента
, CASE
WHEN n % 2 = 1 THEN n / 2
END fid -- ID файла
, sum(sz::bigint) OVER(ORDER BY n) - sz::bigint pos -- позиция начала сегмента
FROM
regexp_split_to_table( -- разбиение в таблицу ...
'2333133121414131402'
, '' -- ... по отдельным символам
)
WITH ORDINALITY T(sz, n)
)
sz | n | fid | pos
2 | 1 | 0 | 0
3 | 2 | | 2
3 | 3 | 1 | 5
3 | 4 | | 8
1 | 5 | 2 | 11
3 | 6 | | 12
3 | 7 | 3 | 15
1 | 8 | | 18
2 | 9 | 4 | 19
1 | 10 | | 21
4 | 11 | 5 | 22
1 | 12 | | 26
4 | 13 | 6 | 27
1 | 14 | | 31
3 | 15 | 7 | 32
1 | 16 | | 35
4 | 17 | 8 | 36
0 | 18 | | 40
2 | 19 | 9 | 40
Поскольку тут остающееся после переноса конкретного файла свободное место влияет на возможность переноса следующего, без рекурсии обойтись будет слишком уж сложно. Поэтому сразу соберем две "карты" сегментов с парами позиций начала/конца: для заполненных файлами и для свободных (сразу укажем MATERIALIZED
, чтобы не наступить на те же грабли):
, seg AS MATERIALIZED (
SELECT
array_agg(ARRAY[pos, pos + sz]::integer[] ORDER BY n DESC)
FILTER(WHERE fid IS NOT NULL) segfile -- карта файлов
, array_agg(ARRAY[pos, pos + sz]::integer[] ORDER BY n)
FILTER(WHERE fid IS NULL) segfree -- карта свободных сегментов
FROM
map
)
segfile : {{40,42},{36,40},{32,35},{27,31},{22,26},{19,21},{15,18},{11,12},{5,8},{0,2}}
segfree : {{2,5},{8,11},{12,15},{18,19},{21,22},{26,27},{31,32},{35,36},{40,40}}
Теперь самое сложное - на каждом шаге рекурсии найти переносимый файл, последовательно "примеряя" его к каждому "свободному" сегменту:
, r AS (
SELECT
1 i
, *
FROM
seg
UNION ALL
SELECT
i + 1
, coalesce(T.segfile, r.segfile) -- если нашли возможный перенос для файла - используем его ...
, coalesce(T.segfree, r.segfree) -- ... если нет - сохраняем прежние состояния
FROM
r
LEFT JOIN
LATERAL (
SELECT -- реконструкция массивов-карт с учетом переноса
segfile[:i - 1]
|| ARRAY[segfree[j][1], segfree[j][1] + segfile[i][2] - segfile[i][1]]
|| segfile[i + 1:] segfile
, segfree[:j - 1]
|| ARRAY[segfree[j][1] + segfile[i][2] - segfile[i][1], segfree[j][2]]
|| segfree[j + 1:] segfree
FROM
generate_subscripts(segfree, 1) j -- перебор свободных сегментов
WHERE
segfree[j][1] < segfile[i][1] AND -- проверка возможности переноса
segfree[j][2] - segfree[j][1] >= segfile[i][2] - segfile[i][1]
LIMIT 1 -- ищем до первой возможности
) T
ON TRUE
WHERE
i <= array_length(r.segfile, 1) -- ограничиваемся количеством файлов
)
i | segfile/segfree
1 | {{40,42},{36,40},{32,35},{27,31},{22,26},{19,21},{15,18},{11,12},{5,8},{0,2}}
{{2,5},{8,11},{12,15},{18,19},{21,22},{26,27},{31,32},{35,36},{40,40}}
2 | {{2,4},{36,40},{32,35},{27,31},{22,26},{19,21},{15,18},{11,12},{5,8},{0,2}}
{{4,5},{8,11},{12,15},{18,19},{21,22},{26,27},{31,32},{35,36},{40,40}}
3 | {{2,4},{36,40},{32,35},{27,31},{22,26},{19,21},{15,18},{11,12},{5,8},{0,2}}
{{4,5},{8,11},{12,15},{18,19},{21,22},{26,27},{31,32},{35,36},{40,40}}
4 | {{2,4},{36,40},{8,11},{27,31},{22,26},{19,21},{15,18},{11,12},{5,8},{0,2}}
{{4,5},{11,11},{12,15},{18,19},{21,22},{26,27},{31,32},{35,36},{40,40}}
5 | {{2,4},{36,40},{8,11},{27,31},{22,26},{19,21},{15,18},{11,12},{5,8},{0,2}}
{{4,5},{11,11},{12,15},{18,19},{21,22},{26,27},{31,32},{35,36},{40,40}}
6 | {{2,4},{36,40},{8,11},{27,31},{22,26},{19,21},{15,18},{11,12},{5,8},{0,2}}
{{4,5},{11,11},{12,15},{18,19},{21,22},{26,27},{31,32},{35,36},{40,40}}
7 | {{2,4},{36,40},{8,11},{27,31},{22,26},{12,14},{15,18},{11,12},{5,8},{0,2}}
{{4,5},{11,11},{14,15},{18,19},{21,22},{26,27},{31,32},{35,36},{40,40}}
8 | {{2,4},{36,40},{8,11},{27,31},{22,26},{12,14},{15,18},{11,12},{5,8},{0,2}}
{{4,5},{11,11},{14,15},{18,19},{21,22},{26,27},{31,32},{35,36},{40,40}}
9 | {{2,4},{36,40},{8,11},{27,31},{22,26},{12,14},{15,18},{4,5},{5,8},{0,2}}
{{5,5},{11,11},{14,15},{18,19},{21,22},{26,27},{31,32},{35,36},{40,40}}
10 | {{2,4},{36,40},{8,11},{27,31},{22,26},{12,14},{15,18},{4,5},{5,8},{0,2}}
{{5,5},{11,11},{14,15},{18,19},{21,22},{26,27},{31,32},{35,36},{40,40}}
11 | {{2,4},{36,40},{8,11},{27,31},{22,26},{12,14},{15,18},{4,5},{5,8},{0,2}}
{{5,5},{11,11},{14,15},{18,19},{21,22},{26,27},{31,32},{35,36},{40,40}}
Собственно, на последнем шаге мы и получаем целевое расположение файлов, которые необходимо пронумеровать в обратном порядке и пронумеровать каждый его сегмент:
SELECT
sum(fid * i) -- контрольная сумма
FROM
(
SELECT
segfile -- состояние после последнего переноса
FROM
r
ORDER BY
i DESC
LIMIT 1
) T
, array_length(segfile, 1) files -- общее количество файлов
, generate_series(
files - 1
, 0
, -1
) fid -- нумерация файлов в обратном порядке
, generate_series(
segfile[files - fid][1]
, segfile[files - fid][2] - 1
) i; -- нумерация блоков внутри файла
Итоговый запрос принимает следующий вид:
WITH RECURSIVE map AS (
SELECT
sz::integer -- размер сегмента
, n -- порядковый номер сегмента
, CASE
WHEN n % 2 = 1 THEN n / 2
END fid -- ID файла
, sum(sz::bigint) OVER(ORDER BY n) - sz::bigint pos -- позиция начала сегмента
FROM
regexp_split_to_table( -- разбиение в таблицу ...
'2333133121414131402'
, '' -- ... по отдельным символам
)
WITH ORDINALITY T(sz, n)
)
, seg AS MATERIALIZED (
SELECT
array_agg(ARRAY[pos, pos + sz]::integer[] ORDER BY n DESC)
FILTER(WHERE fid IS NOT NULL) segfile -- карта файлов
, array_agg(ARRAY[pos, pos + sz]::integer[] ORDER BY n)
FILTER(WHERE fid IS NULL) segfree -- карта свободных сегментов
FROM
map
)
, r AS (
SELECT
1 i
, *
FROM
seg
UNION ALL
SELECT
i + 1
, coalesce(T.segfile, r.segfile) -- если нашли возможный перенос для файла - используем его ...
, coalesce(T.segfree, r.segfree) -- ... если нет - сохраняем прежние состояния
FROM
r
LEFT JOIN
LATERAL (
SELECT -- реконструкция массивов-карт с учетом переноса
segfile[:i - 1]
|| ARRAY[segfree[j][1], segfree[j][1] + segfile[i][2] - segfile[i][1]]
|| segfile[i + 1:] segfile
, segfree[:j - 1]
|| ARRAY[segfree[j][1] + segfile[i][2] - segfile[i][1], segfree[j][2]]
|| segfree[j + 1:] segfree
FROM
generate_subscripts(segfree, 1) j -- перебор свободных сегментов
WHERE
segfree[j][1] < segfile[i][1] AND -- проверка возможности переноса
segfree[j][2] - segfree[j][1] >= segfile[i][2] - segfile[i][1]
LIMIT 1 -- ищем до первой возможности
) T
ON TRUE
WHERE
i <= array_length(r.segfile, 1) -- ограничиваемся количеством файлов
)
SELECT
sum(fid * i) -- контрольная сумма
FROM
(
SELECT
segfile -- состояние после последнего переноса
FROM
r
ORDER BY
i DESC
LIMIT 1
) T
, array_length(segfile, 1) files -- общее количество файлов
, generate_series(
files - 1
, 0
, -1
) fid -- нумерация файлов в обратном порядке
, generate_series(
segfile[files - fid][1]
, segfile[files - fid][2] - 1
) i; -- нумерация блоков внутри файла
Логично, что в этот раз вычисления заняли побольше времени - порядка 22.5 секунд, а 90% времени - поиски подходящего для переноса сегмента:
Этот момент, конечно, тоже можно оптимизировать, раскладывая свободные сегменты "на кучки" по длине, и сразу вместо перебора брать первый из сегментов длины не меньше необходимой. Но на SQL этот вариант не дает существенной оптимизации из-за слишком больших накладных расходов из-за "протаскивания" большого количества записей с массивами сквозь рекурсию.
nickolaym
Это нужно в хаб "ненормальное программирование"! :)
Не стал вчитываться в решение, но заценил размах замысла. Красотища.