【PostgreSQL】SQLでライフゲームの実装

PostgreSQL Advent Calendar 2012 12/14 です。

ライフゲームとは「生命の誕生、進化、淘汰などのプロセスを簡易的なモデルで再現したシミュレーションゲーム」のことです。
碁盤目状に配置されたセルが、隣接するセルとの関係により、誕生・生存・死滅していく様子をシミュレーションします。

ルールは下記参考
ライフゲーム - Wikipedia

このライフゲームをSQLを使って実装してみます。

データ構造

セルの集合を下記のように表現します。
・１つのセルにつき、１行のレコード
・セルは３つの属性（列）を持つ
　integer x：碁盤の左端から右に何個目か
　integer y：碁盤の上端から下に何個目か
　integer alive：生存状態（生きているセルなら1、死んでいるセルなら0）

データはこれだけです。


初期化

碁盤のサイズ、生存しているセルの割合、を決めてランダムに生成

CREATE TABLE cells AS
SELECT
 x::integer, y::integer
 ,CASE WHEN random() < 0.3 THEN 1 -- 3割のセルが生存
 ELSE 0
 END::integer AS alive
FROM
 generate_series(1,5) t1(x) -- 横のサイズが5
 ,generate_series(1,5) t2(y) -- 縦のサイズが5
;
/*
SELECT * FROM cells;
 x | y | alive 
---+---+-------
 1 | 1 |     1
 1 | 2 |     0
 1 | 3 |     0
 1 | 4 |     0
 1 | 5 |     0
 2 | 1 |     0
 2 | 2 |     0
 2 | 3 |     1
 2 | 4 |     1
 2 | 5 |     0
 3 | 1 |     1
 3 | 2 |     1
 3 | 3 |     1
 3 | 4 |     1
 3 | 5 |     0
 4 | 1 |     0
 4 | 2 |     0
 4 | 3 |     0
 4 | 4 |     0
 4 | 5 |     0
 5 | 1 |     0
 5 | 2 |     0
 5 | 3 |     0
 5 | 4 |     1
 5 | 5 |     0
(25 rows)
*/

描画

初期化したセルから碁盤を描画してみます。
aliveの値をテキストに集約して0,1の文字列で表現しています。

SELECT string_agg(alive_y, E'¥n' ORDER BY y) AS board
FROM(
 SELECT
  y
  ,string_agg(alive::text, '' ORDER BY x) AS alive_y
 FROM cells
 GROUP BY y
)t
;
/*
               board               
-----------------------------------
 10100¥n00100¥n01100¥n01101¥n00000
(1 row)

10100
00100
01100
01101
00000
*/

次世代の生成

まずはSQLを

SELECT
 x, y
 ,(
  SELECT
   CASE WHEN c1.alive = 0 AND c2.alives = 3 THEN 1 -- 誕生
   WHEN c1.alive = 1 AND (c2.alives = 2 OR c2.alives = 3) THEN 1 -- 生存
   ELSE 0 -- 死滅
   END
  FROM(
   SELECT sum(c2.alive) as alives
   FROM cells c2
   WHERE
    NOT(c1.x = c2.x AND c1.y = c2.y) -- 自分自身を除く
    AND
    c1.x BETWEEN c2.x - 1 AND c2.x + 1 -- 横の範囲 
    AND
    c1.y BETWEEN c2.y - 1 AND c2.y + 1 -- 縦の範囲
  )c2
 )::integer AS alive
FROM cells c1
;
/*
 x | y | alive 
---+---+-------
 1 | 1 |     0
 1 | 2 |     0
 1 | 3 |     0
 1 | 4 |     0
 1 | 5 |     0
 2 | 1 |     1
 2 | 2 |     0
 2 | 3 |     0
 2 | 4 |     1
 2 | 5 |     0
 3 | 1 |     0
 3 | 2 |     1
 3 | 3 |     0
 3 | 4 |     1
 3 | 5 |     0
 4 | 1 |     0
 4 | 2 |     1
 4 | 3 |     0
 4 | 4 |     1
 4 | 5 |     0
 5 | 1 |     0
 5 | 2 |     0
 5 | 3 |     0
 5 | 4 |     0
 5 | 5 |     0
(25 rows)


01000
00110
00000
01110
00000
*/

