スキップしてメイン コンテンツに移動

投稿

3月, 2009の投稿を表示しています

ErlangでFizzBuzz問題、それをC++のテンプレートで表現する

今更ながらFizzBuzz問題を解いてみる。今回はErlangで解いてみた。それだけだとつまらないので、それをC++のテンプレートで表現してみた。因みにErlangを使っているけど並列処理はしていない。

まずは普通に何の工夫もなく書いてみた。

-module(fizzbuzz). -export([fb/1]). fb(0) -> ok; fb(N) -> fb(N - 1), if N rem 15 =:= 0 -> io:put_chars("FizzBuzz"); N rem 3 =:= 0 -> io:put_chars("Fizz"); N rem 5 =:= 0 -> io:put_chars("Buzz"); true -> io:write(N) end, io:nl().

うーん、面白くない。どうせなら if をなくしてしまおう。というわけで、今度は以下のように書いた。

-module(fizzbuzz). -export([fb/3, fizzbuzz/1]). fb(_, 0, 0) -> io:put_chars("FizzBuzz\n"); fb(_, 0, _) -> io:put_chars("Fizz\n"); fb(_, _, 0) -> io:put_chars("Buzz\n"); fb(N, _, _) -> io:write(N), io:nl(). fizzbuzz(0) -> ok; fizzbuzz(N) -> fizzbuzz(N - 1), fb(N, N rem 3, N rem 5).

少しは関数型プログラミングっぽいかなぁ? これをC++のテンプレートで書いてみると以下のようになる。

#include <iostream> template<int N, int M3, int M5> struct FB { FB() { std::cout << N << std::…

Google App Engine: Googleはてブを作ってみた

Googleの検索結果にリンク付きのはてなブックマーク件数を表示できれば便利だと思い、Google App Engineを使ってウェブアプリケーションとして実装してみた。

最初、はてなブックマーク件数取得APIを使ってみたが、非常に遅い。これはXML-RPC APIによる実装だが、件数を取得するまでブラウザに表示できないのでかなり待たされる。酷いときにはGoogle App Engineの制限によりタイムアウトしてしまうこともあった。仕方がないので素直にhttp://b.hatena.ne.jp/entry/を使って画像表示を行うことにした。

Googleはてブ (画像表示版)
今時のブラウザは遅延読み込みによる画像表示のため待たされずにサクサク表示できる。

Googleはてブ (XML-RPC API版)
一方、API版は画面に表示されるまでかなり待たされる。

コードについては、あまり時間をかけずにザザッと書いたので結構いい加減かも。日本語処理で少しはまって適当に処置した。最後にソースコードを示しておく。

画像表示版:

