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でのテスト駆動開発』というテーマで発表いただきました。

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

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

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

umjammer です。

ネタがホットなうちに、

Google Japanese Input が出ました。変換効率が各地で話題になってますね。
Mac な私も早速導入してみたのですがメニューバー上に表示される変換モードの
アイコンがいまいちキレくありません。ことえりのアイコンと比較してみたところ
サイズが微妙に違うみたいでリサイズされて少しボケた感じになっています。

私は目が結構いい方で、気になって仕方が無いのでことえりのアイコンの色を
変更したアイコンを作成してみました。満足のいく仕上がりになりましたので
公開します。

ライセンスが微妙なので個人利用にとどめてくださいね。

• 直接入力アイコン
• ひらがなアイコン

あと私は「ひらがな」と「直接入力」しか使わないのでとりあえず二つです。

作り方は
/System/Library/Input Methods/Kotoeri.app/Contents/Resources
にあることえりのアイコンを

Gimp の場合

1. 画像/モード で RGB に変換
2. 色/着色 で 色相 228 彩度 68 輝度 34 に変換
   (本家と同じ色にするためにはもう少しがんばれます)
3. PNG としてセーブ

このように変換して、
/Library/Input Methods/GoogleJapaneseInput.app/Contents/Resources
にある等価なアイコンに上書きすればOKです。

見た目にこだわる人はお試しください！

PS

この Blog も Google Japanese Input で書いてみました。悪いけどことえりさんサヨウナラ。

こんにちは。takei-hです。

ちょっと時間が経ってしまったのですが、アシアル株式会社、KLab株式会社の合同勉強会でMessagePackとPHP Extensionについて発表しましたので、資料を公開します。

また、PHP Extensionもだいたい形になったので、公開します。

MessagePack PHP Extensionのダウンロード

Continue reading »

秋の寒さが、木の葉を赤く染める季節になりましたね。みなさんいかがお過ごしでしょうか。
我々若手は、寒さを吹き飛ばすほど熱く燃えております！！

ということで、本日のお昼時、クックパッド様と技術者交流会を行いました。
今回は特にサーバやDBなどのインフラ周りのお話を中心に、楽しい時間を過ごさせていただきました。私は常日頃アプリ側をやっておりますので、今回のインフラ談義はとても勉強になりました！PC向けかモバイル向けか、参照が多いサイトか更新が多いサイトか、ということろで最適なインフラ構成は違ってくるんですね。サーバ/インフラを支える技術 ~スケーラビリティ、ハイパフォーマンス、省力運用を読んでもっと勉強しよう！

また、談義中、社員の方が作ってくださったランチを頂きました。ほうれん草のサラダ、牡蠣のグラタン、きのこリゾット。どれもおいしく頂きました♪ごちそうさまでした！

そして最後に、素敵なキッチンの前で記念写真。ありがとうございました！

勉強会の共同開催など、今後も積極的に外部との技術交流を図っていきます！

こんにちは。takada-atです。

先日開催されたアシアル株式会社、KLab株式会社の合同勉強会で発表しましたので、資料を公開します。

携帯絵文字の文字エンコーディング変換およびキャリア間のマッピングについてKLabでの対応をご紹介させて頂きました。

資料は以下にあります。

■携帯絵文字をutf-8エンコーディングにする話

tadaka-atです。

最近Haskellの記事ばかり書いていますが、PHPも書いてます！ということでPHPのライブラリを公開しました。

■PictgramConverter

サポートする機能は

• 絵文字sjisバイナリをutf-8バイナリに変換
• キャリア間の絵文字変換

「ShiftJISからutf-8への文字コード変換とともに、絵文字もutf-8エンコーディングに変換」「異なるキャリアの絵文字も表示キャリアに合わせて変換」という処理が手軽にしかも高速にできるすぐれものです。

インストールは以下のコマンドで完了します。

$ pear channel-discover openpear.org
$ pear install openpear/PictgramConverter-alpha

詳しく知りたい方は以下の勉強会資料もごらんください。
アシアルKLab合同勉強会で発表しました

takada-atです。
前回HaskellおよびRubyでエコーサーバーを発表したところ、エコーサーバーおよびネットワークプログラミングの基礎について、社内でいろいろな指摘を受けました。
今回は、指摘された点をひとつひとつ改良していきたいと思います。

リンク: Haskellでエコーサーバー

ポート番号

実は恥しながらRFCにエコーサーバーの規定があるのを知らなかったのですが、一般に「エコーサーバー」と言った場合、正式には「RFC862 - Echo Protocol」のサーバー実装を指すことが多いようです。
http://www.faqs.org/rfcs/rfc862.html

RFC862では、エコープロトコルのポート番号に 7 を割り当てています。

A server listens for TCP connections on TCP port 7.

もちろん1024以下のポート番号を利用するには、ルート権限が必要ですが、可能ならポート番号7を利用することが望ましいでしょう。

