KLab若手エンジニアの これなぁに？

12/16（水）に、先日の交流会でお世話になりましたクックパッド様を弊社にお招きして勉強会を開催いたしました！

今回は、クックパッド様から2テーマ、KLabから2テーマの発表がありました。

まずは、KLabから nagai-k が『OpenSocialアプリ入門』というテーマで発表しました。

ソーシャルアプリではどんな風なやりとりが行われているのか、APIの使い方など、ソーシャルアプリの基本となる部分について、分かりやすく解説していただきました！ソーシャルアプリといえば、今もっとも熱い分野のうちのひとつです！弊社でも開発に力を入れており、クックパッド様からも弊社側からも多くの質問が上がり、まさにホットな話題を提供してくださいました！
発表資料はこちら！

次に、同じくKLabから sasaki-k が『全文検索エンジンSolr試食』というテーマで発表しました。

全文検索エンジンSolr（ソーラ）のしくみ、実際に使ってみての気づきなどを発表してくださいました！（魚）料理の試食になぞらえての発表で、笑いを誘いつつ大いに盛り上がりました！Solrはまだ知名度の低い技術ですが、今回の勉強会で注目してもらえたのではないか、とsasaki-kも手ごたえのあった様子（後日談）。これからの動向に期待大です！！
発表資料はこちら！

続きまして、クックパッド様の発表に移りました。

まずは、最高技術責任者（！）の橋本様から、『クックパッドのRailsリニューアル』というテーマで発表いただきました。

なんと、Railsがまだベータ版だった2005年から、そのすばらしさに自信を持っていらっしゃったそうです！また、クックパッドサイトのリニューアルは2008年に行われたそうなのですが、その前に「たべみる」というサイトを、なんと開発開始からわずか1ヶ月でオープンさせることができたそうです！そのスピード感…尊敬します！！

次に、開発の森田様から、『Railsでのテスト駆動開発』というテーマで発表いただきました。

クックパッドサイトの開発中に、どのようなやり方でテストを行っているのか、実例も交えながらお話していただきました！かなり内部的なことも係ってきてしまうので、詳しくお伝えできないのが残念ですが、実際のテスト時の動作画面も見せていただくことができました！こういった勉強会の場でなければ見られない、貴重な体験をさせていただき、本当にありがとうございました！！

ここで、勉強会は一旦終了し、懇親会に移りました。
懇親会では、お酒も入りｗ、クックパッド様と弊社の技術者が語らう、熱い夜となりました！！

お越しいただいたクックパッドの皆様、本当にありがとうございました！

Haskellで、TCPのサーバーを書いてみたいと思い、手始めにエコーサーバーを書いてみました。
エコーサーバーというのは、クライアントからの入力をそのまま返すサーバーです。

以下の記事を参考にもっと簡単なものを作ってみます。
A simple TCP server | The Haskell Sequence

main = withSocketsDo $ do
         [p] <- getArgs
         let port = fromIntegral (read p :: Int)
         soc <- listenOn $ PortNumber port
         putStrLn $ "start server, listening on: " ++ show port
         acceptLoop soc `finally` sClose soc

main部分です。
ソケットを開いてlistenします。

acceptLoop soc = do
  (hd, host, port) <- accept soc
  forkOS $ echoLoop hd
  acceptLoop soc

mainのあとの処理です。
クライアントがきたら、accept(受け付け)して、新しいスレッドを生成し、そちらに処理を任せます。
新しいクラアントに対応しつづけるため、処理が終わってはいけませんので、こちらは無限ループを続けます。

echoLoop hd = do
  sequence_ (repeat (do { -- ioアクションの無限リスト
                          l <- hGetLine hd;
                          hPutStrLn hd l;
                          hFlush hd
                     }))
  `catch` (\(SomeException e) -> return ())
  `finally` hClose hd

クライアントごとの処理です。
こちらは、一行読み込んで一行そのまま書き込むという処理を繰り返しているだけです。

さっそく実行してみましょう。

$ ghc -o echoHS -O --make -threaded echosimple.hs
$ ./echoHS 8080
start server, listening on: 8080

別のコンソールをひらきアクセスしてみます。

$ telnet localhost 8080
hoge
hoge
aiu
aiu

できました！
30行程度で、エコーサーバーが完成しました。
ついでにRubyでも同じものを書いたのでそちらも掲載しておきます。

Continue reading »

天下一プログラマー実行委員の takada-at です。
今回は、本戦１日目の1問目にあたる「障害物ありNクイーン」を紹介します。

解答