class GoogleHatenaImage(webapp.RequestHandler): def __init__(self): self.google_url = "http://www.google.co.jp/" self.google_search_url = "http://www.google.co.jp/search" def get(self): uri_data = urlparse.urlsplit(self.request.uri) baseuri = uri_data[0] + "://" + "".join(uri_data[1:3]) url = self.request.get("content").encode("utf-8") query = self.request.query_string.replace("Shift_JIS", "UTF-…

はじめてのCUDAプログラミングで分子動力学計算

追記(2009/12/12): ここで示してるコードはかなりひどいので少し手直しして、CUDAで作成した分子動力学計算プログラムを書き直してみたという記事にまとめた。こちらも参照して欲しい。

最近、自分の周りではCUDAを使ったGPGPUが流行っているので、どんなものかこの週末にいじってみた。

一日目はNVIDIA GeForce 8800 GTSを搭載したWindows XPマシンにCUDAをインストールをしてリファレンスやサンプルプログラムをパラパラと読んでみた。二日目になんちゃって分子動力学(MD)計算プログラムを書いた。擬似原子を扱っており、全原子のvdW力とクーロン力のみを考慮して分子内結合については考慮しない、液滴中のMD計算だ。取り敢えず、半径20Åの液滴中に1229原子を入れて1000ステップ計算させてみた。C++で書いたプログラムでは4分30秒かかった計算がCUDAでは32秒で計算できた。約9倍ほどの速度が出ているようだ。

まあ、C++のコードも併せて一日で書いたので最適化や高速化については考慮していない。後でスレッドでの分割がやりやすいかもと思ってiとjをそのまま全部計算しているし。気が向いたらちゃんとしたプログラムを書いてみるかも。

CUDAアーキテクチャについてはまだまだ理解が足りない。効率のよいメモリの扱い方を覚えないとなぁ。あと、sharedメモリをうまく扱えてないっぽい。さすがに一日二日じゃキツイか。

初心者が一日で書いたコードなので参考になるかわからないが、以下にソースコードとサンプルの入力データを示しておく。入力データについては、上記で用いた1229原子ではブログ記事するには大きすぎるので154原子の小さなデータを用意した。また、記事の表示量が多くなりすぎるのでC++のソースは割愛させてもらった。Windows上でのコンパイルは下記の通り。

nvcc -lcutil32 -lkernel32 --host-compilation c++ -Xcompiler /EHsc,/W3,/nologo,/O2,/Zi,/MT simple_md_gpu.cu -o simple_md_gpu.exe

入力ファイルをmd.datとして、100ステップ計算させる場合は、以下のように実行する。

simple_md_gpu md.dat …

C++のテンプレートで素数を求める

ふと、C++のテンプレートで素数の計算をさせてみようと思い立ち、コードを書いてみた。書いた後でググってみたら同じことを考えた人がやっぱりいたけど気にしない。これは車輪の再発明ではなくてパズル遊びだから。コードの書き方も違うしね。因みに、このテンプレートによる素数計算ではコンパイル完了時に既に素数が求まっており、実行ではそれを表示するだけなので、ある意味、最速の素数計算プログラムと言えるかも。

短いコードだから読めばわかると思うけど、一応説明しておく。Primesに渡したテンプレートパラメータnを1ずつ減らしながら順番にPrimeに渡して、それが素数なら出力する。素数の判定では、Primeのテンプレートパラメータdの初期値を2とし、dを増やしながらnとの剰余を求め、途中で剰余0となれば特殊化されたPrime<n, d, 0, false>が呼ばれて何もしない。dについてはテンプレートの入れ子を減らしてコンパイル時間を短くするために、2および3で割り切れない値を次のdとしている。dの二乗がnより大きくなった時点(つまりnがnの平方根以下の整数で割りきれなかった場合)、特殊化されたPrime<n, d, r, true>が呼ばれて値を出力する。

以下に100までの素数を出力するコードを示す。main関数のPrimes<100>();の数値を変更すれば任意の数までの素数を出力できる。

#include <iostream> template<int n, int d = 2, int r = 1, bool is_prime = false> struct Prime { Prime() { Prime<n, (d > 2) ? ((d + 2) % 3 ? d + 2 : d + 4) : d + 1, n % d, (n < d * d)>(); } }; template<int n, int d> struct Prime<n, d, 0, false> {}; template<int n, int d, int r> struct Prime<n, d, r, true> { Prime() { std::…

C++: コンパイラは何を知りたがっている?

template<class T> void print_vector(const std::vector<T>& v) { for (std::vector<T>::const_iterator p = v.begin(); p != v.end(); ++p) std::cout << *p << std::endl; }

問題: 上に書いたコードを含むソースをコンパイルしたらエラーが出た。コンパイラにとって何かの情報が足りないようだ。どこが間違っているのだろうか?

答えは以下の通りで、「typenameが抜けている」。

template<class T> void print_vector(const std::vector<T>& v) { for (typename std::vector<T>::const_iterator p = v.begin(); p != v.end(); ++p) std::cout << *p << std::endl; }

コンパイラからはテンプレートパラメータTを含むstd::vector<T>::const_iteratorが型かどうか判断できないので、型であることを明示的に教える必要がある。

まあ、コンパイラによってはtypenameがなくても通っちゃったりするんだけどね。

Bloggerの記事が表示されない不具合

Blogger(blogspot)の記事(エントリ)が正常に表示されない不具合が確認されている。こちらでもその不具合を確認した。

ブログのタイトルやサイドバーは表示されるのだが、記事そのものがブランクとなり表示されない。表示されない記事はランダムで決まるようだ。Googleのディスカッションボードでもかなりの被害が報告されている

取り敢えずの対策として、新しい記事をドラフトで保存しキャッシュをクリアする方法がある。ただし、これは一時的な対策であり、しばらくするとまた表示されなくなったりする。

<script type='text/javascript'> google.friendconnect.container.renderUrlCanvasGadget({'id': 'gadget-canvas'}); </script>

表示されないページのソースを読むと上記のようなコードが吐き出されていることから、Google Friend Connect関連のエラーかと思い、ダッシュボードのプロフィールの設定で「読者になっているサイトを表示」のチェックをはずしたところ、今のところ不具合は出ていない。もっとも今後再発するかもしれないがそしたらそのとき考えよう。

C言語: ポインタと配列について

C言語の入門書を読み始めたばかりの初心者である学生が、先生に質問をしているようです。どんな内容かちょっと聞いてみましょう。

ポインタの使い方

学生: 先生、ポインタの宣言ってこれで合っていますよね。

int *p;

でもp[0] = 5;のように使うとエラーが出るんです。

先生: それは当たり前だ。まだメモリを確保していないだろう? メモリを確保しないと使えないぞ。

学生: でも配列の場合、int a[10];のように宣言したら使えましたよ。ポインタって全然ダメですね。

先生: ポインタと配列はまったく違うものだから、どちらがダメでどちらが良いと云うことはないよ。配列はその場でメモリを確保して使えるが(上記の場合はintを10個分)、プログラム内で決め打ちした数値になってしまう。つまり後から大きさの変更ができないんだ。

一方、ポインタは宣言しただけでは使えないが、後から自由にメモリを割り当ててその大きさを変えられるから、少ないメモリで済む場合は小さく、たくさんのメモリが必要な場合は大きくメモリを自由に確保することができる。

学生: へぇ。ところで、どうやってメモリを確保すればいいんですか?

先生: それはこのようにすればいい。

p = (int*)malloc(10 * sizeof(int));

これは、intのポインタにintの大きさで10個分のメモリを割り当てるという意味だ。確保したメモリが不要になったなら

free(p);

で開放する。この辺についてはその入門書にも載っているだろう。

学生: ふ~ん。なんだか難しそうですね。

先生: 慣れれば難しいことなどないよ。C言語ならmallocでメモリを割り当て、freeで開放と覚えていればいい。

学生: 分かりました。早速使ってみます。

ポインタと配列の違い

学生: ポインタを使ってみましたが、結局、中の数値を見たり変更したりする場合は、p[2]のように配列の形にしないといけないんですよね。なんだか混乱するなぁ。

先生: 別にp[2]ではなくても*(p+2)としても良いぞ。どちらもまったく同じ意味だ。配列型と同じように見えるからといって配列ではないからその点は気をつけることだな。因みに、*(p+2)は*(2+p)とも書けるので、2[p]とも書けることになり、実際にこれは文法上正しいのだ。

学生: えええ! そうだったんだ! 先生、これから…