ちょっと解説

次世代のaliveを生成しているサブクエリを具体的なケースに置き換えてみます。
x=2, y=3のセルは次世代で生存しているでしょうか？
サブクエリをc1.x=2, c1.y=3, c1.alive=1で置換したものが下記になります。

  SELECT
   CASE WHEN 1 = 0 AND c2.alives = 3 THEN 1 -- 誕生
   WHEN 1 = 1 AND (c2.alives = 2 OR c2.alives = 3) THEN 1 -- 生存
   ELSE 0 -- 死滅
   END
  FROM(
   -- ここのサブクエリで周囲の生存セル数を計算
   SELECT sum(c2.alive) as alives
   FROM cells c2
   WHERE
    NOT(2 = c2.x AND 3 = c2.y) -- 自分自身を除く
    AND
    2 BETWEEN c2.x - 1 AND c2.x + 1 -- 横の範囲 
    AND
    3 BETWEEN c2.y - 1 AND c2.y + 1 -- 縦の範囲
  )c2

具体的なケースができたら、後は全てのセルに対して同様に処理してやればOKです。

状態を保存する場合はUPDATEするなり、CREATE TABLEするなりしてやりましょう。


まとめ

ライフゲーム？それ、SQLでもできるよ。


Advent Calendar

明日はsakamotomsさんです。



おまけ1

任意の碁盤の状態からcellsを初期化したい場合

CREATE OR REPLACE FUNCTION board_to_cells(board text)
 RETURNS TABLE(x integer, y integer, alive integer)
 AS $$
  SELECT
   row_number() OVER(PARTITION BY y)::integer as x
   ,y::integer
   ,alive::integer
  FROM(
   SELECT
    row_number() OVER() AS y
    ,regexp_split_to_table(alive_y, '') AS alive
   FROM(
    SELECT
     regexp_split_to_table($1, '\n') AS alive_y
   )t
  )t
 $$
LANGUAGE SQL;

/*
SELECT * FROM board_to_cells(E'010\n100\n100');
*/

おまけ2

パフォーマンス実験
手元の環境にて、初期状態が100×100, 生存率3割で試したところ、次世代の計算にかかる時間が20秒強ほど。
もっと高速な実装を考えてみるのも面白いかも。

【JavaScript】【CI】Jasmine + PhantomJS + JenkinsでJavascriptのテスト

Jasmine

JavaScript用のテスティングフレームワーク
使い方は下記等を参考

JasmineによるJavaScriptのテスト その1 « サーバーワークス エンジニアブログ
http://blog.serverworks.co.jp/tech/2010/11/30/jasmine-tutorial-1/

・インストール（というほどのものでもないが）

以下からzipをダウンロード
https://github.com/pivotal/jasmine/downloads

・サンプル

適当なディレクトリに展開してSpecRunner.htmlをブラウザで表示
例）apacheのDocumentRootにjasmineディレクトリを作成
http://localhost/jasmine/SpecRunner.html

テスト結果が表示されればOK

PhantomJS

Headless WebKit with JavaScript API
画面のないwebkitブラウザ

phantomjsを使うことでjsのテストをコマンド実行できる

・インストール

Windowsへのインストールはバイナリがダウンロードできる
http://code.google.com/p/phantomjs/downloads/list

Unix系なら下記参考
http://phantomjs.org/build.html

・サンプル

例）SpecRunner.htmlのテストを実行
SpecRunner.htmlのreporterを変更

実行

/path-to-phantomjs/bin/phantomjs /path-to-phantomjs/examples/run-jasmine.js http://localhost/jasmine/SpecRunner.html
'waitFor()' finished in 200ms.
Player

Jenkins

ソフトウェアのビルドやcronで起動するジョブなどの繰り返しジョブの実行を監視する。

