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 は何か処理しているが、いつまでも終わらない。

http://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)
層別集計に範囲型を使う >>
×

この広告は1年以上新しい記事の投稿がないブログに表示されております。