«Жизнь» на PostgreSQL

    Недавно на Хабре была опубликована статья Морской бой в PostgreSQL. Должен признаться: я обожаю решать на SQL задачи, для SQL не предназначенные. Особенно одним SQL-оператором. И полностью согласен с авторами:

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

    И еще. Будем честны: всегда использовать SQL по назначению — тоска зеленая. Вспомните, какие примеры приводятся во всех учебниках, начиная с той самой статьи Кодда? Поставщики да детали, сотрудники да отделы… А где же удовольствие, где же фан? Для меня один из источников вдохновения — сравнение процедурных решений с декларативными.

    Я, позвольте, не буду объяснять, что такое Жизнь Джона Конвея. Скажу только, что — оказывается — используя клеточный автомат Жизни, можно построить универсальную машину Тьюринга. Мне кажется, это грандиозный факт.

    Так вот, можно ли реализовать игру Жизнь одним оператором SQL?

    Окей, приступим.

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

    Кстати о матрицах
    Такое же представление удобно использовать для представления матриц, особенно разреженных:

    CREATE TABLE matrix (
      rw  integer,
      cl  integer,
      val float
    );
    

    Простой пример, эффективно взрывающий процедурно настроенный мозг, — умножение матриц. Напомню, что произведением матрицы A(L×M) на матрицу B(M×N) является матрица С(L×N), элементы которой ci,j = ∑k = 1...M  ai,k × bk,j.

    Процедурный алгоритм использует тройной вложенный цикл по i, j, k. А SQL-запросу достаточно простого соединения:

    SELECT a.rw, b.cl, sum(a.val * b.val)
    FROM a
        JOIN b ON a.cl = b.rw
    GROUP BY a.rw, b.cl;
    

    Запрос стоит внимательно изучить и понять. С непривычки это совсем даже непросто. Здесь нет циклов: запрос оперирует множествами элементов и их соединением. Здесь нет размерности матрицы. Здесь не нужно хранить в таблице нулевые элементы.

    Но после того, как мозг взорвался, код ставится очевидным и ничуть не более сложным, чем процедурный. Это важный момент.

    Итак, поле:

    CREATE TABLE cells(
        x integer,
        y integer
    );
    INSERT INTO cells VALUES
        (0,2), (1,2), (2,2), (2,1), (1,0); -- glider
    

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

    WITH shift(x,y) AS (
        VALUES (0,1), (0,-1), (1,0), (-1,0), (1,1), (1,-1), (-1,1), (-1,-1)
    ),
    neighbors(x,y,cnt) AS (
        SELECT t.x, t.y, count(*)
        FROM (
            SELECT c.x + s.x, c.y + s.y
            FROM cells c
                CROSS JOIN shift s
        ) t(x,y)
        GROUP BY t.x, t.y 
    )
    SELECT * FROM neighbors;
    

    Сдвиги (shift) тоже можно сконструировать запросом, но, пожалуй, проще от этого не станет.

    Имея соседей, остается решить, какие клетки должны погибнуть, а какие — родиться:

    WITH shift(x,y) AS (
        ...
    ),
    neighbors(x,y,cnt) AS (
        ...
    ),
    generation(x,y,status) AS (
        SELECT coalesce(n.x,c.x),
               coalesce(n.y,c.y),
               CASE
                    WHEN c.x IS NULL THEN 'NEW'
                    WHEN n.cnt IN (2,3) THEN 'STAY'
                    ELSE 'DIE'
               END
        FROM neighbors n
            FULL JOIN cells c ON c.x = n.x AND c.y = n.y
        WHERE (c.x IS NULL AND n.cnt = 3)
              OR
              (c.x IS NOT NULL)
    )
    SELECT * FROM generation;
    

    Полное соединение здесь необходимо, чтобы, с одной стороны, в пустой клетке могла зародиться новая жизнь, а с другой — чтобы погубить живые клетки «на отшибе». У нас три условия попадания в выборку: либо клетка пуста и у нее ровно три соседа (тогда она должна ожить и получает статус NEW), либо жива и имеет двух или трех соседей (тогда она выживает и получает статус STAY), либо жива, но имеет меньше двух или более трех соседей (тогда она обречена на гибель и получает статус DIE).

    Теперь надо обновить игровое поле, используя информацию о новом поколении клеток. Вот тут-то нам и пригодятся возможности PostgreSQL: мы сделаем все необходимое в том же операторе SQL.

    WITH shift(x,y) AS (
        ...
    ),
    neighbors(x,y,cnt) AS (
        ...
    ),
    generation(x,y,status) AS (
        ...
    ),
    del AS ( 
        DELETE FROM cells
        WHERE (x,y) IN (
            SELECT x, y FROM generation WHERE status = 'DIE'
      )
    ),
    ins AS (
        INSERT INTO cells
            SELECT x, y FROM generation WHERE status = 'NEW'
    )
    SELECT *
    FROM generation
    WHERE status IN ('STAY','NEW');
    

    Собственно, вся логика игры написана!

    К этому алгоритму уже нетрудно прикрутить отображение результата в виде привычной глазу двумерной матрицы. И, как вишенкой на торте, можно закончить запрос командой psql \watch, чтобы поколения сменяли друг друга на экране каждую секунду.

    Вот весь запрос целиком с минимально удобоваримым выводом. Copy, paste, and enjoy!

    WITH shift(x,y) AS (
        VALUES (0,1), (0,-1), (1,0), (-1,0), (1,1), (1,-1), (-1,1), (-1,-1)
    ),
    neighbors(x,y,cnt) AS (
        SELECT t.x, t.y, count(*)
        FROM (
            SELECT c.x + s.x, c.y + s.y
            FROM cells c
                CROSS JOIN shift s
        ) t(x,y)
        GROUP BY t.x, t.y 
    ),
    generation(x,y,status) AS (
        SELECT coalesce(n.x,c.x),
               coalesce(n.y,c.y),
               CASE
                    WHEN c.x IS NULL THEN 'NEW'
                    WHEN n.cnt IN (2,3) THEN 'STAY'
                    ELSE 'DIE'
               END
        FROM neighbors n
            FULL JOIN cells c ON c.x = n.x AND c.y = n.y
        WHERE (c.x IS NULL AND n.cnt = 3)
              OR
              (c.x IS NOT NULL)
    ),
    del AS ( 
        DELETE FROM cells
        WHERE (x,y) IN (
            SELECT x, y FROM generation WHERE status = 'DIE'
      )
    ),
    ins AS (
        INSERT INTO cells
            SELECT x, y FROM generation WHERE status = 'NEW'
    ),
    dimensions(x1,x2,y1,y2) AS (
        SELECT min(x), max(x), min(y), max(y)
        FROM generation
        WHERE status IN ('STAY','NEW')
    )
    SELECT string_agg(CASE WHEN g.x IS NULL THEN ' ' ELSE '*' END, '' ORDER BY cols.x)
    FROM dimensions d
        CROSS JOIN generate_series(d.x1,d.x2) cols(x)
        CROSS JOIN generate_series(d.y1,d.y2) lines(y)
        LEFT JOIN generation g ON g.x = cols.x AND g.y = lines.y AND g.status IN ('STAY','NEW')
    GROUP BY lines.y
    ORDER BY lines.y
    \watch 1
    
    Postgres Professional
    Разработчик СУБД Postgres Pro

    Похожие публикации

    Комментарии 30

      +9
      Вот статья 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)
        +1

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

          0

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


          ВЫБРАТЬ
          ИЗ популяция
          ИМЕЮЩИЕ СУММА
          ИНАЧЕ КОНЕЦ```
          
          Такова жизнь.)))
          +1
          Можно не делать отдельно 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;
            0

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

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

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

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

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


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


                  да?

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

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

                    0

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

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

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

                      0
                      А что было в Университете Бесполезных Знаний #404?
                  +1
                  Мсье знает толк™
                    0

                    Отож.

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

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

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

                      +1
                      Хочу присоединиться к теме со своей поделкой и наброском на тему Телеграм бота выполненного в Postgresql тут
                        0
                        напишите статью тут, а то тот сайт не всегда открывается
                        я подобное делал, только проще, без pl-python, а с помощью pg_curl и pg_task
                          0
                          да я думал уже тоже поделиться и тут. вот соберу мысли в кучу и напишу. спасибо за отклик и плюс. pg_curl и pg_task буду смотреть. я ещё сейчас экспериментирую с apach->flask(wsgi)->pg. пока мне нравятся мои эксперименты
                        0

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

                          +1

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

                            0

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

                              0

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

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

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

                          Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                          Самое читаемое