SICP 読書会 #2 ― 2008年06月10日 23時23分

yukky さん主催の SICP 読書会、その第 2 回に参加しました。今回はあらかじめ予習範囲を提示し、最初の 30 分間でそこを読み進めた上で、後はもっぱら範囲内の問題にあてるという形式でした。私の分も含め各人の解答は当日のチャットログから参照できます。

開始前の空き時間で最初のほうの問題をやっておいたのですが、それでも時間がぜんぜん足りなくて息切れしてしまいそうでした。予習復習をしっかりしておかないとちょっとつらいかもしれませんね。

丸括弧と角括弧

Gauche では (Scheme では?) 丸括弧の代わりに角括弧も使えるので、cond の条件節に使うと読みやすいと教えてもらいました。確かに読みやすくはなりますが、なんだか美しくないような気がするのは私だけでしょうか。

(define (square x) (* x x))

; b の n 乗を求める
(define (expt b n)
  (cond [(= b 0) 1]
        [(even? b) (square (expt (/ n 2)))]
        [else (* b (expt b (- n 1)))]))

ユークリッドの互除法

最大公約数を求めるアルゴリズムとして有名なユークリッドの互除法ですが、英語では Euclidean algorithm といって、「互いに割る」というようなニュアンスは直接的には含まれてないのですね。

反復的プロセスへの変換

累乗と乗算を求める関数を、再帰的プロセスから反復的プロセス (末尾再帰) に直せという問題が出てきます。いろいろ悩んだすえ、以下のように考えにたどり着きました。

; b の n 乗を求める
(define (expt a b)
  (define (iter b n acc)
    (cond ((= n 0) acc)
          ((even? n)
           ; ここをどう書くか
           )
          (else
           ; ここをどう書くか
           )))
  (iter b n 1))

iter はどういう関数かを考えます。S 式表記から離れますが、acc = 1 のとき exp-iter(b, n, 1) は b^n を返します。n = 0 のとき、iter(b, 0, acc) は acc を返します。これらから考えていくと、iter は iter(b, n, acc) = b^n * acc という関数であることが推測されます。n が偶数のときは n / 2 が整数ですから、

  b^n * acc
= b^(n / 2 * 2) * acc
= (b^(n / 2))^2 * acc
= (b^2)^(n / 2) * acc

という変形が成り立ちます。n が奇数のときは、

  b^n * acc
= b^(n - 1 + 1) * acc
= (b^(n - 1) * b) * acc
= b^(n - 1) * (b * acc)

となります。つまり、

  • n が偶数なら iter(b, n, acc) = iter(b^2, n / 2, acc)
  • n が奇数なら iter(b, n, acc) = iter(b, n - 1, b * acc)

となるのです。後はこれを S 式に戻してやれば以下のように完成します。

; b の n 乗を求める
(define (expt a b)
  (define (iter b n acc)
    (cond ((= n 0) acc)
          ((even? n) (iter (square b) (/ n 2) acc))
          (else (iter b (- n 1) (* b acc)))))
  (iter b n 1))

フィボナッチ数の対数的ステップでの計算

問題 1.19 は線形写像の行列表現を利用してフィボナッチ数を O(log N) のステップ数で求める問題です。(bq+aq+ap bp+aq)T = Tpq (a b)T から行列 Tpq が求められるので、Tp′q′ = Tpq2 より p′、q′ も求められますね (行列の右肩の T は転置を表します)。

四元数

なぜか SICP とはあまり関係のない四元数の話も出ました。四元数は応用として 3 次元空間での回転を表現するのに用いられますが、四元数そのものは実 4 次元ですよね。

by nanto_vi [コンピュータ一般] [コメント(0)｜トラックバック(0)]

SICP 読書会 #1 ― 2008年05月17日 02時45分

