Haskell::GR-nの生成(その4)

GR-nの判定方法について考える。
その3までは、(g’∈{GR-(n-1)}, x)から一旦リストを作り、それがGR-nか判定していたが、g’の差集合とxとg’の各要素の差から作られる集合の積が空かどうかで判定するように変更してみる。
g’の差集合はスキャンの過程で何度も求めるが、g’は繰り返し同じ値が現れる。二度目以降は最適化により先の結果が使われることが期待できる。これで、判定の計算コストが低減できないか試してみる。

-- grs.hs
import System
import List
main :: IO ()
main = do { args <- getArgs
; let [n, m] = if length args == 2 then map read args else [4,20]
; putStrLn $ unwords $ map show $ take m $ gr n
}
gr :: Int -> [[Int]]
gr n
| n<1         = []
| n==1        = [[0]]
| n==2        = map (\x -> [0, x]) [1..]
| otherwise   = scanline (gr $ n - 1) 1
where
scanline :: [[Int]] -> Int -> [[Int]]
scanline gs m
| m<1             = []
| otherwise       = let {
lm = n * (n - 1) `div` 2
; gs1 = zip [lm..(lm + m -1)] $ map (\y -> gs !! y) $ reverse [0..(m-1)]
; gs2 = filter (\(x, gse) -> last gse < x) gs1
; gs3 = filter (\(x, gse) -> null $ (diff_set gse) `intersect` (map (x -) gse)) gs2
} in (map (\(x, gse) -> gse ++ [x]) gs3) ++ (scanline gs $ m + 1)
where
diff_set :: [Int] -> [Int]
diff_set s = sort $ map (\(x,y) -> (s !! y) - (s !! x)) cs
where
cs = [(x,y)|x<-[0..(n-3)],y<-[1..(n-2)],x<y]--

GR-40の一つ目を求めるのにかかる時間をその3のコードと比較してみる。

その3:

40:[0,1,3,8,12,22,28,46,59,82,99,114,149,175,214,244,292,333,396,453,497,561,623,732,765,817,961,990,1084,1263,1346,1481,1561,1689,1762,1884,2124,2190,2274,2379]      856.42 real       855.50 user         0.79 sys

今回:40:[0,1,3,8,12,22,28,46,59,82,99,114,149,175,214,244,292,333,396,453,497,561,623,732,765,817,961,990,1084,1263,1346,1481,1561,1689,1762,1884,2124,2190,2274,2379]      636.87 real       635.78 user         1.00 sys

それなりに高速化できたということは、予想通りの最適化が行われたと見ていいのかな。