SICP読書会第31回 - [・ _ゝ・]日記を書くはやみずさん

場所

小飼弾さんの家。広い！本がいっぱい。あんな本棚ほしいなぁ。

8クイーン問題

読書会スタート。この時点で、8クイーン問題についてのコードは1文字も書いていない。
問題2.42の8クイーン問題を、色々脱線しながら考える。safe?プロシージャの実装のアイデアを話すものの、その時点で書いたコードはdefine (safe? k positions)
途中であきらめて、queensプロシージャはWebにある回答をコピペして動かして満足する。

問題2.43

ボードサイズをN、ボードサイズがNのときの、最初のn列にn個のクイーンを置く置き方を $Q(n)$ とする。
色々計算すると、Louisの計算方法では、計算時間 $T^\prime$ が

$T^\prime \leq T^{\prime \prime} = \frac{\sum_{n=0}^{N}Q(n)N^{N-n}}{\sum_{n=0}^{N}Q(n)}T$

になりそうだなぁ、ということが分かった。

読書会で"queen-colsが $N^N$ 回呼び出されるから、計算量も $N^N$ のオーダーで増える"というような話になっていたけど、うちに帰って考えて、重要なのはqueen-colsの呼び出し回数だけではない、という気がしてきた。SICPに出てきた計算量の例題の、典型的なプロシージャは1回の呼び出しあたりの計算量がほぼ固定だったので、呼び出し回数だけを考えておけばよかった。しかし、queen-colsの場合、引数によってfilterを通す要素の数が変わってくるから、それを考慮しなきゃいけないと思う。ということで、自分なりに仮説を立てて計算した結果が上の式。なぜこの式に辿りついたかは、末尾の"もっと詳しく"を参照。

実際に検証してみると、

N=7 のとき - 予想： $T^{\prime} < 1500T$ , 実測： $T^{\prime} = 580T$
N=8 のとき - 予想： $T^{\prime} < 6250T$ , 実測： $T^{\prime} = 3040T$

Nがどんどん大きくなっていけば、近づいていくんじゃないかなぁ、という気がする。

もっと詳しく

Louisの方法について考えてみる。

そもそもあとから気がついたが、queen-colsの呼び出し回数は $N^N$ ではなく $N + N^2 + \cdots + N^N$ 回だった。なぜなら、

(queen-cols N) で (queen-cols (- N 1))がN回呼ばれて
(queen-cols (- N 1)) で (queen-cols (- N 2))がN回呼ばれて
(queen-cols (- N 2)) で (queen-cols (- N 3))がN回呼ばれて
...
(queen-cols (- N (- N 1))) で (queen-cols 0)がN回呼ばれて

となっているので、(queen-cols k)が呼び出される回数を $Times(k)$ とするなら、 $N \times Times(k) = Times(k-1)$ となっている。つまり、(queen-cols k)が呼び出される回数は

$Times(k) = N\cdot Times(k+1) = N^2 Times(k+2) = \cdots = N^{N-k} Times(N) = N^{N-k}$

である( $Times(N)=1$ )。つまり、queen-colsが呼び出される回数の総計は

$\sum_{k=0}^{N} N^{N-k} = N^N + N^{N-1} + \cdots + N^2 + N^1 + 1 = \frac{N^{N+1}-1}{N-1}$ となる。

オーダーとしては $O(N^N)$ だけども。

さて、queen-cols1回の計算量が固定量なら、queensプロシージャの計算量が増えるオーダーは $O(N^N)$ だが、そうは問屋が卸さない*1。おそらく、queen-colsの1回の計算量を決めるのは、フィルタに通す要素の数だ！と山を張ることにする。

(queen-cols k)でフィルタに通す要素の数は、上で使った $Q(n)$ を使って書くなら、 $Q(k)$ 個になる。フィルタに要素1個を通すのが $\alpha$ の計算量だとすると、(queen-cols k)の計算量は $\alpha Q(k)$ である。

全体の計算量については、(個々の(queen-cols k)の計算量)×(呼び出し回数)の総和をとってやればいいから

$T^{\prime \prime} = \sum_{k = 0}^{N}(\alpha Q(k))\times Times(k) = \alpha \sum_{k = 0}^{N}Q(k)N^{N-k}$ となる。

一方、模範的なqueensプロシージャの場合、(queen-cols k)はそれぞれのkについて1回ずつしか呼び出されないので、

$T = \sum_{k = 0}^{N} (\alpha Q(k)) \times 1 = \alpha \sum_{k = 0}^{N}Q(k)$ となる。

あとは、比をとってやれば謎の $\alpha$ が消えてすっきりする。ちなみに、上の方で不等号を使ったのは、queen-colsには他にも色々な処理があるので、Louisの方法だともうすこし遅くなるだろう、という予想を含めて不等号を使った。

NP問題

8クイーン問題は、NP完全ですよ、という話。あとでかく。

JSONP

MeCabをAPI経由で使えるMECAPIを作っているたつをさんからJSONPについての話を聞く。JSONP = JavaScriptのみで、クロスドメインにデータのやり取りをするためのバッドノウハウということでFA?

BASIC

弾さん(というかその場の人達？)に、「未成年のうちはRailsなんて使わず、BASICで茨の道を行け」というありがたいお言葉をｗｗｗ
弾さんが、DIMになんでもかんでも突っ込めばBASICでもレキシカルスコープが実現できる、みたいなことを言っていたけど、BASICは中学生くらいのときにちょっとかじったくらいだからよくわからんなぁ(´・ω・`)
BASICは一応ISO、ANSI、JISで規格策定されているという初耳情報。

名前がわからない

Web上に写真がある人以外は、顔と名前が一致してないでつ(´д`)次の読書会から徐々に覚えていこう。

*1:1回言ってみたかった。今は反省している。