forkについて

forkしたあと、親プロセスでハンドラを閉じていないという指摘を受けましたが、これは誤解で、GHCの「forkIO」「forkOS」は、forkシステムコールとは無関係な、スレッドを新たに生成する関数です。名前が少しまぎらわしいですね。
なお余談ですが「forkIO」は疑似スレッド、「forkOS」はネイティブスレッドを生成します。
さらに余談ですが、http://ja.wikipedia.org/wiki/食事する哲学者の問題って、ひょっとして「フォーク」と「fork」をかけてるんですかね？ 大発見だと思ったんですが、全然関係ない上に間違ってますか、そうですか……。

参考リンク: Control.Concurrent

シグナルハンドリングについて

いくつかのシグナルをハンドリングしておかなければ、クライアントの動作によってサーバー自体がダウンしてしまいます。
特に危険なのがSIGPIPEです。
ソケットに対し、書き込みを行なった場合、相手側がすでにclose状態だとこのシグナルが発生します。デフォルトの動作ではプロセスが強制終了してしまいます。

参考リンク:
シグナル (ソフトウェア) - Wikipedia
SIGPIPE - Wikipedia, the free encyclopedia

以上をふまえた上で、高レベルAPIを提供するNetworkライブラリではなく、より低レベルなNetwork.Socketライブラリを使うように書き換えてみます。

main部分は以下のように変わりました。

main = withSocketsDo $ do
         let port = fromIntegral 7
         soc <- socket AF_INET Stream 0
         addr <- inet_addr "0.0.0.0"
         let sockaddr = SockAddrInet port addr
         bindSocket soc sockaddr
         listen soc 5
         -- mainスレッドではいくつかのシグナルをブロック
         blockSignals $ list2set [sigPIPE]
         putStrLn $ "start server, listening on: " ++ show port
         acceptLoop soc `finally` sClose soc

list2set = foldr addSignal emptySignalSet

read, writeについて

以前のバージョンではソケットからの読み込み・書き込みにhGetLine, hPutStrLnを利用していたのですが、これを使うと、サーバー・クライアント間の改行コードの違いなどによって問題が発生しうるという指摘を受けました。
エコープロトコルの実装としては、行ごとの読み込みではなく、文字列をすぐ読み込んで書き込む方が望ましいでしょう。

def echo_do(soc)
    while true
        buf = soc.recv(1)
        soc.write(buf)
    end
end

テスト

以上の動作確認をtelnetを手動で立ち上げて確認するのではなく、Rubyによるテストスクリプトを作成し、こちらで動作確認を行なうことにしました。

require 'test/unit'
require 'socket'

class EchoTest < Test::Unit::TestCase
    def test_echo
        #エコーのテスト
        soc = TCPSocket::new("localhost", 7)
        ["abc", "ab\na", "\n"].each do |s|
            soc.write(s)
            buf = soc.read(s.size)
            assert_equal(s, buf)
            puts buf
        end
        soc.close
    end
    def test_concurrent
        #同時接続のテスト
        socs = []
        3.times do |i|
            Thread::fork(i,socs){ |i, socs|
                sleep 0.1
                soc = TCPSocket::new("localhost", 7)
                s = "hoge"
                soc.write(s)
                buf = soc.read(s.size)
                assert_equal(s, buf)
                puts buf
                socs << soc
            }
        end
        (ThreadGroup::Default.list - [Thread.current]).each {|th| th.join}
        socs.each {|s| s.close}
    end
end

ソースコード

Haskell版とRuby版、修正したものを以下に掲載します。
なお、Haskell版のコンパイルはthreadedオプションを付け以下のようにやってください。

ghc -threaded --make -o echo2 echo2.hs

Continue reading »

先週の日曜日、弊社若手社員３人でICPC東京大会を観戦、懇親会にも参加させていただきました。
（ICPCの公式ページはこちら→ACM/ICPC Asia Regional Contest 2009, Tokyo, Japan）
今回は弊社もスポンサーとして、ICPCと学生プログラマーの支援をさせていただきました！

ICPCの会場に入るや否や、さっそく大きな歓声が！！
そう、そこで行われていたのは「Javaチャレンジコンペ」という、各チームが短時間で作成したAI同士の熱い戦いです。

こういったAI同士を競い合わせる競技は熱く盛り上げれますね。次回天下一プログラマー大会の参考にさせていただきます！

本選の優勝者は「HITORI#｣チーム。チームの一人は天下一プログラマーコンテストの優勝者です。他にも天下一プログラマーに参加されていた方々が多数入賞されていました。おめでとうございます！！

表彰の後の懇親会ではinada-nがスピーチをさせていただきました。

今後も、プログラミングコンテストの主催や後援を通して、学生プログラマーを応援していきたいと考えております！
夏に開催された天下一プログラマーコンテストが気になる方はこちらにアクセス！！

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 »