Comments 30
где та же задача решена на языке запросов платформы 1С: Предприятие,
который по сути — тот же SQL.
Запрос там поместился на восьми строчках:
ВЫБРАТЬ Клетки.Х, Клетки.У ПОМЕСТИТЬ Популяция ИЗ &Популяция КАК Клетки
;
ВЫБРАТЬ -1 КАК Шаг ПОМЕСТИТЬ Дельта ОБЪЕДИНИТЬ ВЫБРАТЬ 0 ОБЪЕДИНИТЬ ВЫБРАТЬ 1
;
ВЫБРАТЬ Х + Вправо.Шаг КАК Х, У + Вниз.Шаг КАК У
ИЗ Популяция, Дельта КАК Вправо, Дельта КАК Вниз
СГРУППИРОВАТЬ ПО Х + Вправо.Шаг, У + Вниз.Шаг
ИМЕЮЩИЕ СУММА(ВЫБОР КОГДА Вправо.Шаг = 0 И Вниз.Шаг = 0 ТОГДА 9 ИНАЧЕ 1 КОНЕЦ) В (3, 11, 12)
Или на английском:
SELECT Клетки.Х AS Х, Клетки.У AS У INTO Популяция FROM &Популяция AS Клетки
;
SELECT -1 AS Шаг INTO Дельта UNION SELECT 0 UNION SELECT 1
;
SELECT Популяция.Х + Вправо.Шаг AS Х, Популяция.У + Вниз.Шаг AS У
FROM Популяция AS Популяция, Дельта AS Вправо, Дельта AS Вниз
GROUP BY Популяция.Х + Вправо.Шаг, Популяция.У + Вниз.Шаг
HAVING SUM(CASE WHEN Вправо.Шаг = 0 AND Вниз.Шаг = 0 THEN 9 ELSE 1 END) IN (3, 11, 12)
INSERT/DELETE
, а вместо них использовать ON CONFLICT
, если расширить ячейку ее статусом:CREATE TABLE cells(
x integer
, y integer
, v integer -- 1 - "живая" клетка
, PRIMARY KEY (x, y)
);
-- заполняем матрицу по картинке
INSERT INTO cells
SELECT
x - 1 x
, y - 1 y
, (v <> ' ')::integer v
FROM
(VALUES(
$$
*
*
***
$$ -- image
)) T(s)
, LATERAL(
SELECT regexp_split_to_array(s, '\n') lines
) Y
, LATERAL unnest(lines[2 : array_length(lines, 1) - 1]) WITH ORDINALITY AS L(line, y)
, LATERAL regexp_split_to_table(line, '') WITH ORDINALITY AS C(v, x);
-- моделируем новое поколение, отображая предыдущее
WITH n AS ( -- каждая "живая" клетка добавляет +1 каждому своему соседу
SELECT
x + dx x
, y + dy y
, count(*) n
FROM
cells c
, generate_series(-1, 1) dx
, generate_series(-1, 1) dy
WHERE
dx ^ 2 + dy ^ 2 > 0 AND -- только "соседи", без центральной клетки
v > 0 -- отбираем только "живые"
GROUP BY
1, 2
)
, ins AS ( -- заменяем состояние всех ячеек
INSERT INTO
cells
SELECT
x
, y
, CASE
WHEN n = 2 THEN NULL -- 2 соседа - состояние не меняется
WHEN n = 3 THEN 1 -- 3 соседа - рождается
ELSE 0 -- во всех остальных случаях - гибнет
END v
FROM
n
ON CONFLICT(x, y)
DO UPDATE SET v = coalesce(EXCLUDED.v, cells.v) -- NULL сохраняет состояние
)
SELECT
string_agg(CASE WHEN v > 0 THEN '*' ELSE ' ' END, '' ORDER BY x)
FROM
(
SELECT
x
, y
FROM
(
SELECT
min(x) xl
, max(x) xr
, min(y) yl
, max(y) yr
FROM
cells
WHERE
v > 0 -- снова отбираем только "живые"
) ranges
, LATERAL generate_series(xl, xr) x
, LATERAL generate_series(yl, yr) y
) T
LEFT JOIN cells
USING(x, y)
GROUP BY
y
ORDER BY
y;
Но ведь так тот же глайдер будет оставлять за собой бесконечный след из мертвых клеток? Нехорошо.
А вот одно соединение у меня лишнее, это факт.
Не рисуются — это понятно, но в таблице-то остаются мусором.
А в остальном красиво, да.
но ведь тогда не будет самого интересного:
К тому же скорость расчетов (которая, правда, вряд ли нас тут сильно волнует) будет зависеть только от числа живых клеток, а не от размеров поля.
да?
Ну, кстати, умножение матриц из статьи тоже не чистит нули :)
А задачку помню по старой, старой книжке «Этюды по программированию». Вот набрать бы примеров подобных задач по декларативного программированию.
Для меня например главная проблема программирования на pl/pgSQL — использовать декларативный подход к решению.
Два примера уже есть.
Может, кто ещё подкинет?
Это предыдущий вариант, но чуть быстрее за счет отсутствия разрастания не-живых клеток во все стороны:
WITH n AS (
SELECT
x + dx x
, y + dy y
, CASE sum(v)
WHEN 2 THEN NULL
WHEN 3 THEN 1
ELSE 0
END v
FROM
cells c
, generate_series(-1, 1) dx
, generate_series(-1, 1) dy
WHERE
abs(dx) + abs(dy) > 0
GROUP BY
1, 2
)
, ins AS (
INSERT INTO
cells
SELECT
n.*
FROM
n
FULL JOIN
cells c
USING(x, y)
WHERE
n.v IS NOT NULL AND
coalesce(c.v, 0) <> coalesce(n.v, 0)
ON CONFLICT(x, y)
DO UPDATE SET v = EXCLUDED.v
)
SELECT
string_agg((coalesce(v, 0) + 32)::"char", '' ORDER BY x)
FROM
(
SELECT
x
, y
FROM
(
SELECT
min(x) xl
, max(x) xr
, min(y) yl
, max(y) yr
FROM
cells
) ranges
, LATERAL generate_series(xl, xr) x
, LATERAL generate_series(yl, yr) y
) g
NATURAL LEFT JOIN
cells
GROUP BY
y
ORDER BY
y;
Да там много всякого было, но сайт больше не алё.
И даже машина времени почему-то ничего не показывает.
Вообще, рекурсивные SQL-запросы Тьюринг-полны, поэтому можно реализовать любую вычислимую функцию.
я подобное делал, только проще, без pl-python, а с помощью pg_curl и pg_task
Главный вопрос: а какая итоговая скорость?
Кто ж ее измерял. Простенькие фигуры — моментально, а большие инсталляции я не пробовал.
Разве ж это главное в ненормальном программировании?
Вопрос не праздный) если вдруг я (или кто-то ещё) захочет запустить симуляцию Жизни на ну очень большом поле, то какое решение, хотя бы в теории, сулит максимальную скорость: мощная СУБД где-то в облаке, или, к примеру, крутая мощная видеокарта (считать на ней, конечно, не рисовать), вот что интересно.
И еще. Будем честны: всегда использовать SQL по назначению — тоска зеленая.
Телефоном можно тоже гвозди забивать!
«Жизнь» на PostgreSQL