«Жизнь» на PostgreSQL

[Ildarovich]

Вот статья 2011 года: Игра «Жизнь» в одном запросе,
где та же задача решена на языке запросов платформы 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)

[erogov]

О, прикольно. Собственно, идея ровно та же самая, с точностью до деталей реализации.
А вот использовать нулевой сдвиг и арифметику вместо статусов — это вы здорово придумали, это красиво.

[o_O_Tync]

Алгоритм гопника получается:

ВЫБРАТЬ
ИЗ популяция
ИМЕЮЩИЕ СУММА
ИНАЧЕ КОНЕЦ```

Такова жизнь.)))

[Kilor]

Можно не делать отдельно 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;

[erogov]

Но ведь так тот же глайдер будет оставлять за собой бесконечный след из мертвых клеток? Нехорошо.
А вот одно соединение у меня лишнее, это факт.

[Kilor]

Нет, не будет — они «обнуляются» и не рисуются.

[erogov]

Не рисуются — это понятно, но в таблице-то остаются мусором.
А в остальном красиво, да.

[Kilor]

но в таблице-то остаются мусором

Спору нет. В этом варианте еще и undead-клетки (v = 0) плодятся во все стороны, хоть и не видны.

[ifinik]

но ведь тогда не будет самого интересного:

К тому же скорость расчетов (которая, правда, вряд ли нас тут сильно волнует) будет зависеть только от числа живых клеток, а не от размеров поля.

да?

[Kilor]

Скажем так, в этом варианте от размеров поля тоже ничего не зависит, но зависит еще и от количества не вполне живых. :)

[gurux13]

Ну, кстати, умножение матриц из статьи тоже не чистит нули :)

[erogov]

А и действительно, having не помешал бы.

[rinace]

Спасибо за пример. Сейчас буду пробовать.
А задачку помню по старой, старой книжке «Этюды по программированию». Вот набрать бы примеров подобных задач по декларативного программированию.
Для меня например главная проблема программирования на pl/pgSQL — использовать декларативный подход к решению.
Два примера уже есть.
Может, кто ещё подкинет?

[Kilor]

Вам хочется еще малопонятных SQL? Их есть у меня! :)
Это предыдущий вариант, но чуть быстрее за счет отсутствия разрастания не-живых клеток во все стороны:

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;

[erogov]

Все мои заметки на эту тему вот тут. Но они старые, там оракл еще.

[Igor_Le]

А что было в Университете Бесполезных Знаний #404?

[erogov]

Да там много всякого было, но сайт больше не алё.
И даже машина времени почему-то ничего не показывает.

[hard_sign]

Мсье знает толк™

[erogov]

Отож.

[igormu]

Тоже делал Жизнь SQL-запросом, только поле хранится в строке и количество соседей вычисляется смещениями, без join. Все поколения вычисляются и выводятся в пределах одного запроса, без внешних циклов. Количество соседей + сама клетка с весом 9 представляются в восемнадцатеричной системе счисления, чтобы значение поместилось в один знак. Законы рождения / смерти клетки прописаны в константе в translate, можно менять.

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

[erogov]

Тоже вариант. На мой вкус несколько менее "SQL way", но SQL многообразен.

[kraser]

Хочу присоединиться к теме со своей поделкой и наброском на тему Телеграм бота выполненного в Postgresql тут

[RekGRpth]

напишите статью тут, а то тот сайт не всегда открывается
я подобное делал, только проще, без pl-python, а с помощью pg_curl и pg_task

[kraser]

да я думал уже тоже поделиться и тут. вот соберу мысли в кучу и напишу. спасибо за отклик и плюс. pg_curl и pg_task буду смотреть. я ещё сейчас экспериментирую с apach->flask(wsgi)->pg. пока мне нравятся мои эксперименты

[TimeCoder]

Главный вопрос: а какая итоговая скорость?

[erogov]

Кто ж ее измерял. Простенькие фигуры — моментально, а большие инсталляции я не пробовал.
Разве ж это главное в ненормальном программировании?

[TimeCoder]

Вопрос не праздный) если вдруг я (или кто-то ещё) захочет запустить симуляцию Жизни на ну очень большом поле, то какое решение, хотя бы в теории, сулит максимальную скорость: мощная СУБД где-то в облаке, или, к примеру, крутая мощная видеокарта (считать на ней, конечно, не рисовать), вот что интересно.

[erogov]

Ну очевидно СУБД проиграет. Общие алгоритмы, на клеточные автоматы не заточенные, это раз, и много "ненужной" работы, связанной с транзакциями, два.
Тут что-то массивно-параллельное хорошо должно работать по идее.

[igormu]

FPGA или ASIC выиграют однозначно.

[den_labs]

И еще. Будем честны: всегда использовать SQL по назначению — тоска зеленая.

Телефоном можно тоже гвозди забивать!