AIRの聖地和歌山県御坊市美浜町に行ってきました

keyの代表作『AIR』の聖地、美浜町に行ってきました。
18きっぷの日帰りで名古屋←→和歌山は相当シビアで、現地滞在時間は2時間もなかったです。。。
夏の終わりの雰囲気が感じられ、非常に良いところでした。

ローカル線紀州鉄道西御坊駅。非常に短い区間を走っています。一時間に一本しか電車がないので結局この路線は使用せず、自力でJR御坊駅から浜まで歩いていきました。
f:id:xxxasdfghjk999:20170901122112j:plain
西御坊駅のすぐ前にあるAIRのOPで登場する廃線跡。原作では線路がつながっていましたが、安全措置のためか途切れていました。
f:id:xxxasdfghjk999:20170901122108j:plain
往人と観鈴が歩いた道。
f:id:xxxasdfghjk999:20170901122103j:plain
煙樹ヶ浜。時間の関係ですみからすみまで回れず、適当に堤防にこれを置いて撮影しました。
f:id:xxxasdfghjk999:20170901122057j:plain

時間がシビアな旅でしたがなかなかおもしろかったです。

鎌倉に行ってきました

夏休みなので旅行に行ってきました。
行き先は鎌倉です。
主にP.A.WORKSのアニメ『TARI TARI』の舞台を探訪しに行きました。
いろいろトラブルはあったけど楽しかったです。
続きから↓

続きを読む

しょーもないプログラム

#include<stdio.h>

int main()
{
  int i;
  while(1){
    printf("\x1b[41m");
    printf("\x1b[30m");
    printf("すぐにけせ");
  }
  return 0;
}

ターミナルの出力の色変えられるんですね...
某ゲームの都市伝説的なアレ

テストあとひとつ

夏休みまであとちょっと~~~
がんばれおれ

Haskellでフィボナッチメモ化再帰

さっき挙げたプログラムだとfib(40)ぐらいでもう数十秒ぐらいかかり、だいぶ遅いです。
メモ化再帰を使って高速化すればいいじゃん(いいじゃん)と思いましたが、Haskellの性格上、なかなか実装は困難を極めました。ここにメモ化再帰フィボナッチをメモしておきます...

fib x = if(x < 3)
        then 1
        else (fiblist !! (x-1) + fiblist !! (x-2))
fiblist = [fib x  | x <- [0,1..]]

実行結果

ghci> fib 5000
3878968454388325633701916308325905312082127714646245106160597214895550139044037097010822916462210669479293452858882973813483102008954982940361430156911478938364216563944106910214505634133706558656238254656700712525929903854933813928836378347518908762970712033337052923107693008518093849801803847813996748881765554653788291644268912980384613778969021502293082475666346224923071883324803280375039130352903304505842701147635242270210934637699104006714174883298422891491273104054328753298044273676822977244987749874555691907703880637046832794811358973739993110106219308149018570815397854379195305617510761053075688783766033667355445258844886241619210553457493675897849027988234351023599844663934853256411952221859563060475364645470760330902420806382584929156452876291575759142343809142302917491088984155209854432486594079793571316841692868039545309545388698114665082066862897420639323438488465240988742395873801976993820317174208932265468879364002630797780058759129671389634214252579116872755600360311370547754724604639987588046985178408674382863125

5000項目でも一瞬で計算できます。さすがメモ化(というより多倍長が標準実装スゴイ)
書いてみるとこんだけかい!って感じですが...
Haskellはまずリストを宣言してそのリストの内容を後から変更することができません!
具体的にいえば、リストを宣言したならばそのリストのn項目に新しく数値を代入したりすることはできません。
(リストをくっつけたり分解したりといったことはできます)
メモ化に当たってリストの先頭や末尾に要素を付け足しできるという性質を使い、末尾に少しずつフィボナッチ数を付け足していく感じでボトムアップ式に再帰を行おうと思ったのですが、Haskellのリストのことがよくわかっておらず、引数にリストをとる必要があるかもしれないと思い、なかなかややこしそうだったのでやめました。
上の実装は、Haskell遅延評価特性を用いています。遅延評価とは、その数値が必要となったときに初めてその計算を実行するという特性です。これによってメモリが有限の計算機でも、抽象度の高いプログラミングができ、あたかも無限の要素をもつリストを作ることができます。この遅延評価というのは関数型特有の長所です(手続き型では実行の順序によって計算結果が変わる可能性があるが、関数型では副作用がなく、いつ計算しても同じ値が得られるため)。それによってfiblistは無限に並ぶフィボナッチ数列を表すことができます。fib関数ではfiblistのx-1,x-2項目を取り出して和を取るように言っていますが、これをまだ計算していなかったならばfibを再帰して...ということを繰り返し、fiblistを埋めていきます。メモ化再帰も結構きれいにかけて満足です。これを応用すればいろんなメモ化がかけそうですね。

追記

fib 0 = 0
fib 1 = 1
fib x = fiblist !! (x-1) + fiblist !! (x-2)
fiblist = [fib x  | x <- [0,1..]]

こっちのほうがエレガントですね