書くのが遅くなりましたが、先日開かれた snow-bell さん主催の SICP 勉強会 (計算機プログラムの構造と解釈の読書及び演習) に参加しました。SICP 勉強会は午後からだったのですが、同じ会場で午前中に Gauche 勉強会 (私は不参加) も開かれており、チャットログも合同となっています。他の参加者の記事はSICP勉強会のまとめと異業種交流会 - snow-bellの日記からどうぞ。

組み合わせと合成手続き

Scheme の式 (expression) には組み合わせ (combination) と合成手続き (compound procedure) がある。式を評価したとき、組み合わせならば部分式 (リストの各項) が再帰的に評価されるが、合成手続きでは部分式が組合せとして評価されるとは限らない。

たとえば、手続き定義 (関数定義) (define (square x) (* x x)) は合成手続きであり、この式中の (square x) は組み合わせとして評価されるわけではない (ここでは関数 square に値 x を適用しているわけではない)。

作用的順序と正規順序

引数をすべて評価してから関数にそれらを適用するのが作用的順序の評価 (applicative-order evaluation)。関数の内容を先に展開し、引数が必要になった時点でその引数を評価するのが正規順序の評価 (normal-order evaluation)。

評価順 言語例 SICP 別称
引数が先 Scheme、C 作用的順序の評価 正格評価 (strict evaluation)、先行評価 (eager evaluation)、値呼び出し (call-by-value)
関数が先 Haskell 正規順序の評価 非正格評価 (non-strict evaluation)、遅延評価 (lazy evaluation)、名前呼び出し (call-by-name)

それにしても normal、regular、canonical、strict にそれぞれ正規、正則、正準、正格と別個の訳語を割り当てていった人たちはすごいと思う。

1.1.6問題1.3

演習問題三つの数を引数としてとり，大きい二つの数の二乗の和を返す手続きを定義せよ．、私の解答は以下。

(define (f1.3 x y z)
  (cond ((and (>= x z) (>= y z)) (+ (* x x) (* y y)))
        ((and (>= y x) (>= z x)) (+ (* y y) (* z z)))
        ((and (>= z y) (>= x y)) (+ (* z z) (* x x)))
        (else -1))) ; must not come here

基本的な考え方としては一番小さな数を見つけ、それ以外の二つの数の二乗の和を返すというもの。比較に等号を入れているのは同じ数が複数含まれているときのため。しかし二乗の和を求める部分をまとめてないなど無駄が多い。

雑感

ちょうど書籍を買って積んでいたところだったので、一から読む勉強会はいいタイミングでした。各人の演習問題の解答を見ると、こんな風に書けたのかと思うところが多々あり勉強になります。

第 2 回は 5 月 31 日に Vim 勉強会、Kansai.pm と合同で行われるそうです。また、5 月 24 日には Kanasan.JS JavaScript 第 5 版読書会 #4 も開かれるので、関西の方は是非 (もちろん関西以外からでも) 参加してみてはいかがでしょうか。

by nanto_vi [コンピュータ一般] [コメント(0)｜トラックバック(0)]

Google の大規模データ処理 ― 2008年01月25日 19時59分

Google の鵜飼文敏さんによる講演会「大規模データ処理を可能にする Google の技術」に行ってきました。内容的には筑波大学で開かれたものと同じではないかと思います (「新ビジネスモデル」がそのままだったことなどから)。以下、上記記事に載っていないことを中心にメモから抜書きを。