Jenkins - 日本語 - Jenkins Wiki
https://wiki.jenkins-ci.org/display/JA/Jenkins

・インストール

java -jar jenkins.warを実行するか、サーブレットコンテナにデプロイ

例）tomcatにデプロイする場合
/path-to-tomcat/webapps/jenkins.warを配置
http://localhost:8080/jenkinsにアクセス


Phatomjs + Jasmineでテスト結果をJUnit形式のxmlに出力

以下からライブラリをダウンロード
https://github.com/detro/phantomjs-jasminexml-example

phantomjs_jasminexml_runner.jsを/path-to-phantomjs/testに配置
core.jsを/path-to-phantomjs/test/lib/utilsに配置

jasmine.phantomjs-reporter.jsをjasmineのテストhtmlで読み込み、reporterを変更

例）SpecRunner.htmlのテスト結果をxmlに出力
SpecRunner.htmlのreporterを変更

実行

/path-to-phantomjs/bin/phantomjs /path-to-phantomjs/test/phantomjs_jasminexml_runner.js http://localhost/jasmine/SpecRunner.html [path-to-output]

[path-to-output]で指定したディレクトリにTEST-Player.xmlが出力される。


Jenkinsでテストをジョブ登録

Jenkinsの画面から
①新規ジョブの作成を押す
②ジョブ名を入力し、フリースタイル・プロジェクトのビルドを選択してOKを押す
③ビルド→ビルド手順の追加→シェルの実行でテスト実行コマンドを登録

例）SpecRunner.htmlの場合は下記を指定

/path-to-phantomjs/bin/phantomjs /path-to-phantomjs/test/phantomjs_jasminexml_runner.js http://localhost/jasmine/SpecRunner.html $WORKSPACE

$WORKSPACEはjenkinsの環境変数。通常は$JENKINS_HOME/workspace/[job-name]
tomcatにデプロイした場合、$JENKINS_HOMEは$TOMCAT_USER_HOME/.jenkinsがデフォルト

④ビルド後の処理→JUnitテスト結果の集計を選択してテスト結果XMLを指定
  $WORKSPACEに出力している場合は*.xml
⑤設定を保存し、ビルドを実行して動作確認。ビルド履歴からテスト結果等が閲覧できる。
⑥その他、ビルド・トリガで自動実行、ビルド後の処理でメール通知、等を設定

PostgreSQLで統計解析 PL/R 基礎編3 : CRAN(Rライブラリ)利用

CRAN

perlにCPANがあるように、CRANというRのモジュールを公開するネットワークがあり、多くのプログラムが公開されている。
The Comprehensive R Archive Network

下記記事を参考に、PL/RでCRANから取得したモジュールを利用してみる。
zooパッケージを使って行列の欠損値を補間する(R Advent Calendar 2011) - My Life as a Mock Quant


Install R Package

パッケージのinstallはRから

r #R起動
> install.packages("zoo")

Use R Package

パッケージはlibrary(zoo)で読み込み。
行列の欠損を補完する関数を作成

CREATE OR REPLACE FUNCTION na_locf(matrix int4[][]) RETURNS int4[][] AS '
    library(zoo);
    return(na.locf(matrix))
' LANGUAGE 'plr';
SELECT na_locf(ARRAY[ARRAY[1,2,3],ARRAY[4,null,6],ARRAY[7,8,9]]);
-- nullが2で補完される。

CREATE OR REPLACE FUNCTION na_approx(matrix int4[][]) returns int4[][] as ' 
    library(zoo);
    return(0.5 * (na.approx(matrix) + t(na.approx(t(matrix)))))
' LANGUAGE 'plr';
SELECT na_approx(ARRAY[ARRAY[1,2,3],ARRAY[4,null,6],ARRAY[7,8,9]]);
--nullが5で補完される。

PostgreSQLとRのデータ構造の違いに気をつければライブラリの使用は比較的簡単

PostgreSQLで統計解析 PL/R 基礎編2 : R用データ読み込み

