SQL HowTo: оконные функции (Advent of Code 2024, Day 22: Monkey Market)

[z_serg]

Здравствуйте!

В части №2 решение выбрано для демонстрации возможностей оконок? Вроде как более очевидное и быстрое решение, это иметь массив с последними изменениями внутри рекурсии.

[Kilor]

Не факт, что оно будет как-то существенно быстрее - это же на каждом шаге рекурсии к каждому массиву надо приписывать значение в конец и отбрасывать первое, если я понял идею правильно.

[z_serg]

WITH RECURSIVE r AS 
(
	WITH nums AS 
	(
	  SELECT
	    line[1]::int8 secret,
	    client
	  FROM
	    regexp_matches(
$$
1
2
3
2024
$$
	    , '[^\r\n]+(?=$|[\r\n])'
	    , 'g'
	    ) WITH ORDINALITY nums(line,client) 
    )
    SELECT 
    	client,
    	secret,
    	null::int2[] AS last_changes,
    	0 AS cnt
    FROM 
    	nums 
    UNION ALL 
    SELECT 
    	client,
    	secret3,
    	(secret3 % 10 - secret % 10)::int2 || last_changes[1:3],
    	cnt + 1 
    FROM 
    	r,
    	LATERAL 
    	(SELECT ((secret * 64) # secret) % 16777216) AS seq1(secret1),
    	LATERAL
     	(SELECT ((secret1 / 32) # secret1) % 16777216) AS seq2(secret2),
     	LATERAL
    	(SELECT ((secret2 * 2048) # secret2) % 16777216) AS seq3(secret3)
    WHERE 
    	cnt < 2000
)
SELECT 
	sum(price)
FROM 
(
SELECT DISTINCT ON (client,last_changes)
	client,
	secret % 10 AS price,
	last_changes
FROM 
	r
WHERE 
	cnt > 3
ORDER BY 
	client,
	last_changes,
	cnt,
	price DESC
 ) AS q 
GROUP BY 
	last_changes
ORDER BY 
	sum(price) DESC 
LIMIT 1;

Получилось ~1.5 раза, 9сек вместо 13

[Kilor]

Согласен, так можно, только last_changes получается "развернутым" относительно условия. Но вроде на ответ это повлиять не должно.

Если взглянуть на этот кусок плана, то на блоке с парой WindowAgg так можно сэкономить:

Дальше лишь вопрос в длине массива-последовательности - при больших размерах операции над массивами становятся очень уж небыстрыми.