Penggunaan alat khusus untuk keperluan lain seringkali menimbulkan tanggapan negatif dari para profesional. Namun, menyelesaikan tugas yang tidak berarti tetapi menarik melatih pemikiran lateral dan memungkinkan Anda menjelajahi alat dari berbagai sudut pandang untuk mencari solusi yang sesuai.
Dan selanjutnya. Jujur saja: selalu menggunakan SQL untuk tujuan yang dimaksudkan adalah kebosanan yang hijau. Ingat contoh apa yang diberikan di semua buku teks, dimulai dengan artikel yang sama oleh Codd ? Pemasok dan suku cadang, karyawan dan departemen ... Di mana kesenangannya, di mana kesenangannya? Bagi saya, salah satu sumber inspirasi adalah membandingkan solusi prosedural versus deklaratif.
Izinkan saya tidak menjelaskan apa itu Life of John Conway. Saya hanya akan mengatakan bahwa - ternyata - dengan menggunakan otomat seluler Life , Anda dapat membuat mesin Turing universal. Menurut saya ini adalah fakta yang luar biasa.
Jadi, apakah mungkin menerapkan game Life dengan satu pernyataan SQL?
Oke, mari kita mulai.
Bidang kita akan menjadi tabel dengan koordinat sel hidup, dan sama sekali bukan larik dua dimensi, seperti yang mungkin Anda pikirkan dengan terburu-buru. Tampilan ini lebih natural untuk SQL, ini menyederhanakan kode dan memungkinkan Anda untuk tidak memikirkan batas bidang. Selain itu, kecepatan kalkulasi (yang, bagaimanapun, hampir tidak membuat kita khawatir di sini) hanya akan bergantung pada jumlah sel hidup, dan bukan pada ukuran lapangan.
Berbicara tentang matriks
, :
, , — . , A(L×M) B(M×N) (L×N), ci,j = ∑k = 1...M ai,k × bk,j.
i, j, k. 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;
. . : . . .
, , , . .
Jadi bidangnya:
CREATE TABLE cells(
x integer,
y integer
);
INSERT INTO cells VALUES
(0,2), (1,2), (2,2), (2,1), (1,0); -- glider
Untuk menghitung tetangga, alih-alih memutar loop prosedural, mari kita pindahkan "matriks" kita satu sel ke delapan arah dan jumlahkan jumlah sel hidup di setiap posisi.
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;
Pergeseran juga dapat dibuat dengan kueri, tetapi mungkin tidak akan membuatnya lebih mudah.
Karena memiliki tetangga, tinggal memutuskan sel mana yang harus mati dan mana yang harus dilahirkan:
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;
Hubungan yang lengkap diperlukan di sini agar, di satu sisi, kehidupan baru dapat muncul di sel yang kosong, dan di sisi lain, untuk menghancurkan sel-sel hidup "di pinggiran kota". Kami memiliki tiga kondisi untuk masuk ke sampel: apakah sel kosong dan tepat tiga tetangga (kemudian harus hidup dan menerima status BARU), atau masih hidup dan memiliki dua atau tiga tetangga (kemudian bertahan dan menerima status TETAP), atau masih hidup, tapi memiliki kurang dari dua atau lebih dari tiga tetangga (kemudian akan mati dan menerima status DIE).
Sekarang kita perlu memperbarui lapangan bermain menggunakan informasi tentang generasi sel baru. Di sinilah kapabilitas PostgreSQL berguna: kita akan melakukan semua yang kita butuhkan dalam pernyataan SQL yang sama.
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');
Sebenarnya, semua logika permainan sudah tertulis!
Sudah mudah untuk melampirkan pada algoritma ini tampilan hasil dalam bentuk matriks dua dimensi yang familiar di mata. Dan, seperti icing on the cake, Anda bisa mengakhiri kueri dengan perintah psql
\watchsehingga beberapa generasi saling berganti di layar setiap detik.
Berikut ini seluruh kueri, dengan keluaran yang dapat dicerna secara minimal. Salin, tempel, dan nikmatilah!
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