前回 に続き、
今回はR用のサンプルデータを読み込んでPostgreSQLのデータとして受け取ってみる。


Test Data

データ集めは下記を参考に
統計を学びたい人へ贈る、統計解析に使えるデータセットまとめ - ほくそ笑む

今回は、世界の48都市の経済状態を記録したデータのcsvを読み込んでみる。


Composite Type Sample

読み込むcsvは文字列と数値が含まれており、Rではデータフレームという形式で読み込まれる。
データフレーム形式のデータはPostgreSQLでは複合型として受け取れる。
PL/Rのマニュアル記載のサンプルは下記の通り。

CREATE TYPE emp AS (
    name text
    ,age int2
    ,salary int4
);
CREATE OR REPLACE FUNCTION get_emps() RETURNS SETOF emp AS '
   names <- c("Joe","Jim","Jon")
   ages <- c(41,25,35)
   salaries <- c(250000,120000,50000)
   df <- data.frame(name = names, age = ages, salary = salaries)
   return(df)
' LANGUAGE 'plr';

SELECT * FROM get_emps();
/*
name | age | salary
text | smallint | integer
------+-----+-----------
Joe | 41 | 250000
Jim | 25 | 120000
Jon | 35 | 50000
*/

複合型を作成するのが手間なので、下記のようにしてみたらうまくいった。

CREATE OR REPLACE FUNCTION get_emps(out name text, out age int4, out salary int4) RETURNS SETOF record AS '
   names <- c("Joe","Jim","Jon")
   ages <- c(41,25,35)
   salaries <- c(250000,120000,50000)
   df <- data.frame(name = names, age = ages, salary = salaries)
   return(df)
' LANGUAGE 'plr';
SELECT * from get_emps();

が、引数を与えた場合はうまく動作しない模様…。
マニュアルにもデータフレームをsetof recordで返せるとは明示されていないので、対応範囲外なのかもしれない。


Get CityEcon

では、本題のcityecon.csvを読み込んでみる。

CREATE TYPE cityecon AS (
    city text
    ,work int4
    ,price float8
    ,salary float8
);
CREATE OR REPLACE FUNCTION get_cityecon(csvpath text) RETURNS setof cityecon AS '
    x <- read.csv(csvpath)
    return(x)
' LANGUAGE 'plr';
SELECT * FROM get_cityecon('/path-to-csv/cityecon.csv');
-- ERROR:  invalid input syntax for integer: "-"

元データにnull値として"-"が入っているためエラー。
Rで"-"をNAに置き換えておく。

CREATE OR REPLACE FUNCTION get_cityecon(csvpath text) RETURNS setof cityecon AS '
    x <- read.csv(csvpath)
    x$Work <- ifelse(x$Work=="-", NA, x$Work) 
    x$Salary <- ifelse(x$Salary=="-", NA, x$Salary) 
    return(x)
' LANGUAGE 'plr';
SELECT * FROM get_cityecon('/path-to-csv/cityecon.csv');
-- OK

さらに、CSV以外のファイル形式にも対応できるようにしてみる。

CREATE OR REPLACE FUNCTION get_cityecon(path text, header boolean, separator text) RETURNS setof cityecon AS '
    if(is.null(separator)){
        sep <- ""
    } else sep <- separator    
    if(header){
        x <- read.table(path, header = T, sep = sep)
    }else{
        x <- read.table(path, header = F, sep = sep)
    }
    x$Work <- ifelse(x$Work=="-", NA, x$Work) 
    x$Salary <- ifelse(x$Salary=="-", NA, x$Salary) 
    return(x)
' LANGUAGE 'plr';
SELECT * FROM get_cityecon('/path-to-csv/cityecon.csv', true, ',')
-- OK

データの区切り文字とヘッダーが含まれるかどうかを指定可能。

読み込むデータに合わせて複合型を作成したり、NULL値の変換をしたりと結構めんどくさい。
もうちょっと簡単に読み込みたいなあという感想。