此頃 Google にはやる物
現在 Google では Google の使命 (Google's mission is to organize the world's information and make it universally accessible and useful...) の早打ちが流行中。鵜飼さんは 50 秒程度、一番速い人は 30 秒程度。
Google の扱う情報
Google のいう「情報」はインターネット上のものだけに限らない (例: Google ブック検索)。
データセンター構築の方針
初期のころは「いかに狭い部屋にマシンを詰め込むか」、現在は「いかに故障した部品を交換しやすくするか」。
電力コスト
ハードウェア性能は向上したが、性能あたりの電力消費量は改善していない。
4 年間の電力コストがハードウェアコストの半分を超える。
スケール = コスト
大規模なソフトウェアは大規模なハードウェアを要求し、大規模なハードウェアはお金 (コスト) を要求する。
SQL DB は使わない
データの分析は単純なもの (合計、最大値、最小値、上位 k 個、フィルタリングなど) がほとんどで、DBMS の高度な機能は必要ない。
これらの分析処理は可換的、結合的なため処理順は任意。
MapReduce
Google の開発した大規模データ処理のためのプログラミングモデル。自動的並列分散化、耐障害性、I/O 最適化に優れている。
日本語での解説は Radium Software Development に詳しい。講演中に使っていた図及び例もほとんどそのまま。
Map、Reduce 関数は C++ で記述。
Map から Reduce に渡す処理を「シャッフル」と呼んでいた。内容的には「ソート」のほうが適切な気がするのに、なぜ「シャッフル」というのか?
Sawzall
MapReduce 上で動くデータ分析用言語。強い静的型のスクリプト言語。
限定詞によるループ、if の簡略化が可能。when (i : each int; queries[i].language = JAPANESE) { ... } (foreach (queries 中の query) { if (query.language = JAPANESE) { ... } } より最適化しやすいのか?)
Google での利用に最適化されている (フィンガープリントや日付が組み込みのデータ型になっているなど)。
例外処理はなく、異常時には undefined を返す。undefined は無視して処理を進めることも可能。
Bigtable
数千台のサーバ、テラバイト規模のメモリ、ペタバイト規模のディスクを扱い、毎秒 100 万 Read/Write を可能にするデータベースシステム。
疎な分散多次元表。(行, 列, タイムスタンプ) でアクセス。
行に対する操作はアトミック。
連続する数行をタブレットという単位にまとめて管理。
GFS (Google File System)、Chubby、SSTable といった Google のシステムの上に構築。
日本語での解説は steps to phantasien に詳しい。
タブレット
SSTable (不変二次元マップ) とログデータ (SSTable からの更新分) の組み合わせ。
SSTable は書き換えできないので、追加、削除分はログデータに記録する。ログデータがたまってきたら SSTable を作り直す。
データ量がもたらすもの
計算能力が増えると難しい問題が解けるようになるというのはよく知られているが、データ量が増えると解決不能だった問題が解けるようになるというのはあまり知られていない。
データ量の増加が可能にしたアプリケーションの例
スペル訂正 (「もしかして」機能など)。Web を文脈つきの辞書とみなす。
Google が公開している論文など
以上の技術の概要については Papers Written by Googlers で参照できる。
東京オフィスの位置づけ
東京オフィスはローカライズオフィスではない。

質疑応答では「もしかして」機能に関する質問が多く出ていました。「答えられない」という回答もちらほら。

「もしかして」で間違った結果をどう直すか
間違った結果を目視で直したりはしない。すべて機械処理。
テキスト処理は言語非依存。
BM 法を検索したら KMP 法が引っかかった
ユーザによってはそれが正しい。究極的にはパーソナライゼーションで解決すべきこと。
1 日にコードを書く時間は
日によって違うが、1 日 5 時間くらいコードを書く。レビューなどでコードを読む時間も多い。
日本語の処理に使っている知識は
日本語の知識の利用は皆無。品詞情報なども使っていない。
C++ をどのような言語として使っているか
基本的にオブジェクト指向言語として使っているが、部署によっては better C として使ったりテンプレートを使ったりすることも。
例外は使わない。Google の規模だとほぼすべての実行パスを通るため、見た目がわかりやすくなっても処理を追いにくくなる。
Android に関して、Java 言語を使いながら、Java ME 上のライブラリとしてではなく、既存のものと互換性のないプラットフォームとして作り出す必然性は
開発責任者がそのほうがいいと思ったのだろう。