20
-Q--*******Q----
---Q*******--Q--
----******-----Q
-----****Q------
-----***------Q-
------*-Q-------
----------Q*****
Q---------******
--Q-------******
----------Q*****
-----Q*Q--------
-----***-----Q--
----Q****------Q
----******--Q---
----*******---Q-
----*******Q----

問題について

エイト・クイーン・パズルの変形版です。問題文にある通り、他のクイーンが一手で移動できるマスを避け、盤面上にクイーンを置いていきます。

 ----*******-----
 ----*******-----
 ----******------
 -----****-------
 -----***--------
 ------*---------
 -----------*****
 ----------******
 ----------******
 -----------*****
 ------*---------
 -----***--------
 -----****-------
 ----******------
 ----*******-----
 ----*******-----

まず素朴にこのパズルを解く方法を考えてみましょう。
以下では、縦のラインを「列」、横のラインを「行」と呼ぶことにします。
左からi列目、上からj行目のマスを(i,j)と書きます。i,jは0から数えます。

各行に対し、左から右、上の行から下の行へクイーンを置いていくとしましょう。
最初に(0,0)に置いた場合、このクイーンの経路には他のクイーンは置けませんから、次にクイーンを置けるマスは(12,0)、さらにその次に置けるのは(2,0)となります。
最初に(1,0)に置いた場合は、次にクイーンを置けるマスは(12,0)、さらにその次に置けるのは(3,0)となります。

-最初に(0,0)に置いた場合

Qxxx*******Qxxxx
xxQx*******-----

-最初に(1,0)に置いた場合

xQxx*******Qxxxx
xxxQ*******-----

このように、「(0,0)に置く？ / 置かない？」「(0,1)に置く？ / 置かない？」というそれぞれの選択肢が運命の分かれ道となり、それによってその後にクイーンを置けるマスが変わっていきます。左側の矢印を「置く」、右側の矢印を「置かない」として、次に置けるマスを図示しますと、以下のようになります。

問題は、これらの経路の内、「置く」を選んだ回数が最大のものを探すことです。

アルゴリズム

このようなグラフの探索問題を解くアルゴリズムにはいくつかバリエーションがありますが、ここでは「深さ優先探索」を使います。
他にも代表的なアルゴリズムとして「幅優先探索」がありますが、エイト・クイーンのような問題の場合、考慮すべき経路の量が多く、ふさわしくありません。
http://ja.wikipedia.org/wiki/深さ優先探索
http://ja.wikipedia.org/wiki/幅優先探索

深さ優先探索の実装は、スタックを利用するか再帰を利用するのが一般的です。
Rubyで再帰を利用した場合の探索部分を以下に示します。

def depthFirst x, y, h
    return h if (h[:map].size==y) #それ以上行がないので終了
    max = h
    x.upto(h[:map][y].size-1) do |x1|
    # y行目でx列目より右の、クイーンを置くことができるマスのそれぞれについて...
        next if h[:map][y][x1] != BRANK
        nmap = deepcopy(h[:map])
        setQueen(nmap, [x1,y])
        #クイーンを置いてみて、その後の運命を見定める
        r = depthFirst(x1+1, y, {:map=>nmap, :count=>h[:count]+1})
        #最大のものをとる
        if(max[:count] < r[:count])
            max = r
        end
    end
    #あえて置かないという選択肢も調べる
    r = depthFirst(0, y+1, h)
    if(max[:count] < r[:count])
        max = r
    end
    max
end

日本語で書くと以下のようになります。

• y行目でx列目より右で、クイーンを置くことができるマスのそれぞれについて、
  • とりあえずクイーンを置いてみて、その右のマスに対し同じ操作を繰返す
  • それぞれの結果の内最大のものを取る
• 行の右端まで行ったら下の行へ行く
• それ以上行がなくなったら終了

あとはデータ構造です。
単純に考えれば盤面は二重配列にするのがよいでしょう。最適化を考え、ビットの配列にしてもよいですが、「何もない場合」「障害物」「クイーン」「クイーンの経路」といった状態が考えられるため、ビットの配列を複数持つ必要があります。
また、クイーンの数を比較するため、クイーンの合計数を盤面とは別に持つのもよいでしょう。

最適化

さて、以上を実装して解答が出れば話は簡単なのですが、この問題の場合、計算量の多さがネックになります。
素朴に解こうとすると一時間では計算が終わらないということにもなりかねません。
そこで、いくつか最適化の手段を考えていきましょう。

