フィボナッチ数列のうち、各桁の数字を足した数で割り切れる(ry

たまたま見つけたネタ。

 cf. フィボナッチ数列 – utthi_fumiの日記

タイトルが長くなったので省略しちゃったけど、ちゃんと引用すると、こう。


フィボナッチ数列のうち、各桁の数字を足した数で割り切れる数を以下の例に続けて小さいほうから5個求めてください。

2 → 2 ÷ 2

3 → 3 ÷ 3

5 → 5 ÷ 5

8 → 8 ÷ 8

21 → 21 ÷ 3・・・2 + 1= 3で割る

144 → 144 ÷ 9・・・1 + 4 + 4 = 9で割る

引用してもわかりにくいな。要するに、フィボナッチ数列を {Fn} (n=0,1,2…)として、Fn の各桁の数を足し合わせたものを S(Fn) とすると、S(Fn) で割り切れる Fn を小さい順に5つ(ただし、例に出ている 114 までを除く)求めよ、ってことだ。

「 これはメモ化と大きな桁を扱う事についての問題です 」なんて書いてあるけど、大きな桁はその通りだけど、n から Fn を求めようとするからメモ化なんかが必要になるんであって、この問題では小さい順に調べればいいんだから素直にフィボナッチ数列の頭から生成すればいい。

というわけで、Go でやってみた。ただやってみるだけじゃなくて、あんまり使ったことのないゴルーチンとチャネルを使ってみたよ。

まずは単純にフィボナッチ数列を生成するところから。

package main

import (
	"fmt"
)

func main() {
	s := makeFib()
	for i := 0; i < 10; i++ {
		f := <- s
		fmt.Println(f)
	}
}

type Stream chan int

func makeFib() Stream {
	s := make(Stream)
	go func() {
		a, b := 0, 1
		for {
			f := a
			a, b = b, a + b
			s <- f
		}
	}()
	return s
}

関数 makeFib は、チャネルを返す。で、このチャネルからフィボナッチ数列を一つずつ取り出せる。makeFib の中のゴルーチンは無限ループになっているので、(アルゴリズム上は)無限に取り出すことができる(実際はどうだかわからない)。実行結果は次の通り。

^o^ > go run fib_chan.go
0
1
1
2
3
5
8
13
21
34

さて、それじゃ本題に入ろう。といってもフィボナッチ数列はもう得られているんだから、あとは条件に合う数 Fn を5つ出力するだけだ。こうなった。

package main

import (
	"fmt"
)

func main() {
	s := makeFib()
	i := 0
	for i < 5 {
		f := <- s
		if f > 144 && isDivisible(f) {
			i++
			fmt.Println(f)
		}
	}
}

type Stream chan int

func makeFib() Stream {
	s := make(Stream)
	go func() {
		a, b := 0, 1
		for {
			f := a
			a, b = b, a + b
			s <- f
		}
	}()
	return s
}

func sumOfPlaces(n int) int {
	sum := 0
	for n > 0 {
		sum += n % 10
		n /= 10
	}
	return sum
}

func isDivisible(n int) bool {
	return (n % sumOfPlaces(n)) == 0
}

実行結果。

^o^ > go run fib_divisible.go
2584
14930352
86267571272
498454011879264
160500643816367088

OK。ちゃんとできた。

リスト(配列)の中で隣り合う同じ値をグループ化する(3)

しつこいようだけど、今度は Go でやってみた。

^o^ > go run adjacentGroup.go
[[1 1] [2 2] [3] [1 1]]
[]

defer

defer 文は、関数を抜けるときに実行する処理を登録する。defer 文で登録する処理は関数またはメソッド呼び出しでなければならない。
例を示そう。

関数 foobar でそれぞれ defer 文で処理を登録している。これを実行するとこうなる。

^o^ > go run defer.go
foo start
bar start
bar end
foo end

関数を抜けるときに処理が実行されているのがわかる。

defer 文で登録した処理は、ランタイムエラーが起こっても有効だ。次の例では一番深い関数呼び出し(baz)で panic を起こしている。この例でも defer 文で登録された処理は実行され、その後、エラーメッセージを表示する。

^o^ > go run defer2.go
foo start
bar start
bar end
foo end
panic: oops!

goroutine 1 [running]:
main.baz()
        C:/Users/takatoh/Documents/w/learning-go/defer2.go:6 +0x6b
main.bar()
        C:/Users/takatoh/Documents/w/learning-go/defer2.go:12 +0x141
main.foo()
        C:/Users/takatoh/Documents/w/learning-go/defer2.go:18 +0x141
main.main()
        C:/Users/takatoh/Documents/w/learning-go/defer2.go:22 +0x27
exit status 2

panic

組み込み関数 panic は、エラーメッセージを表示して、プログラムを中断する。何か致命的なエラーが起こった場合に使用する。
簡単な例を示そう。関数 fact は 0 以上の整数に値を返し、それ以外の場合には panic を呼ぶ。

実行例。

^o^ > go run panic.go
3628800
362880
40320
5040
720
120
24
6
2
1
1
panic: fact : domain error

goroutine 1 [running]:
main.fact(0xffffffffffffffff, 0x1, 0x1, 0x2)
        C:/Users/takatoh/Documents/w/learning-go/panic.go:7 +0xb8
main.main()
        C:/Users/takatoh/Documents/w/learning-go/panic.go:18 +0x43
exit status 2

for ループの最後で fact-1 を与えているので panic が呼ばれている。

エラー処理

Go には例外機構がない。じゃ、どうやってエラー処理をするかというと、多値を使って関数の返り値としてエラーを返すようにする。
例を見てみよう。

fact 関数は階乗を求める関数だけど、値を2つ返す。求めたい関数の値とエラーだ。通常はエラーとして nil を返すけど、引数が0より小さかった場合はゼロ値と nil でないエラーを返す。
試してみよう。

^o^ > go run err_fact.go
3628800
362880
40320
5040
720
120
24
6
2
1
1
fact : domain error

最後の行が fact-1 を与えた場合だ。ちゃんとエラーが表示されている。

エラトステネスの篩

前回のエントリで作った makeIntstreamFileter を使って、素数列を生成するプログラムを作ってみよう。「エラトステネスの篩」というアルゴリズムを使う。
まずはコード。

makeIntstreamFilter は前回と同じだ。篩にあたる seive が素数列を生成する。
まずはストリームを用意しておく(変数 s)。で、ゴルーチンを起動して、中で 2 から始まる整数列を生成するストリームを in に代入する。ここからは繰り返しで、in の先頭 x は素数なのでそのまま s に送信する。そして inx で割り切れる数を取り除くフィルタをかけたストリームに置き換える。これで inx で割り切れない数列を生成するストリームになった。
結果として素数以外はストリームから取り除かれて、素数だけが残るっていうわけだ。
実行結果。

^o^ > go run eratosthenes.go
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 211 223 227 229 233 239 241 251 257 263 269 271 277 281 283 293 307 311 313 317 331 337 347 349 353 359 367 373 379 383 389 397 401 409 419 421 431 433 439 443 449 457 461 463 467 479 487 491 499

ストリーム

チャネルを使って、数列を生成することを考える。数列のような一連のデータの流れを、ストリームとよぶ。
まずは単純な例から。

type を使って、整数をやり取りするチャネルに Stream という別名をつけている。
makeInt 関数は、整数2つ(nm)を引数にとって Stream を返す。中では、Stream を作っておき、ゴルーチンで匿名関数を実行する。このゴルーチンは for ループの中で n から m までを Stream に書き込み、最後に閉じる。
こうすることによって、数列が生成できるわけだ。
実行例:

^o^ > go run stream.go
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

次に、Stream を高階関数に渡してみよう。マッピングを行う streamMap とフィルタリングを行う streamFilter を作ってみる。どちらも関数と Stream を受け取って、新しい Stream を返す。

実行例:

^o^ > go run stream2.go
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
1 4 9 16 25 36 49 64 81 100 121 144 169 196 225 256 289 324 361 400
1 3 5 7 9 11 13 15 17 19

タイムアウト

非常に時間のかかる処理をゴルーチンにするといつまでも終わらなくなる可能性がある。selecttime パッケージの After を組み合わせると、タイムアウトの処理ができる。
After は一定時間が経過したらデータを送信するチャネルを返す。なので、select と併用することでタイムアウトの処理ができるわけだ。

ここでは、時間のかかる処理(関数)として、フィボナッチ数を求める関数を用意した。これで5つのゴルーチンを起動しておき、その終了を待つと同時に time.After で500ミリ秒でタイムアウトするようにしている。つまり time.After の返り値であるチャネルからデータが送られてくる前に処理が終わったゴルーチンだけが結果を表示するわけだ。

^o^ > go run channel_after.go
9227465
24157817
63245986
Timeout

このとおり、500ミリ秒では3つしか終わらなかった。

Goで画像アップローダーを作ってみた

画像アップローダーっていうと、あれだ、ユーザーがアップロードした画像を保存しておいて掲示板かなんかから参照できるようになってるやつだ。あれ、なんでアップローダーっていうんだろうね。
ま、とにかく Go で WEB アプリケーションを書く練習に作ってみた。Go ってワンバイナリでサーバーが作れるからいいよね。
名前は Sulaimān (スライマーン)にした。

 cf. github.com/takatoh/sulaiman

シングルページアプリケーション

複雑なシステムではないので、html を読み込むのはルートにアクセスしたときだけで、あとはすべて ajax で非同期に更新するシングルページアプリケーションにした。
おかげでサーバーサイドの Go だけじゃなくて、クライアントサイドの JavaScript も結構書いた。

サーバーサイド

サーバーサイドの WEB フレームワークには Echo というのを使った。ググってみた範囲では、結構簡単そうだったし、速度も速いらしい。それからデータベースの OR マッパーには gorm というのを採用。Ruby や Python の OR マッパーとちょっと勝手が異なるけど、データベースといってもテーブルひとつの簡単なものだし、Go の中では割とメジャーなものみたい。

 cf. Echo
 cf. gorm

ほかにも JSON を扱うライブラリとか、画像のサムネイルを作るのにはこないだちょっと書いた resize を使った。
コードのすべては上でリンクした GitHub を見てもらいたいけど、メインのファイルだけ載せておこう。

設定ファイルやデータベースの読み込みをしたあと、Echo とハンドラーのインスタンスを作って、ルーティングの設定をしている。GET とか POST とかのメソッドでルーティングの設定をするのは Ruby の Sinatra なんかと雰囲気が似ている。

クライアントサイド

上に書いた通り、シングルページアプリケーションなので、いったんページを読み込んだ後はすべて ajax で非同期に処理をする。ページ遷移はない。
で、JavaScript のライブラリには定番の jQuery と、ページ描画のフレームワークには Vue.js というを使ってみた。jQuery は以前使ったことがあるけど Vue.js は初めてだ。

 cf. Vue.js

でも、Vue.js は学習コストが低いのも売りらしく、実際特に苦労することもなかった。もっとも大したことはしてないんだけども。

ちょっとひっかかった点

それでもうまくいかなかったところはあって、ひとつにはページのタイトルがあげられる。ページタイトルは設定ファイルから読み込んで表示するようにした。まあ、当たり前の発想だよね。で、どうやって表示しようかというときに、サーバー側でテンプレートを使うことを最初に考えた。Go には html/template というライブラリが標準であって、それを使おうとしたんだけど、テンプレートの構文が Vue.js のものと同じ(データを埋め込みたいところに {{ foo }} みたいに書く)で、共存ができなかった。仕方がないので、タイトルも ajax でとってきてクライアントサイドで更新するようにした。
もうひとつもクライアントサイド。次のページを読み込む Next リンクをクリックしたときの動作を、ajax で次のようにやろうとしたところ、うまくいかない。

これ、結構悩んでいろいろ調べて、結局こうなった。

なんでこうじゃなきゃ動かないのかわからない。あとで調べよう。
ともかくもこれで一通りはできた。

やり残したこと

たいていのアップローダーにはついている、ファイルの削除機能がない。一応、削除のためのキーをアップロードの際に入力するようにはしてあるので、今後実装するかもしれない。でもどんな UI にしようか悩んでいる。
それと、ページの下までスクロールしたら自動で次のページを読み込む、いわゆる無限スクロールも実装してみたい。
いつになるかわからないけど。

JPEG画像のリサイズ

Go で画像をリサイズしたいときには、github.com/nfnt/resize を使うといいらしい。

 cf. github.com/nfnt/resize

今回はこれを使って、JPEG 画像のサムネイルを作ってみた。サムネイルは 120×120 に納まり、アスペクト比を保つものとした。

少し引っかかった点が2つ。
1つは、rezise.Resize 関数のサイズを指定する第1、第2引数の指定について。単に 120×120 にリサイズしたいだけならそのように指定すればいいけど、これだとアスペクト比が保存されずに正方形のサムネイルができてしまう。アスペクト比を保存するには、幅か高さのうち小さいほうに 0 を指定してやればいいんだけど、画像が横長なのか縦長なのかで場合分けをする必要があった。

もう1つは、場合分けをするために元画像の幅と高さが必要なので、image.DecodeConfig 関数で取得している。けど、その後、そのまま画像のデコードをしようと image.Decode 関数を呼び出してもエラーになってしまうこと。原因は、image.DecodeConfig 関数でファイルの途中まで読み込んでいるので、そのままだと image.Decode 関数はファイルの途中から読み込むことになって正常にデコードできない、ということだと思う。
そこで (*File) Seek 関数で読み込み位置をファイルの先頭に戻している。この関数は引数を2つとり、1つ目は一のオフセット、2つ目はそのオフセットをどこからにするかの指定。0 だとファイルの先頭から、1 だと現在位置から、2 だとファイルの終わりからになる。
というわけで、Seek(0, 0) として読み込み位置をファイルの先頭に戻してから image.Decode を呼び出して成功した。

一応実行例。

^o^ > go run img_resize.go sample.jpg resized.jpg

横長の画像も、縦長の画像もうまくサムネイルができた。