奥歯の治療完了

11月から続けていた奥歯の治療がようやく今日で完了した。
奥歯の土台を金属で形成し、その上に義歯を接着して一体の歯に仕上げてある感じ。
噛み合わせも良くなってとりあえず一段落ついた。

んが、本日先生と相談の上、下の親知らずを両方共抜歯することにした。
上は生えなかったのだが、下は両方共手前の奥歯にひっかかる形でちょこっと頭が見える程度に斜めに生えている。
この状態で放置しておくと、周辺の歯茎を傷めたり手前の奥歯の虫歯の原因になっちゃうねぇと脅されて諭されて、抜歯を決意。

年内中にとりあえず片側に手をつけることに。
苦難は続く。

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

任意のGR-nの要素の最大値の下限について考える。

[0,g1,g2,…,g(n-1)]について定義から隣り合う要素の差は全て異なるので、隣り合う要素の差分の最小のセットとして[1,2,..,n-1]が考えられる。この時、g(n-1)はn*(n-1)/2になる。

以上から、GR-(n-1)とn*(n-1)/2未満の数の組み合わせはGR-nに含まれないことになり、この部分の探索を省くことが出来る。
隣り合わない要素の差についても考慮すればg(n-1)の下限はもっと大きくなるはずだが、それは結局OGRを求めようとするようなもので、あまり現実的でない。これでも、O(n^2)にあたる計算量を削減できることになるはずで、それなりに高速化を期待できる。

で、ちょこっとコードを書き直してみた。

 

-- 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 = map (\(x, gse) -> gse ++ [x]) gs2
} in filter gr_p gs3 ++ (scanline gs $ m + 1)
where
gr_p :: [Int] -> Bool
gr_p ns = let ds = sort $ map (\(x,y) -> (ns !! y) - (ns !! x)) cs
in ds == nub ds
where
cs = [(x,y)|x<-[0..(n-2)],y<-[1..(n-1)],x<y]

その2の時のコードと今回のコードでGR-40の最初の一つ目を見つけるのにかかる時間を比べてみる。

その2:

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]
1208.36 real      1207.24 user         0.93 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]
856.42 real       855.50 user         0.79 sys

まずまず高速化できたようだ。とはいえ、GR-150とか計算させようとすればまだまだとんでもなく時間がかかりそうだ。

七瀬ふたたび(最終回)

終わっちゃいましたねぇ。

自分には結構満足なクオリティでしたね。
蓮佛美沙子、柳原可奈子の演技もいい感じだったし。

設定が大幅変更になっているので、必然ストーリも原作からは大分違ったものになっていると思うが(大分記憶が曖昧になってるけど)、それでもテイストというかエンディングへの収束感みたいなものはよく反映されているんじゃないかな。