まず何度も繰り返すことになるクイーンの配置を最適化します。すべてのマスに対するクイーンの経路をあらかじめ計算してキャッシュ(メモ化)おきましょう。
あらかじめ計算しておけば、すべてのマス(障害物以外)を一度ずつ処理するだけで済みます。
経路の探索中は、同じマスに対し何度も何度もクイーンを配置する処理が必要になりますから、計算結果のキャッシュが有効にはたらくはずです。
さらに言えば、左から右、上から下に処理していくため、クイーンの経路は「右、右下、下、左下」の4つのみ考慮すれば済みます。左上や左にすでにクイーンがあった場合はそもそもそのマスにはクイーンを配置できません。

--x-*******-----
---xx****-------
xxxxQx*---------
---xxx-----*****
--x-x-x---******
左上、左、上にクイーンがないことはすでに確定しているため、考慮しなくていい。

また、以下のようなメモ化も考えられます。
パターン1とパターン2は違う盤面ですが、下から2つの行だけを見ると、同じ状態になっています。
ということは、下から2つの行を処理をする際にはどちらの場合でも同じ結果が出てくるはずです。つまり、「残りの行」の状態をキーにして結果をキャッシュして置くことで、いくつかの分岐を省略することができます。
とりわけ探索の後半は、ほとんどクイーンの経路で塗りつぶされた盤面を処理することになるはずですから、この処理が有効なはずです。
ただし、これによってメモリを食うことにもなるので、どの程度このキャッシュを働かせるかは微妙な選択でしょう。実際、言語によっては、このメモ化をしない場合の方が速くなることもありました。

---Q
Qxxx
xxQx
xxxx
x-xx
xxxx
パターン1

----
--Qx
Qxxx
xxxQ
x-xx
xxxx
パターン2

この探索の場合、網羅性を考えると、最適な配置のために「置ける場所にあえてクイーンを置かない」という選択肢も検討する必要があります。しかし、これによって探索する経路が大分増えてしまうのも事実です。
仮に「あえて置かない」選択肢を取らなかった場合の計算量が「n の m乗」(選択肢の数+深さ)だったとすると、「あえて置かない」選択肢を追加することで、概算で「(n+1) の m乗」にまで経路が増えてしまいます。
さらに言えば、「この行にはあえて置かない」という選択を10回繰り返したあとの経路などは、クイーンの数が最大になるとは考えづらいため、検討する必要がないものです。
よって、「あえて置かない」選択肢の回数を制限することにしましょう。この場合網羅性を犠牲にしているので、「クイーンの数が最大であること」を示さなければなりません。しかし「あえて置かない」選択肢の許容量を順次増やしていくことで最大の解を検討することもできるはずです。ところでその際、90度回転してから探索をはじめた方が都合がよくなります。これはこの盤面の特性によります。
障害物で分断された行(or列)のそれぞれを「ブロック」と呼ぶことにしましょう。縦のラインには、22ブロック(2つに分割された列が6、分割されていない列が10)あります。横のラインには、28ブロック(2つに分割された行が12、分割されていない行が4)あります。
縦または横のラインだけを見ていっても、1ブロックにクイーンを1つしか置けないのはあきらかです。つまり、縦のラインを見ていくと、この盤面におけるクイーンの最大値は22であることが明らかになります。縦のラインの方が最大値が低いため、横回転して縦のラインを基準に考えた方がよいのです。

実際には、この盤面の場合、「あえて置かない」選択肢の数は1回で十分であることがわかります。
計算を実行してみると、以上の最適化を組み合わせることで、Rubyでも10分程度、Haskellなどでは5分以下で解にたどりつくことができました。
解は以下のようになります。

20
-Q--*******Q----
---Q*******--Q--
----******-----Q
-----****Q------
-----***------Q-
------*-Q-------
----------Q*****
Q---------******
--Q-------******
----------Q*****
-----Q*Q--------
-----***-----Q--
----Q****------Q
----******--Q---
----*******---Q-
----*******Q----

この盤面が最大であることの証明は以下のようになります。
縦のラインに注目しましょう。クイーンが置かれていないブロックは(6,j)の列と、右から4列目、(11,j)の列だけです。ということは、もしクイーンを増やせるとしても、最大で2つにとどまります(1ブロックにクイーンを1つ以上置くことはできません)。

つまり余地が一つしかない以上、「2ブロック見逃す」という選択肢を考慮することで、置けるクイーンの数が増えることはありえません(理論上の最大値が22である以上、2つ見逃した時点で、20を超えることはないはずです)。
以上より、この解が最適解の1つであることがわかりました。

