Pull to refresh

Comments 30

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

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

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


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

Такова жизнь.)))
Можно не делать отдельно 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;

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

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

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

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

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


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


да?

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

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

Спасибо за пример. Сейчас буду пробовать.
А задачку помню по старой, старой книжке «Этюды по программированию». Вот набрать бы примеров подобных задач по декларативного программированию.
Для меня например главная проблема программирования на pl/pgSQL — использовать декларативный подход к решению.
Два примера уже есть.
Может, кто ещё подкинет?
Вам хочется еще малопонятных 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;
А что было в Университете Бесполезных Знаний #404?
Тоже делал Жизнь SQL-запросом, только поле хранится в строке и количество соседей вычисляется смещениями, без join. Все поколения вычисляются и выводятся в пределах одного запроса, без внешних циклов. Количество соседей + сама клетка с весом 9 представляются в восемнадцатеричной системе счисления, чтобы значение поместилось в один знак. Законы рождения / смерти клетки прописаны в константе в translate, можно менять.

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

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

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

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

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

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

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

Телефоном можно тоже гвозди забивать!
Only those users with full accounts are able to leave comments. Log in, please.

Information

Founded
Location
Россия
Website
www.postgrespro.ru
Employees
51–100 employees
Registered
Representative
Иван Панченко

Habr blog