おとうさん、ぼくにもYコンビネータがわかりましたよ！ - 2009-04-09 - きしだのはてな
やっと、Yコンビネータが何を意味するものなのか、どういう意義があるのかがわかりました。 名前を使わず再帰ができますよ！というだけのものじゃなかったのですね。 まずλありき 関数の話をしたいのです。 そのとき、いちいち hoge(x) = x * 2 としてhogeを・・・、とか名前をつけて話を進めるのがめんどうなので、関数を値としてあらわすと便利ということで、λという値を定義するのです。 そうすると、上のhoge関数なんかはλ(x)(x*2)などとあらわせますが、引数をあらわすのに()を使うといろいろまぎらわしいので、 λx.x*2 のように表記します。 というのがλ。 このとき、λになにかわたされたら、引数としてあらわされる部分を単純におきかえます。 (λx.x*2)y とあったら、xの部分をyでおきかえて (λx.x*2)y → y * 2 となります。λの引数部分を与えられた引数で置
メッセージキューを使って分散MapReduceを実装する 2009-02-16 - きしだのはてな
さて、JMSでメッセージキューも使えるようになって、HadoopでMapReduceも試してみた。そうするとやりたくなるのがメッセージキューを使った分散MapReduceの実装ですね。ということで、JMSを使ってメッセージキューによる分散MapReduceをやってみました。実際にはローカルでしか動かないのですが、コンセプトモデルということで。 メッセージキューで遊びたいのでJMSを試す HadoopでのMapReduceを気軽に試すサンプル Hadoopサンプルで作ったのと同じように、クラスがJavaファイル中でimportされている回数を数えてみます。 考え方として、ちょっと強引ですが、GoogleやHadoopのMapReduceは分散ファイルシステム付きメッセージキューといえます。けど小規模につつましくやる分には分散ファイルシステムは必要ないので、MapとReduceを分散することだ
GoogleのMapReduceは僕たちに必要か？ - きしだのはてな
ということで、Google MapReduceの実装であるHadoopを使ったMapReduceと、JMSを使ったMapReduceをやってみました。 メッセージキューを使って分散MapReduceを実装する HadoopでのMapReduceを気軽に試すサンプル これ何のためにやったかというと、そこらにあるような数十台規模のサーバーを前提としたときに、Hadoopの有効性、ひいてはその元になってるGoogle MapReduceの有効性について疑問に思ったからです。そこで、ちょっと試してみた、と。 ここで、メッセージキューを使った場合に1秒でできてた処理が、Hadoopを使うとスタンドアロンモードでも40秒近くかかりました。擬似分散モードだと4分近くです。 いくらHadoopの実装がひどいとしても、これはあんまりです。 Googleでの実装はもっと効率的なものになっていると思いますが、そ
計算量を具体的に見てみる 2009-01-06 - きしだのはてな
アルゴリズムの話では、計算量の解析がかかせません。 計算量はオーダー記法で表されますが、これは、データの入力量に対してどのくらい時間がかかるかをあらわしたものです。 こういった話はどのアルゴリズムの本にも載ってるはずですが、具体的にどのようなプログラムを書くとそのオーダーになるかという記述はあまりありません。 ということで、やってみました。 計算時間表示のための共通処理を行うクラスは、一番最後に書いてます。 O(1) 計算時間がO(1)のアルゴリズムは、処理が入力の量によらない場合です。 配列の要素のアクセスや、ハッシュテーブルによるデータ検索、連結リストへの追加削除などがこれにあたります。 コードには入力量でのループが含まれません。 public class O1 extends ViewCompFrame{ @Override void compute(int n) { proc();
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