Ruby, Python, Haskellによるコードの例を以下に掲載します。
(Haskellは解答用言語に含まれていませんでしたが、おまけです)。

Continue reading »

ども、amo-kです。

先日デプロイ時に実況中継するIRCボットを作ったのでこれについて。

KLabでは通常、
テスト/本番環境に最新のプログラムソースコードを反映する際に
以下のような手順を踏む。

１．踏み台サーバにログイン
２．SVN Export
３．アーカイヴ作成
４．テスト/本番環境にアーカイヴをアップロード
５．テスト/本番環境のコマンドを実行し、アーカイヴ解凍、各Webサーバに同期
６．お掃除

通常はこれを１コマンドで実現するためにデプロイスクリプトを書いて
そのスクリプトを実行する事でデプロイすることとなる。

その際に、デプロイした人はターミナルをチェックしていれば
スクリプトの標準出力で進捗を把握できるが、たの案件メンバは解らない。
そこで、デプロイ実況中継をするIRCボットを作ってみた。

今回は特定のキーワードに反応したり、待機する必要がないので
各ステータス毎にIRCサーバに接続、チャンネルJOIN、レポート、切断ということをする
非常に単純なボットを作った。

以下、IRCクライアント画面サンプルとサンプルソースコード
工夫した点は特に無いが、ライブラリを使わずに
TCPコネクションを張ってIRCサーバと通信している点が若干特徴的かもしれない。
IRCクライアント画面キャプチャサンプル

サンプルコード

#!/usr/bin/ruby

require 'socket'

chan = ARGV[0]
msg  = ARGV[1]

sock = TCPSocket.open("localhost", 6667)
sock.send("NICK DeployBot\r\n", 0);
sock.send("USER DeployBot localhost localhost :DeployBot\r\n", 0);
sock.send(sprintf("JOIN #%s\r\n", chan), 0);
sock.send(sprintf("NOTICE #%s :<-------------- %s -------------->\r\n", chan, msg), 0);
sock.send("QUIT\r\n", 0);
sock.readlines
sock.close

最初はphpでsocket関数を使って実装しようと思ったんだけど
実は踏み台サーバでsocket関数が有効になっていなかったので、設定するのが面倒でもうRubyで杜撰に書いちゃおうと思ってRubyで書きましたｗｗ

amo-kさんにつづき、私(takda-at)もHTTPクライアントを実装してみました。
まずはRubyのコードです。Rubyでは、socketというネットワークプログラミング用のライブラリが標準で用意されています。その中でもTCPSocketなどのクラスを利用するとHTTPクライアントなども非常に簡単につくれるのですが、今回は勉強のため、あえて低レイヤーなところから書いています。

socketライブラリの中でも、Socketクラスは、ソケットをシステムコールレベルで操作するための機能を提供しています。メソッド名などもシステムコールと同じ名前が採用されているようです。
Rubyリファレンスマニュアルの説明にはそこまで詳細な解説が無いので、LinuxなどのManPageも合わせて見た方が参考になります。
また今回は勉強のために、socketライブラリのソースコードも少しのぞいてみました。socketライブラリはC言語で書かれたRubyの拡張ライブラリです。最新の安定板であるRuby1.8.7では、ruby-1.8.7-p72/ext/socket/socket.c にソースコードがあります。

参考
-Socket - Rubyリファレンスマニュアル-
-Manpage of SOCKET
-Manpage of GETHOSTBYNAME

難しかったのはSocket::connectを呼び出し、接続を行なうところです。このメソッドの引数には、バイナリデータを文字列の形でわたします。C 言語のconnect関数には、引数として、sockaddr構造体というものをわたすのですが、Socket::conncetメソッドの場合、Rubyの側からCの構造体を文字列の形でわたしてやる必要があります。
Rubyで、データをバイナリ文字列に変換するにはArrayクラスのpackメソッドを利用します。
Rubyでバイナリデータを扱うプログラムを書いたのははじめてだったので、非常に勉強になりました。

参考
-Manpage of CONNECT
-Array::pack - Rubyリファレンスマニュアル
-packテンプレート文字列 - Rubyリファレンスマニュアル

Continue reading »

Ruby でHTTP通信をする方法はいくつかあります。
最も簡単なのは、open-uriを使う方法でしょう。

単純にあるURIに対してGETリクエストを送り、返されたHTMLを表示するだけなら、以下のように１行で済ませることもできます。

$ ruby -ropen-uri -e 'open(ARGV[0]){|f| puts f.read }' http://www.klab.jp/

Continue reading »