終了後、鵜飼さんとのじゃんけんに勝って Google T シャツをゲット。さらに残って話を聞いていたところ、余った Google T シャツももらったので、結局白黒 2 枚の T シャツ (前面に Google ロゴ、背面に「I'm Feeling Lucky!」)をいただくこととなりました。

by nanto_vi [コンピュータ一般] [コメント(0)｜トラックバック(0)]

OSC2007 Kansai ― 2007年07月26日 01時28分

21 日土曜日にオープンソースカンファレンス 2007 Kansai へ行ってきました。

ブラウザでの JavaScript の世界へのお誘い

もじら組のしものさんによる講演。JavaScript や Ajax ライブラリについて触れたあと、Firebug の紹介がありました。addons.mozilla.org へ行き Firebug をインストールするところから実際の使用までを、リアルタイムでデモしてくれたのがわかりやすかったです。ただ、画面の解像度が高すぎてスライドの文字が読みづらかったかも。

Ruby on Rails ハンズオンセミナー

実際に Ruby on Rails で簡単な Web アプリケーションを作ってみようという企画。Ruby on Rails 初体験だったのですが、これは確かに手早くものを作るにはもってこいですね。資料に $ vi ....rb とあって、vi なんて最後に使ったのは何年前だったっけとあせったのですが、さすがにそこは Emacs でも何でもいいとのことで一安心。しかし日本語配列なのはいいとして、Caps Lock と Ctrl の位置、Ctrl + h が一文字消去ではなくヘルプなど、微妙なところでやりづらかったです。

Ruby の紹介で、Ruby を使い慣れてくると for 文を使わなくなるといっていたのが印象的でした。JavaScript でもバージョン 1.6 以降なら Array#forEach、Array.forEach があるのですが、どうも関数生成・関数呼び出しのコスト、いちいち function や return といったキーワードを書かなくてはいけない手間が気になって、何でもかんでも使おうとは思えないというのが個人的な感想です。

環境によっては for 文と配列拡張 (Array Extras) とで速度に大差はないとのこと。ちなみに、SpiderMonkey において for-in 文・for-each-in 文が for 文・配列拡張より遅くなる原因として考えられるのは、新規イテレータオブジェクトの作成、プロトタイプチェーンの探索、重複するプロパティ名の除去といったところでしょうか。

ライトニングトーク

閉会式に先立って持ち時間 5 分のライトニングトーク。収支概算が大流行でした。もじら組某氏のチャイナ服はみんなスルー気味だったような。

Ruby 関西

Ruby 関西に参加すると Haskell ができるようになるそうです。

もじら組

ここに、himorin (しもの) さんによるプレゼン手法、通称「himorin メソッド」が開発されました。

用意するもの
  • バッテリーが寿命を迎えたノート PC
手順
  1. まず Mozilla 24 の紹介。
  2. Mozilla 24 プログラムの書類選考結果 53 件をひたすら読み上げる。
  3. 3 分経過、このまま結果読み上げで 5 分使い切るのかと思ったところで、バッテリー切れにより PC が休止状態へ突入。
  4. そのまま終わってしまうのかと思いきや、1 分程度で復帰完了。残り 1 分をきってる。
  5. とにかく残りのページだけめくり、ネゴロさんの耳付き写真が出たところで再び休止状態へ。
  6. 終。

宇田道信さん

自作の楽器「ウダー」の紹介。和音の構成を多角形として視覚化できるとのことで、音楽的素養ゼロの私にもなんかすごいということは十分伝わりました。TLD la はラオス。

by nanto_vi [コンピュータ一般] [コメント(0)｜トラックバック(0)]

Google のソフトウェア開発 ― 2007年04月29日 19時41分

Google 技術講演会「Developing Software in the Real World」に行ってきました。講演者は Google 東京 R&D センター ソフトウェアエンジニアの南野朋之さん。その 1 週間前に行われた、Mozilla Corporation の Seth Bindernagel と Seth Spitzer との講演会 (Mozilla Party JP 8.0 とは別物) には参加できなかったので、リベンジ (?) という形になります。

南野さんはインターンを経て Google へ入社、Google マップでの写真表示を開発された方で、今回の公演内容は Google でのソフトウェア開発体制、および Photos on Google Maps 開発の舞台裏に関してでした。

Google でのソフトウェア開発体制

OKR (Objectives and Key Results)
四半期ごとに目標 (長期、短期) を立て、成果を評価する。これが各エンジニア、個別チーム (5 ～ 6 人)、会社などさまざまなレベルで行われる。
百聞はデモに如かず
20% ルールでの成果など、とにかくデモを作る。それに対してチーム内外からフィードバックを受けられる。
Design Doc
実際のコーディングへ移る前に、Why、How を書いておく。
Weekly Snippets
週ごとに今週すること (したことだったかも) を書いておく。
強大なインフラ
数千台のクラスタ、ペタバイト規模のストレージ、Web データなどを (インターンでも) 自由に扱える。
何でも共有
全ソースコードは全エンジニアに共有される。Design Doc、Weekly Snippets など、誰が何をしているのかという情報も共有される。

Photos on Google Maps

機能概要
Google マップでお店やホテルを検索した際、その店舗に関する写真をバルーン内に表示する。
最初のアイデア
Web ページ中から住所情報などを元に関連する画像を取得する。
ノイズの除去
複数ページで使われている画像は、サービスのロゴやボタンなどである可能性があるので取り除く。
イメージ検索チームのシステムを利用してポルノ画像を取り除く。
精度の向上
住所情報だけでなく、店舗名とともに使われる特徴的な語も利用する。
デモ
自前の HTTP サーバーと Greasemonkey 用スクリプトでデモを作成。
公開
2007 年 3 月 8 日に公開。海外では Slashdot.org にも取り上げられた (該当するトピックがわかりませんでした) が、日本では反応が薄かった。(私自身気づいてませんでした。m(_ _)m)

質疑応答

Google をやめた人がソースコードを流出させる可能性について
NDA により縛られている。また、Google の社訓 Don't Be Evil には、そのようなマナーに反することをしなくても、良いソフトウェアは作れるという意味もある。さらに、ソースコードが手元にあっても、Google 外でそれを実行するのは難しい (数千大規模のクラスタを用意できないなど)。
Google 内に外部ソースコードが混入する可能性について
ソースコードのライセンス専門の担当者もいるはず。(中国語 IME の辞書問題に関しては残念。)
Google 内で出たアイデアのうち、実際世の中に出るものの割合は?
アイデアだけで終わるものもあるが、いったん走り出せば大体は世に出る。
日本語のメーリングリストもあるのか?
メーリングリストなどはすべて英語。前述の Design Doc、Weekly Snippets なども英語。
個人情報に関して
通常のエンジニアはユーザーのアクセスログを閲覧できない。Google Suggest の開発など、特殊な場合は契約書にサインした上で閲覧できるが、それでも生の IP アドレスなどは取得できない (ハッシュ化されている)。メールの盗み見はできない。

感想

Google の強みというのは、強大なインフラと、広範囲からのフィードバックにあると感じました。やはり一人で作業していても煮詰まってしまうところ、Google なら共有されたソースコードを参考にすることもできれば、誰が何をしているのかがすぐわかるので専門の人に聞くことも簡単です。それから英語が重要。読み書きだけでなく会話もできないときつそうな雰囲気です。

しかし、いくら Google 内部で情報が共有されているといっても、外から見ればブラックボックスなので、オープンソースソフトウェアとの関係にどう折り合いをつけていくのか疑問が残ります。(このことについて質問しておけばよかった。)

by nanto_vi [コンピュータ一般] [Web 関連技術] [コメント(0)｜トラックバック(3)]