お試しの最近のブログ記事

MapReduce in Scala

| # Comments
この記事は Scala Advent Calendar jp 2010 の9日目です。

と言いつつ空気を読まずにMapReduceやっちゃいますよ。
簡易的にではありますが、GoogleやHadoopでおなじみ(?)のMapReduceフレームワークをScalaで実装してみました。

というわけで、これを実装したときのポイントや便利な機能などを挙げていこうと思います。

ダイクストラ法

| # Comments
最短経路問題を解くためのアルゴリズムである「ダイクストラ法 (Dijkstra's Algorithm)」というのをScalaで実装してみました。

参考にしたのは ダイクストラ法(最短経路問題) です。

ダイクストラ法 (Dijkstra's Algorithm) は最短経路問題を効率的に解くグラフ理論におけるアルゴリズムです。スタートノードからゴールノードまでの最短距離とその経路を求めることができます。

正しく実装出来ているかどうかはよくわかりません。。。

居眠り床屋問題

| # Comments
ScalaのActorのお勉強がてら、「居眠り床屋問題」というものに挑戦してみました。

居眠り床屋問題 どう書く?org

並行処理のお題です。ある床屋の亭主は、客がいないときまって居眠りを始めます。床屋店内には三台の散髪兼順番待ち用の椅子があり、客は来店時に椅子に空きがあれば、いずれかに勝手に座って自分の番が来るのを待ち、散髪を終えてから店を出ます。空席が無ければそのまま何もせずに立ち去ります。居眠り中の亭主は、客の入店時に起こされると待ち客すべてをひとりずつ順に散髪しますが、誰もいなくなればまた居眠りを始めます。

この床屋店に16人の客が訪れた日のシミュレーションを行なうコードと、その結果(下に例として示したログ形式。「[スレッドのIDなど] イベント描写」の一覧と終了後の総括)を出力して示してください。なお、散髪には一人当たり100~400ミリ秒の時間(この範囲でランダムに変化)を要し、客は通常 0~200ミリ秒(同)の間隔で訪れます。ただし例外として9番目の客だけは前の客から1200ミリ秒程度の間隔(すなわち、最大三名の待ち客全員を散髪し終えるのに十分な時間)をあけて訪れるものとします。

実装に際し、実行時のデッドロックの回避はもちろんですが、そのほかにも、競合状態(席の空きを確認して座ろうとしたら、もう別の客が座っていた...というような事態)などの不整合も生じないよう配慮し、必要であればそのための対策を講じてください。たとえば来客の間隔が仮に0ミリ秒で固定の場合(つまり、客が一斉に来店した場合)でも、コードが正常に動作するかどうか試してみるのもよいかもしれません。


若干手抜きでログ出力などが設問通りではありませんけど。

どう書く?orgにて、なぜかどうしても気になる問題があって頭を悩ませてしょうがないのでまじめに考えてみました。

2^i * 3^j * 5^k なる整数

2^i * 3^j * 5^k の形で表される整数を小さい方から順に 100 個列挙するプログラムを書いてください。 i, j, k は 0 以上の整数です。アルゴリズムのオーダーについても考えてみてください。

例えば最初の 10 個は次のようになります:

 1 = 2^0 * 3^0 * 5^0
 2 = 2^1 * 3^0 * 5^0
 3 = 2^0 * 3^1 * 5^0
 4 = 2^2 * 3^0 * 5^0
 5 = 2^0 * 3^0 * 5^1
 6 = 2^1 * 3^1 * 5^0
 8 = 2^3 * 3^0 * 5^0
 9 = 2^0 * 3^2 * 5^0
10 = 2^1 * 3^0 * 5^1
12 = 2^2 * 3^1 * 5^0

※解答では i, j, k の各値を示す必要はありません。

9arrows

| # Comments
9arrows

プロジェクトの成果物を細分化し、担当者割り振りやスケジュール・進捗状況の管理を行うWBS(Work Breakdown Structure:作業分解図)。
プロジェクトを管理する上で欠かせないこの手法を中心に、チームとしても個々としても作業を効率的に進められるようになるツールです。

ということですので、試してみることにします。

PostgreSQLで構築されているようですが、手元に環境がないのでMySQLで動くようにしてみようと思います。

Twitter Icon

AdSense

Creative Commons License
このブログはクリエイティブ・コモンズでライセンスされています。
Powered by Movable Type 5.14-ja

Google検索

カスタム検索

2013年10月

    1 2 3 4 5
6 7 8 9 10 11 12
13 14 15 16 17 18 19
20 21 22 23 24 25 26
27 28 29 30 31