ロードバイクを買いました。
CodeKata Four - Data Munging
http://codekata.pragprog.com/2007/01/kata_four_data_.html
Mungが訳せない・・・。
Martin Fowlerが KataTwoについて
「ひとつの関数についての練習だけで，実践的でない」
と注文をつけてくれた。その通りだと思う。
そこで，今日はもうちょっと複雑にしてみた。
実際のデータを扱う問題を3つ用意した。
【Part One: Weather Data】
2002年6月，NewJersey州Morristownの気象データが，weather.datに記録されている。
temperature spread(注)が一番小さい日のday number（カラム1）を探し出してほしい。
注 1188116772*1 一日の最高気温（カラム2）と最低気温（カラム3）の差
weather.dat
http://choko-chai.haru.gs/kshun/Hatena/weather.htm
【Part Two: Soccer League Table】
2001年第2シーズン，英国 Premier Leagueの結果がfootball.dat に記録されている。
Fカラムはチームの得点のシーズン合計，Aカラムは失点の合計だ。
得点合計と，失点合計の差が最も小さいチームの，チーム名を出力するコードを
書いてみてくれ。
football.dat
http://choko-chai.haru.gs/kshun/Hatena/football.htm
【Part Three: DRY Fusion】
上の2つのコードから，できる限り共通部分を切り出して，
より短くなった2つのコードと，共通コードという形にまとめてほしい。
【振り返り】
・最初にコードを書くときの設計方針が，後で共通部を切り出す作業に
どれくらい影響を与えただろうか？
・2つ目のコードを書くときに，1つ目のコードを書いたことの影響があったろうか？
・共通化を図ることはいつでも良いことだろうか？
共通化することで，可読性は下がらなかったか？保守性はどうかな？
【Ans.共通化前】
#wether.rb
def calMinSpread
file = File.open('wether.dat')
file.gets
file.gets
minArray = calSpread(file.gets)
while line = file.gets
array = calSpread(line)
minArray = array if minArray[1] > array[1]
end
return minArray[0]
end
def calSpread(line)
dummy, day, mxT, miT = line.split(/\s+/)
return day.to_i, mxT.to_i - miT.to_i
end
#football.rb
def calBestTeam
file = File.open('football.dat')
file.gets
minPoint = calPointDefference(file.gets)
while line = file.gets
if(!(line=~/---/))
array = calPointDefference(line)
minPoint = array if minPoint[1] > array[1]
puts "#{minPoint[0]}/#{minPoint[1]}"
end
end
return minPoint[0]
end
def calPointDefference(line)
array = line.split(/\s+/)
puts "#{array[7]}-#{array[9]}"
return array[2], (array[7].to_i - array[9].to_i).abs
end
【Ans.共通化後】
#wether.rb
def calMinSpread_common
file = fileread('wether.dat',2)
minArray = calDiff(file.gets, 1,2,3)
while line = file.gets
array = calDiff(line, 1,2,3)
minArray = array if minArray[1] > array[1]
end
return minArray[0].to_i
end
#football.rb
def calBestTeam_common
file = fileread('football.dat',2)
minArray = calDiff(file.gets, 2,7,9)
while line = file.gets
if(!(line=~/---/))
array = calDiff(line, 2,7,9)
minArray = array if minArray[1] > array[1]
end
end
return minArray[0]
end
#共通コード
def fileread(name,skip)
file = File.open(name)
skip.times do
file.gets
end
return file
end
def calDiff(line, name_i, max_i, min_i)
array = line.split(/\s+/)
return array[name_i], (array[max_i].to_i - array[min_i].to_i).abs
end
CodeKata Three - How Big, How Fast?
コード＝カタ 大きさは？速さは？
http://codekata.pragprog.com/2007/01/kata_three_how_.html
見積もり算は身に着けると役に立つ。
コーディングしている時に，
・データがどれくらい大きくなるのか？
・繰り返し処理にどの程度時間がかかるのか？
などの概算値を求めなくちゃいけないことがあるだろう。
これもシンプルなKataだ。それぞれの問題に概算値を答えればいい。
暗算してみてほしい。
【1.How Big?】
1-1
次の数の符号なし表現をすると，2進で何桁だろか？
・1,000
・1,000,000
・1,000,000,000
・1,000,000,000,000
・8,000,000,000,000
1-2
僕のの町にはだいたい，20,000 人が住んでいる。
全ての人の，名前，住所，電話番号を文字型で記録するとしたら，
どれだけのディスク容量が必要だろうか？
1-3
僕は1,000,000ヶの整数値を二分木に保存したい。
どれだけのノードと，レベルが必要になるだろうか？
32-bit アーキテクチャでは，どれだけの容量になるだろうか？
【2.How Fast?】
2-1
僕が持ってる「Meyer’s Object Oriented Software Construction」は，
1200ページある。こいつを56kbit/secの回線で送るとしたら，
どれだけ時間がかかるだろうか？
オーバーヘッドなんかは考えなくていい。
2-2
僕の二分探索のアルゴリズムは，10,000件の配列から探すと4.5msかかる。
100,000件なら6msだ。10,000,000件から探したらどれだけかかるかな？
ただし，メモリは十分にあって，ページングは起きないと思っていい。
2-3
Unixのパスワードが一方向Hash関数を使って保管されている。
Hash変換された文字列から，元のパスワードを復元することはできない。
とすれば，あるアカウントのパスワードを不正に取得しようとしたら，
全ての文字の組み見合わせを試してみるしかない。
発生させた文字列をパスワードとして入力すると，Hash関数にかけられ，
オリジナルと一致するかが試される。
もし一致したら，成功だ。
今，あるシステムのパスワードが，16文字で，文字の候補が96あったとしよう。
Hash関数を実行するのにかかる時間が1msだとしたら，
この攻撃法は現実的だろうか？
Ans.1-1
まず，2^10 = 1024 neq 10^3。
これでいけば，
・10桁
・20桁
・30桁
・40桁
・43桁
Ans.1-2
僕の名前はアルファベットで14文字，だから32文字取ればいい。
住所は都道府県で16文字，市区町村で32文字，その先も32文字かな。
電話番号は16文字取ればいい。
すると一人当たり128文字。これは128B。
だから20,000*128B neq 20*130KB = 2.6MB
Ans.2-1
日本語の場合，ビジネス文書でA4一枚は約2000文字。
A5判の本なら1000文字としよう。
すると一冊は，
1200page * 1000char/page * 2B/char = 2.4MB
伝送速度は56Kbit/s = 7KB/s
だから
2.4MB / 7KB/s neq 350s neq 6分
Ans.2-2
比較回数 = log_2(件数)
だから
log_2(10,000) = 4*log_2(10) 回で4.5ms
log_2(100,000)= 5*log_2(10) 回で6ms
比較回数について，Mを自然数として，
M*log_2(10)回なら(M-1)*1.5msかかる。
10,000,000件だと，比較回数は
7*log_2(10) 回なので，
(7-1)*1.5ms = 9ms
Ans.2-3
必要な時間は96^16*1ms
これは，
64^16ms = 1024^6ms neq 10^18ms = 10^15s 以上になる。
１日は3600*24 neq 9*10^4s neq 10^5sだとすると，
10^(15/5)日=1024日 以上必要。
つまり3年近く計算にかかるので，この方法はやめたほうがいい。
CodeKata Two -- Karate Chop
コード＝カタ 二分探索を極める。
A binary chop （binary searchのコト），
それは，ソートされた配列から，探したい値のインデックスを求める単調な方法だ。
探したい値が，全体を二分したグループのどちらにあるかに着目する。
この二分する作業を繰り返し，探している値を見つけるか，
配列の中を探し終えたときに，処理が止まる。
効率はまずまずだ。
【問題】
このKataは直球勝負だ。
テクニックや言語は君に任せるから，二分探索を実装してほしい。
そして次の日，まったく違ったやり方で，再び，実装してもらいたい。
こんなことを，その次の日も，そのまた次の日も繰り返す。
合計，5種類の二分探索を実装してみてくれ。
例えば，ひとつは典型的な繰り返し方式のものだったり，
再帰的だったり，処理が関数に切り分けられていのものだろう。
【目的】
1.アルゴリズムを組む中で出会う，エラーの一つ一つに注目してほしい。
二分探索はエラーの宝庫なんだ。多くのバリエーションを作成していくうちに，
エラーに遭遇することが減っていくのを実感するだろう。
2.作ったバリエーションを見比べて見よう。どれが一番実用的か？
作ってて楽しかったか？完成まで大変だったか？
そして，何故そうっだったかを考えよう。
3.実際，二分探索について，5種類のオリジナルなやり方を見出すのは難しい。
どのようにして達成したか，柔軟な発想ができたかを振り返ろう。
【仕様】
二分探索メソッドを作成する。引数は，探したい値と，対象となる配列だ。
戻り値は，探したい値のインデックスまたは-1（見つからなかったとき）。
chop(int, array_of_int) -> int
配列の数は多くないと思っていい。計算時間やメモリ容量は，このKataでは
気にしなくていい。
【試験値】
def test_chop
assert_equal(-1, chop(3, []))
assert_equal(-1, chop(3, [1]))
assert_equal(0, chop(1, [1]))
#
assert_equal(0, chop(1, [1, 3, 5]))
assert_equal(1, chop(3, [1, 3, 5]))
assert_equal(2, chop(5, [1, 3, 5]))
assert_equal(-1, chop(0, [1, 3, 5]))
assert_equal(-1, chop(2, [1, 3, 5]))
assert_equal(-1, chop(4, [1, 3, 5]))
assert_equal(-1, chop(6, [1, 3, 5]))
#
assert_equal(0, chop(1, [1, 3, 5, 7]))
assert_equal(1, chop(3, [1, 3, 5, 7]))
assert_equal(2, chop(5, [1, 3, 5, 7]))
assert_equal(3, chop(7, [1, 3, 5, 7]))
assert_equal(-1, chop(0, [1, 3, 5, 7]))
assert_equal(-1, chop(2, [1, 3, 5, 7]))
assert_equal(-1, chop(4, [1, 3, 5, 7]))
assert_equal(-1, chop(6, [1, 3, 5, 7]))
assert_equal(-1, chop(8, [1, 3, 5, 7]))
end【Ans.1】 基本形。Javaです。
private int chop(int target, int[] array){
if(array.length==0){
return -1;
}
int begin = 0;
int end = array.length - 1;
while(begin <= end){
int mean = (begin+end)/2;
if( target < array[mean]){
end = mean -1;
}else if(target > array[mean]) {
begin = mean + 1;
}else{
return mean;
}
}
return -1;
}【Ans.1.1】 基本形。Rubyです。
def chop(target, array) rem = 0 while array.size >= 1 mid = ((array.size-1)/2).to_i case target <=> array[mid] when 1 array = array[mid+1,array.size] rem += mid+1 when 0 return mid+rem when -1 array = array[0,mid] end end return -1 end
CodeKata One - Supermarket Pricing
スーパーマーケットの商品の価格を決める，とてもシンプルな問題。
最も単純な価格付けは，
Case1 この商品は0.65$です。
一方で、厄介な場合もある。
Case2 3個まとめて買えば，1$です。（4個，5個買ったら？）
Case3 1poundで$1.99です。（4ounce買ったら？）
Case4 2個買ったら，3個目はただです。（3個目は0$？）
・1pound=16ounce=456g
【問題】
コーディングは必要ない。
Case1からCase4に対応できる，お金と価格を表現するモデルを考案すること。
また，モデルは汎用的であること。
つまり，レジでも在庫管理でも受注時でも使える。
それには次のPointに注意してほしい。
Point1 0.01$未満のお金は存在するのか？
Point2 端数は，いつ丸めるのか？
Point3 どのようにして価格決定のaudit trialを保障するか？
Point4 サービス代金と商品価格では状況は異なるか？
Point5 棚にある100個の商品がCase4方式だった時，在庫としてどれだけ価値がある？
・audit trial
監査証跡 かんさしょうせき
情報処理のプロセスが追跡できるようにした記録。
ログファイル等がこれにあたる。
（はてなダイアリーキーワード，より）
【目的】
自由なスタイルでモデル化することを練習してほしい。
たくさんの方法を考え付くこと。
それぞれのモデルについて，良いところと悪いところを考えること。
・どんな技術で実現できるのか？
・記録するのには？
・そのモデルが良いと，どうやったら証明できるか？
【Ans1】
・販売価格は，定価×割引率として決める。
・割引率は，タイプとパラメータによって定まる割引方式（Case2タイプ，Case4タイプ等）に購入数を与えて求める。
タイプCase2やCase4のものなど。
パラメータは，まとめ買い割引の単位個数や，その時の価格など。
・商品が売れると，商品名と日時をKeyとして，販売価格を記録する。
・同時に在庫管理にアクセスし，在庫情報を更新する。
・在庫価値は，仕入れ価格×個数で決める。
・よって利益は，（販売価格 - 仕入れ価格）の和になる。
シーケンス図へのLink
Code Kata コード＝カタ
Dave Thomas（Rubyを世界に紹介した達人プログラマ）
http://www.codekata.com/
・Kataは空手の型。もう英語化してるみたい。
【背景】
優れたミュージシャンになるには何が必要か？
音楽理論の習得や，楽器の仕組みを知ることは役に立つ。
才能もあればいいけど，究極は「練習」。
何度も何度も練習するんだ。
スポーツでも同じ。
マッチョな体や才能もいいけど，
プロは一日に何時間も練習する。
ところが，ソフトウェア開発者はどうだろう？
ぶっつけ本番じゃないだろうか？
仕事の中で練習しているから，失敗するんだ。
プロの仕事と練習を切り離そう。
僕らには練習が必要だ。
【Kataとは】
練習に必要なのは，邪魔されない時間と，
試したくなるシンプルな方法だ。
何度も繰り返して，失敗に慣れる必要がある。
毎回，フィードバックを行えば，必ず向上していく。
仕事じゃなくて，プレッシャーがないことも大切だ。
練習が楽しくなる。
続けるうちに自分が進歩したって気がつくだろう。
Code Kataは，こんな練習の考え方を，
ソフトウェア開発に適用する試みだ。
Kataは空手の反復練習法で，続けることで，
日々，ちょっとづつ進歩できる。
Code Kataの意図はそこにある。
それぞれのKataは小一時間で試せる。
時にはコーディングが必要だけど，やり方は自由だ。
コーディングよりも，もっと背景にあることが，問題の主題だったりもする。
問題には正解なんか無いことのが多いだろう。
でも大事なのは，学ぶ過程で身に付いていくものだ。
それに，僕が新しいkataをどんどん追加していくだろうけど，
是非，頑張ってみてほしい。
Kataについて話がしたかったらメーリングリストがある。
http://tech.groups.yahoo.com/group/CodeKata/
Google社内ツアーの映像
リンク先のClipをクリック。
で紹介されていたので，引っ張ってきました。
Dean Takahashiさんが，Googleの広報に連れられてのツアーを，
リポートしています。
途中，カフェテリアのシーンがあるのですが，
ターバン巻いている人や，中国っぽい人が目立ちます。
このTakahashiさん声のトーンが低くて，・・・私には聞き取りにくい。
時折，Microsoftとは対照的だ，とか，これが秘密兵器です。
など聞こえるのですが，細部がわからない・・・。
Link:こちらは記事版（mercurynews.comへの登録が必要）
記事を読んだところ，Googleでは次のことが，タダで，社内（社屋のことをキャンパスと呼ぶ）で，
できるそうです。
- 食事（マイクロソフトはジュースだけタダ）
- 洗濯
- シャワー
- スポーツジム
- infinity pools（多分，泳いでも進まない逆流プール）
- バレーボールコート
- マッサージ
- 診察
- 託児所
- 仕事にペット連れOK
こんな手厚い福利厚生について，記事では次のように書かれています（引用）。
The Google founders came from academia and they wanted a university setting. That means casual rules, lots of eager young thinkers, and benefits that keep employees loyal.
一方で，こうも書かれています（引用）。
Those doctors can better understand issues the Google workers suffer from, like ergonomic issues or wear and tear from long hours.
至れり尽くせりもいいですけど，自分の体は大切にしたいトコです。
