Born Too Late

社内で, 主に MySQL 初学者を対象とした勉強会をやってきました.
社内勉強会ということで, というと言い訳になりますが, いつも以上にゆるふわな内容となっています.

改めて見るとソースどこだよ? っていう情報がいくつかあるので反省.
(「RDBMS を使いつつ, NOSQL で最適化というパターンがほとんど」とかどこのことだよと. まぁ Tumblr とかはそれにあたるみたいですが)

あと, インデックスの仕組みを単純化して話すために B-Tree じゃなくて Binary Search Tree について紹介してますが, この辺も詳しい方の突っ込みが欲しい所です.

ところで勉強会に参加していてよく思うのですが, 勉強会というのは自分で発表してナンボだということです.
これは勉強会で人の話を聞くのは意味が無い, ということではなくて, 自分で調べたときの方が 30 倍ぐらい身に付くんじゃないか, という感覚によります.
どう考えても発表した方がコストパフォーマンスの高い学習ができる.

自分のスキルアップに繋がるからそれはそれでいいんですが, やっぱり社内でとなると, 貴重なみんなの時間を使わせてもらうことにもなるので, 出来る限り聞いてる人の身に付くような工夫を心がけたいなと思います.

そこで今回は, みんなで Binary Search Tree を作る, という参加型の企画を仕込んでみました.
作る, といってもいきなり実装するのはハードルが高いので, ひとりひとりに適当な名前 (タロウとかハナコとか) を順に挙げてもらい, ホワイトボードに Binary Search Tree を書いていくというものです.
(今思えばこれ写真に残しておけばよかった)

思いのほか盛り上がったし, ちゃんと理解してもらえたようでした.
Head First データ構造という感じでおもしろかったです.

あと, スライド中で紹介しているんですが, ハーバード大学のコンピュータサイエンスの授業の動画はオススメです.
教授のテンションがやたら高くて白熱教室という感じ. (ついていくのが大変そうな感じではある)

今回の発表では, Binary Search の文脈で 4:30 辺りの, 電話帳で Binary Search と Linear Search をやってる部分をみんなで観ました.

Coffee キメるの気持ちいいですね.
Node.js で実行してください.

CoffeeScript のコードスニペット書いてます.

See also

• 常識を覆すソートアルゴリズム！その名も”sleep sort”！

この記事は個人的なメモです.

プログラミング言語C 第2版 ANSI規格準拠を読んでいて, 構造体の章に出てきた BinaryTree がよくわからないので, とりあえず Ruby で実装してみた.
単語をキーに, その回数を数えるだけの単純なプログラム.

BinaryTree::Node クラス

ツリー構造のノードを表すクラス.
単語, 回数, そして左/右のノードをプロパティとして持ちます.

RSpec

せっかくなので BDD (振る舞い駆動開発) の練習.

実行するとこのようになります.

$ rspec binarytree_spec.rb --format doc
BinaryTree::Node
  with word "foo" and no children
    it should behave like Node with word "foo"
      word
        should == "foo"
    it should behave like Node with no children
      left
        should be nil
      right
        should be nil
    size
      should == 1
    count
      should == 1
    words
      should == ["foo"]
    count_all
      should == 1
  with word "foo" and inserted a node with word "bar"
    it should behave like Node with word "foo"
      word
        should == "foo"
    it should behave like Node with one child with no children
      size
        should == 2
    right
      should be nil
    words
      should == ["bar", "foo"]
    count_all
      should == 2
    its child on the left
      it should behave like Node with no children
        left
          should be nil
        right
          should be nil
      word
        should == "bar"
      size
        should == 1
      count
        should == 1
      count_all
        should == 1
  with word "foo" and inserted a node with word "hoge"
    it should behave like Node with word "foo"
      word
        should == "foo"
    it should behave like Node with one child with no children
      size
        should == 2
    left
      should be nil
    words
      should == ["foo", "hoge"]
    count_all
      should == 2
    its child on the right
      it should behave like Node with no children
        left
          should be nil
        right
          should be nil
      word
        should == "hoge"
      size
        should == 1
      count
        should == 1
      count_all
        should == 1
  with word "foo" and inserted a node with word "foo"
    it should behave like Node with word "foo"
      word
        should == "foo"
    it should behave like Node with no children
      left
        should be nil
      right
        should be nil
    count
      should == 2
    words
      should == ["foo"]
    count_all
      should == 2
  with word "foo" and inserted a node with word "bar" 3 times
    it should behave like Node with word "foo"
      word
        should == "foo"
    right
      should be nil
    count
      should == 1
    size
      should == 2
    words
      should == ["bar", "foo"]
    count_all
      should == 4
    its child on the left
      word
        should == "bar"
      size
        should == 1
      count
        should == 3
      count_all
        should == 3
  with word "foo" and inserted a node with word "hoge" 3 times
    it should behave like Node with word "foo"
      word
        should == "foo"
    left
      should be nil
    count
      should == 1
    size
      should == 2
    words
      should == ["foo", "hoge"]
    count_all
      should == 4
    its child on the right
      word
        should == "hoge"
      size
        should == 1
      count
        should == 3
      count_all
        should == 3
  with word "a" and inserted nodes with word "b" ~ "j"
    size
      should == 10
    words
      should == ["a", "b", "c", "d", "e", "f", "g", "h", "i", "j"]

Finished in 0.03146 seconds
57 examples, 0 failures

いやー, RSpec って楽しいですね.
PHP にもこういうの欲しい.

実行してみる

“to be or not to be” というフレーズ中に含まれる単語と, その回数を計算します.
結果は以下のとおり.

$ ruby example.rb
be (2)
not (1)
or (1)
to (2)

4 words.
6 nodes.

今度は C/C++ でも実装してみよう.
そして BTree や B+Tree についても勉強してみよう.

というわけで今日はここまで.