2014/09/01
PostgreSQL >  順列生成の PL/pgSQL と再帰クエリ
最近 PL/pgSQL を余り書いていない。文法を忘れないよう、試しに R の順列生成関数（e1071 というパッケージにある permutations）を PL/pgsql のストアド関数で真似てみた。実行環境は 2014/08/13 の実機を参照。permutations のソースは ↓ のとおり短い。結果は matrix 型になるが、PL/pgSQL ストアドでは一次元配列の複数行で返すようにした。


↓ こんなに長くなってしまった。R の行列操作の代わりに、二次元配列を一要素ずつループして代入するため。最後に値を返す際、配列の次元を簡単に二次 → 一次に変えられないので文字列にして両端の { と } を削っている。
CREATE OR REPLACE FUNCTION "201409"."permutations"(int)
RETURNS setof int[] LANGUAGE plpgsql IMMUTABLE AS $BODY$
DECLARE
	-- same as R
	n int = $1 ;
	z int[][] = '{{1}}' ;
	x int[][] ;
	a int[] ;
	i int ;
	j int ;

	-- add in this function
	r1 int ;
	r2 int ;
	c int ;
BEGIN
IF n = 1 THEN
	RETURN NEXT ARRAY[1] ;
	RETURN ;
END IF ;
FOR i IN 2..n LOOP
	-- R : "x = cbind(z, i)"
	x = replace(concat('{', repeat(concat('{'
		, repeat('0,', array_length(z, 2) + 1), '},')
			, array_length(z, 1)), '}'), ',}', '}') :: int[][] ;
	FOR r1 IN 1..array_length(x, 1) LOOP
		FOR c IN 1..array_length(x, 2) LOOP
			x[r1][c] = CASE WHEN c > array_length(z, 2) THEN i
					ELSE z[r1][c] END ;
		END LOOP ;
	END LOOP ;

	-- R : "a = c(1:i, 1:(i - 1))"
	a = (SELECT array_agg(generate_series) FROM (
		SELECT generate_series(1, i)
		UNION ALL SELECT generate_series(1, i - 1)
	) foo) ;

	-- R : "z = matrix(0, ncol = ncol(x), nrow = i * nrow(x))"
	z = replace(concat('{', repeat(concat('{'
		, repeat('0,', array_length(x, 2)), '},')
			, i * array_length(x, 1)), '}'), ',}', '}') :: int[][] ;

	-- R : "z[1:nrow(x), ] = x"
	FOR r1 IN 1..array_length(x, 1) LOOP
		FOR c IN 1..array_length(x, 2) LOOP
			z[r1][c] = x[r1][c] ;
		END LOOP ;
	END LOOP ;

	FOR j IN 1..(i - 1) LOOP
		-- R : "z[j * nrow(x) + 1:nrow(x), ] = x[, a[1:i + j]]"
		r2 = 1 ;
		FOR r1 IN (j * array_length(x, 1) + 1)
			..(j * array_length(x, 1) + array_length(x, 1)) LOOP
			FOR c IN 1..array_length(z, 2) LOOP
				z[r1][c] = x[r2][a[c+j]] ;
				-- RAISE INFO 'r1=%, c=%', r1, c ;
			END LOOP ;
			r2 = r2 + 1 ;
		END LOOP ;
	END LOOP ;
END LOOP ;
FOR r1 IN 1..array_length(z, 1) LOOP
	RETURN NEXT right(left(z[r1:r1][1:n] :: text, -1), -1) :: int[] ;
END LOOP ;
END ;
$BODY$ ;

-- Example
SELECT "201409"."permutations"(6) ;


一応動いたと思ったが、なぜか引数を 8 以上にするといつまでも結果が出ない。配列のサイズが大きくなり過ぎるのだろうか。その様子を動画 ↓ で記録した。まず 1〜6 の順列は 0.3 秒ででき、1〜7 も 2.5 秒かかったが一応できる。しかし 8 を渡すと、配列操作のループの途中から先へ進まない。止まった訳でなく CPU は何か処理しているが、いつまでも終わらない。

https://kenpg.up.seesaa.net/image/20140901_sql_2.flv



行列操作を中心にした R の関数をそのまま PL/pgSQL で真似るのは無理があるのだろう。順列生成については以前 ↓ 再帰クエリで実装したので、それを使って書き直す。

■ 2014/03/24 PostgreSQL : 順列の列挙（3）クエリ微修正、速度比較
http://kenpg.seesaa.net/article/392258681.html

記事の再帰クエリを、重複のない 1〜n の順列に特化してストアド化した。↓ 使い方、結果の型は先ほどの PL/pgSQL と同じ。
CREATE OR REPLACE FUNCTION "201409"."permutations_sql"(int)
RETURNS setof int[] language sql IMMUTABLE AS $BODY$
WITH RECURSIVE r AS (
	SELECT $1 len, array_agg(sub) ar1, NULL :: int[] ar2
	FROM generate_series(1, $1) sub
	UNION ALL
	SELECT len - 1, array_remove(ar1, unnest), ar2 || unnest
	FROM r, unnest(ar1)
	WHERE len > 1
)
SELECT ar2 || ar1 FROM r WHERE len = 1 ;
$BODY$ ;

-- Example
SELECT "201409"."permutations_sql"(9) LIMIT 1000 ;

↓ ストアド関数のテスト。1〜9 の全順列（362,880 行）を生成し、先頭 1000 行を表示。所要時間は 578 ミリ秒（二番目の画像）。



↓ もう一つテスト。1〜9 の全順列を生成し一つのテーブルに保存する場合。362,880 行あるので 2 秒ちょっとかかった。テーブルサイズは 32 MB（二番目の画像）。


<< SVG のパスを取り込む（1）
層別集計に範囲型を使う >>