良いもの。悪いもの。

恭賀新年

2012-01-01T06:23:00.001+09:00

今年は2012年です。

bool leap_year(int y) { return !(y%4)^!(y%100)^!(y%400); }

そして、leap_year(2012) が真となるので閏年です。平年と比べて一日増えるわけですが、その一日たりとも無駄にしない充実した一年にしたいと思います。

本年もどうぞ宜しくお願い申し上げます。

円周率を1万桁まで求める

2011-12-23T17:02:00.004+09:00

マチンの公式で円周率を1万桁まで求めるプログラムを、Python, Erlang, Haskell, C++で書いてみた。出力結果の最後の数桁はずれているかも。また、実行時間を測ったりもしているが、1万桁程度ならどのコードでも瞬時に求まる。

まずは素直にPythonで。実行時オプションで桁数指定、実行時間測定付き。オプションなしで1万桁まで求める。

pi.py

#!/usr/bin/env python import sys, time N = 10**10000 def arctan(m): global N c = N a = b = c / m m2 = m * m s = k = 1 while c: b /= m2 k += 2 c, s = b / k, -s a += c * s return a def main(args): global N if len(args) > 1: N = 10**int(args[1]) t1 = time.time() pi = str((arctan(5) * 4 - arctan(239)) * 4) t2 = time.time() print pi[0] + '.' + pi[1:] print "Time: %f" % (t2 - t1) if __name__ == "__main__": main(sys.argv)

実行:

$ ./pi.py

次にErlangで求めてみる。

pi.erl

-module(pi). -export([pi/0]). pi()->N=e(10,10000),(a(5,N)*4-a(239,N))*4. e(B,N)->e(B,N,1). e(_,0,R)->R; e(B,N,R)->e(B,N-1,R*B). a(X,N)->a(X,N div X,N div X,N,1,1). a(_,A,_,0,_,_)->A; a(M,A,B,_,S,K)->B_=B div(M*M),C=B_ div(K+2),S_=-S,A_=A+C*S_,a(M,A_,B_,C,S_,K+2).

実行:

$ erl 1> c(pi). 2> pi:pi().

そしてHaskellを使う。ソースコードは一行だ。

pi.hs

n=10^10^4;p=a 5 n*4-a 239 n;a m n=t m(n`div`m)(n`div`m)n 1 3;t _ a _ 0 _ _=a;t m a b c s k=t m(a-y*s)x y(-s)(k+2)where x=b`div`m^2;y=x`div`k

実行:

$ ghci Prelude> :l pi Prelude> p*4

最後にC++のコード。多倍長演算でちょっと長い。実行時間測定付き。

pi.cpp

#include <iostream> #include <iomanip> #include <algorithm> #include <cmath> #ifdef _MSC_VER #include <ctime> inline double get_time() { return static_cast<double>(std::clock()) / CLOCKS_PER_SEC; } #else #include <sys/time.h> inline double get_time() { timeval tv; gettimeofday(&tv, 0); return tv.tv_sec + 1e-6 * tv.tv_usec; } #endif typedef unsigned long long number; const int FIG = 8; const number BASE = 0xffffffffULL; const number NN = 100000000ULL; // C = 1.0 / (4 * log10(2)) / FIG; #define C (0.830482023722/FIG) #define M (X/FIG+2) #define N (static_cast<int>(X*C+2)) template<int X> class PI { private: number ans[N]; public: void add(number* a, number* b); void sub(number* a, number* b); void div(number* a, number d); number intdiv(number x, number y); void mul(number* a, number d); void atan(number* a, number m); number or_numbers(number* a); bool has_bit(number* a); void decimal(number* a, number* w); void print(); void calc(); }; // a <- arctan(1 / m) template<int X> void PI<X>::atan(number* a, number m) { number b[N] = { 1 }; number c[N] = { 1 }; div(b, m); std::copy(b, b + N, a); const number m2 = m * m; for (int i = 1; has_bit(c); i++) { div(b, m2); std::copy(b, b + N, c); div(c, i * 2 + 1); if (i & 1) sub(a, c); else add(a, c); } } // a <- a + b template<int X> void PI<X>::add(number* a, number* b) { for (int i = 0; i < N; i++) { number x = a[i] + b[i]; if (x & ~BASE) { a[i] = x & BASE; int j; for (j = i - 1; a[j] == BASE; j--) a[j] = 0; a[j]++; } else a[i] = x; } } // a <- a - b (a > b) template<int X> void PI<X>::sub(number* a, number* b) { for (int i = 0; i < N; i++) { if (a[i] < b[i]) { a[i] = (BASE + 1) + a[i] - b[i]; int j; for (j = i - 1; a[j] == 0; j--) a[j] = BASE; a[j]--; } else a[i] -= b[i]; } } // a <- a / d (d <= BASE) template<int X> void PI<X>::div(number* a, number d) { number res = 0; for (int i = 0; i < N; i++) { res <<= (FIG * 4); number x = a[i] + res; number q = x / d; a[i] = q; res = x - q * d; } } template<int X> number PI<X>::intdiv(number x, number y) { const number maxbit = ~((number)-1>>1); number a = 0; number b = 0; int cnt = sizeof(number) * 8; while (cnt--) { a <<= 1ULL; if (x & maxbit) a |= 1ULL; x <<= 1ULL; b <<= 1ULL; if (a >= y) { ++b; a -= y; } } return b; } // a <- a * d (d <= BASE) template<int X> void PI<X>::mul(number* a, number d) { number q = 0; for (int i = N - 1; i >= 0; i--) { number x = a[i] * d + q; a[i] = x & BASE; q = x >> (FIG * 4); } } // OR numbers template<int X> number PI<X>::or_numbers(number* a) { number ret = 0; for (int i = 0; i < N; i++) ret |= a[i]; return ret; } template<int X> bool PI<X>::has_bit(number* a) { for (int i = 0; i < N; i++) if (a[i]) return true; return false; } // hex to decimal number template<int X> void PI<X>::decimal(number* a, number* w) { number b[N]; std::copy(a, a + N, b); w[0] = b[0]; b[0] = 0; for (int i = 1; i < M; i++) { mul(b, NN); w[i] = b[0]; b[0] = 0; } } // print answer template<int X> void PI<X>::print() { number w[M]; decimal(ans, w); std::cout << std::setw(4) << std::right << w[0] << "."; for (int i = 1; i < M; i++) { std::cout << std::setw(FIG) << std::setfill('0') << w[i] << " "; if(i % 6 == 0) std::cout << std::endl << " "; } std::cout << std::endl; } // calculate PI // Machin's formula: 4 * arctan(1/5) - arctan(1/239) = PI / 4 template<int X> void PI<X>::calc() { number x[N]; atan(ans, 5); mul(ans, 4); atan(x, 239); sub(ans, x); mul(ans, 4); } int main() { std::ios_base::sync_with_stdio(false); PI<10000> pi; double start_time = get_time(); pi.calc(); double end_time = get_time(); pi.print(); std::cerr << "Time: " << end_time - start_time << std::endl; return 0; }

実行:

$ c++ pi.cpp -O3 -o pi $ ./pi

好きな・嫌いなコンピュータ言語のアンケート

2011-11-30T00:09:00.008+09:00

社内で好きなコンピュータ言語と嫌いなコンピュータ言語のアンケートを取ってみた。ことの発端は自分のツイートなのだが、思いがけず賛同を得ることができたので、実際にアンケートを社内で行うことにしたのだ。各自で社内Wikiを編集してもらってもよかったのだけど、プログラムを作る会社でもあるし、投票システムに興味もあったので、Google App Engine (GAE)で作ってみることにした。以前にGAEで掲示板などを作成していたので、それらを流用して時間をかけずにすぐに仕上げることができた。以下のリンクから実際に投票できる。

好きな・嫌いなコンピュータ言語のアンケート

表示されているコンピュータ言語一覧から、最も好きな言語と最も嫌いな言語をそれぞれ一つずつ、それ以外にも好きな言語や嫌いな言語があれば、それらも選択(複数可)する。投票したい言語が一覧にない場合は「言語の追加」で自由に追加できるようになっている。言語を選択して投票ボタンを押すと、投票数とそのグラフが更新される。表示されるグラフには、「最も好きな・最も嫌いな言語」と「好きな・嫌いな言語」の2つがあり、青のグラフが「好きな言語」、赤のグラフが「嫌いな言語」を表している。「好きな・嫌いな言語」のグラフについては、「最も好きな・最も嫌いな言語」と「好きな・嫌いな言語」を足し合わせた票数となっている。

また、コメントも投稿できるようになっていて、自分の好きな言語を啓蒙するのも良し、嫌いな言語について文句を言うのもアリだ。自由に書き込める。

現時点での社内での票は以下のグラフに示す通りで、幅広く票が入っているように思う。傾向としては、C, C++, C#, ASM, Python, Rubyあたりが人気で、Visual Basic, Java, Perlが不人気みたいだ。

今回作成したコードの簡単な説明を書いておく。上述の「好きな・嫌いなコンピュータ言語」だけでなく、初期変数を設定することで、「好きな・嫌いな動物」「好きな・嫌いな食べ物」などのように、簡単に任意のアンケートを作成できるようになっている。グラフについてはGoogle Chart APIを利用しているが、1,000ピクセルを超えることができないので、表示数を1,000ピクセル以内に抑える処理を入れている。また、頻繁にデータベースにアクセスしないようにmemcacheも利用している。詳細についてはコードを読んで欲しい。

以下に今回作成したGAEのコードを示しておく。

main.py

#!/usr/bin/env python # -*- coding: utf-8 -*- """main.py Copyright (C) 2011 nox""" import os, cgi, re, math, datetime import urllib, Cookie import wsgiref.handlers from google.appengine.api import memcache from google.appengine.ext import webapp from google.appengine.ext import db from google.appengine.ext.webapp import template # 許可する投票タイトル. TITLES = { "test": u"投票テスト", "lang": u"好きな・嫌いなコンピュータ言語のアンケート" } # 表示メッセージ. MESSAGES = { "test": u"投票をお願いします。", "lang": u"最も好きな言語と最も嫌いな言語をそれぞれ1つ、他に好きな言語や嫌いな言語があればそれも選択(複数可)して投票をお願いします。" } # 投票する属性. (タイトル / love / like / hate / dislike) PROPS = { "test": (u"テスト", u"最高", u"良い", u"最低", u"悪い"), "lang": (u"言語", u"最も好き", u"好き", u"最も嫌い", u"嫌い") } # チャートのタイトル. (love and hate / like and dislike [including love and hate]) CHARTS = { "test": (u"最高・最低のテスト", u"良い・悪いテスト"), "lang": (u"最も好きな・最も嫌いな言語", u"好きな・嫌いな言語") } # 最大表示件数 TARGET_LIMIT = 300 COMMENT_LIMIT = 100 class MainPage(webapp.RequestHandler): def get(self): self.response.out.write(u""" <html> <head> <title>Opinion Poll</title> </head> <body> <div><a href="vote">投票システム</a></div> </body> </html>""") # 投票データ. class VoteData(db.Model): id = db.StringProperty(multiline=False) content = db.StringProperty(multiline=False) love = db.IntegerProperty() like = db.IntegerProperty() hate = db.IntegerProperty() dislike = db.IntegerProperty() # コメントデータ. class CommentData(db.Model): id = db.StringProperty(multiline=False) username = db.StringProperty(multiline=False) content = db.TextProperty() date = db.DateTimeProperty(auto_now_add=True) # 投票システム・表示. class Vote(webapp.RequestHandler): def get(self): global TITLES, TARGET_LIMIT id = self.request.get("id") if id not in TITLES.keys(): return # データベースまたはMemcacheからデータの読み込み. cache_votes_key = "votes_%s" % id try: votes = memcache.get(cache_votes_key) except: try: memcache.delete(cache_votes_key) except: pass votes = None if votes is None: votes = VoteData.all().order("content").filter("id =", id).fetch(TARGET_LIMIT) try: memcache.add(cache_votes_key, votes) except: pass cache_comments_key = "comments_%s" % id try: comments = memcache.get(cache_comments_key) except: try: memcache.delete(cache_comments_key) except: pass comments = None if comments is None: comments = CommentData.all().order("-date").filter("id =", id).fetch(COMMENT_LIMIT) try: memcache.add(cache_comments_key, comments) except: pass # チャート表示 (1,000ピクセル以下にデータ数を収める). target2, target4 = [], [] target2_max, target4_max = 0, 0 for v in votes: v.love = int(v.love) if v.love else 0 v.hate = int(v.hate) if v.hate else 0 v.like = int(v.like) if v.like else 0 v.dislike = int(v.dislike) if v.dislike else 0 if v.love or v.hate or v.like or v.dislike: target4.append((v.content, v.love + v.like, v.hate + v.dislike)) target4_max = max(target4_max, v.love + v.like, v.hate + v.dislike) if v.love or v.hate: target2.append((v.content, v.love, v.hate)) target2_max = max(target2_max, v.love, v.hate) target2_max = (target2_max - 1) / 10 if target2_max > 0 else 0 target2_max = (target2_max + 1) * 10 target4_max = (target4_max - 1) / 10 if target4_max > 0 else 0 target4_max = (target4_max + 1) * 10 n = 0 while True: target2 = filter(lambda t: max(t[1:]) > n, target2) if len(target2) <= 16: break n += 1 if target2: text = "" if n > 0: text = u" (%d票以上)" % (n + 1) fig = 10**(int(math.log10(target2_max))) if target2_max / fig < 5: fig /= 2 chart_scale = "|".join([str(i) for i in range(0, target2_max + 1, fig)]) chart_target2_url = u"http://chart.apis.google.com/chart?chs=%dx200&chd=t:%s|%s&chds=0,%d&cht=bvg&chco=4d89f9,f9894d&chxt=y,x&chxl=0:|%s|1:|%s&chtt=%s%s" % (len(target2) * 60 + 30, ",".join([str(t[1]) for t in target2]), ",".join([str(t[2]) for t in target2]), target2_max, chart_scale, "|".join([urllib.quote(t[0].encode('utf-8')) for t in target2]), CHARTS[id][0], text) else: chart_target2_url = "" n = 0 while True: target4 = filter(lambda t: max(t[1:]) > n, target4) if len(target4) <= 16: break n += 1 if target4: text = "" if n > 0: text = u" (%d票以上)" % (n + 1) fig = 10**(int(math.log10(target4_max))) if target4_max / fig < 5: fig /= 2 chart_scale = "|".join([str(i) for i in range(0, target4_max + 1, fig)]) chart_target4_url = u"http://chart.apis.google.com/chart?chs=%dx200&chd=t:%s|%s&chds=0,%d&cht=bvg&chco=4d89f9,f9894d&chxt=y,x&chxl=0:|%s|1:|%s&chtt=%s%s" % (len(target4) * 60 + 30, ",".join([str(t[1]) for t in target4]), ",".join([str(t[2]) for t in target4]), target4_max, chart_scale, "|".join([urllib.quote(t[0].encode('utf-8')) for t in target4]), CHARTS[id][1], text) else: chart_target4_url = "" # 挨拶. H = (datetime.datetime.utcnow() + datetime.timedelta(hours=9)).hour if H >= 5 and H < 11: greeting = u"おはようございます。" elif H >= 11 and H < 17: greeting = u"こんにちは。" elif H >= 17 or H < 5: greeting = u"こんばんは。" else: greeting = u"こんにちは。" greeting += MESSAGES[id] # ウェブ上で表示させるデータ. template_values = { "id": id, "title": TITLES[id], "target": PROPS[id][0], "love": PROPS[id][1], "like": PROPS[id][2], "hate": PROPS[id][3], "dislike": PROPS[id][4], "votes": votes, "comments": comments, "chart_target2_url": chart_target2_url, "chart_target4_url": chart_target4_url, "greeting": greeting, } path = os.path.join(os.path.dirname(__file__), "vote.html") self.response.out.write(template.render(path, template_values)) # 投票ターゲットの追加. class AddVote(webapp.RequestHandler): def post(self): vote = VoteData() vote.id = self.request.get("id") try: try: memcache.delete("votes_%s" % vote.id) except: pass except: pass if not self.request.get("content").strip(): self.redirect("/vote?id=%s" % vote.id) return content = cgi.escape(self.request.get("content").strip()[:100]) v = VoteData.all().filter("id =", vote.id).filter("content =", content).get() if not v: vote.content = content vote.put() self.redirect("/vote?id=%s" % vote.id) # 投票. class PostVote(webapp.RequestHandler): def post(self): vote = VoteData() vote.id = self.request.get("id") love = self.request.get_all("love") like = self.request.get_all("like") hate = self.request.get_all("hate") dislike = self.request.get_all("dislike") try: try: memcache.delete("votes_%s" % vote.id) except: pass except: pass if not (love or like or hate or dislike): self.redirect("/vote?id=%s" % vote.id) return for d in love: v = VoteData.all().filter("id =", vote.id).filter("content =", d).get() if not v.love: v.love = 1 else: v.love = int(v.love) + 1 v.put() for d in like: v = VoteData.all().filter("id =", vote.id).filter("content =", d).get() if not v.like: v.like = 1 else: v.like = int(v.like) + 1 v.put() for d in hate: v = VoteData.all().filter("id =", vote.id).filter("content =", d).get() if not v.hate: v.hate = 1 else: v.hate = int(v.hate) + 1 v.put() for d in dislike: v = VoteData.all().filter("id =", vote.id).filter("content =", d).get() if not v.dislike: v.dislike = 1 else: v.dislike = int(v.dislike) + 1 v.put() self.redirect("/vote?id=%s" % vote.id) # コメントの投稿. class PostComment(webapp.RequestHandler): def insert_whitespace(self, matchobj): return re.sub("(?<!<br) ", " ", matchobj.group(0).replace("\t", " ")) def post(self): global TARGET_LIMIT comment = CommentData() comment.id = self.request.get("id") try: try: memcache.delete("comments_%s" % comment.id) except: pass except: pass if not self.request.get("content").strip(): self.redirect("/vote?id=%s" % comment.id) return if self.request.get("username").strip(): comment.username = cgi.escape(self.request.get("username").strip()[:255]) else: comment.username = "Anonymous" comment.content = cgi.escape(self.request.get("content").strip()[:2000]) comment.content = re.sub("\r\n|\r|\n", "<br />", comment.content) comment.content = re.sub("\[link\](.*?)\[/link\]", "<a href=\"\g<1>\">\g<1></a>", comment.content) comment.content = re.sub("\[code\](.*?)\[/code\]", self.insert_whitespace, comment.content) comment.content = re.sub("\[code\](.*?)\[/code\]", "<span style=\"font-family:courier new,monospace;font-size:85%;white-space:pre;color:#0000ff;\">\g<1></span>", comment.content) comment.date = comment.date + datetime.timedelta(hours=9) comment.put() self.redirect("/vote?id=%s" % comment.id) def main(): application = webapp.WSGIApplication([("/", MainPage), ("/vote", Vote), ("/vote/add", AddVote), ("/vote/post", PostVote), ("/vote/comment", PostComment), ], debug=False) wsgiref.handlers.CGIHandler().run(application) if __name__ == "__main__": main()

vote.html

<?xml version="1.0" encoding="UTF-8"?> <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.1//EN" "http://www.w3.org/TR/xhtml11/DTD/xhtml11.dtd"> <html xmlns="http://www.w3.org/1999/xhtml" xml:lang="ja"> <head> <meta http-equiv="Content-Type" content="text/html; charset=UTF-8"> <link type="text/css" rel="stylesheet" href="/stylesheets/main.css" /> <title>{{ title }}</title> </head> <body> <script type="text/javascript"> function resize_textarea(ev){ var textarea = ev.target || ev.srcElement; var value = textarea.value; var lines = 1; for (var i = 0, l = value.length; i < l; i++) if (value.charAt(i) == '\n') lines++; if (lines > 5) { if (lines > 20) textarea.setAttribute("rows", 20); else textarea.setAttribute("rows", lines); } else textarea.setAttribute("rows", 5); } </script> <div style="font-weight: bold; font-size: large; padding-bottom: 20px;">{{ title }}</div> <div> <p>{{ greeting }}</p> </div> <form action="/vote/add" method="post"> <input type="text" name="content" size="20" maxlength="100"></input> <input type="submit" value="{{ target }}の追加" /> <input type="hidden" name="id" value="{{ id }}"> </form> <form action="/vote/post" method="post"> <div> <table border="0" width="400"> <th>{{ target }}</th><th>{{ love }}</th><th>{{ like }}</th><th>{{ hate }}</th><th>{{ dislike }}</th> {% for vote in votes %} <tr> <td><a href="http://ja.wikipedia.org/wiki/{{ vote.content }}">{{ vote.content }}</a></td> <td align="center"><input type="radio" name="love" value="{{ vote.content }}" /> {% if vote.love %} {{ vote.love }} {% else %} 0 {% endif %}</td> <td align="center"><input type="checkbox" name="like" value="{{ vote.content }}" /> {% if vote.like %} {{ vote.like }} {% else %} 0 {% endif %}</td> <td align="center"><input type="radio" name="hate" value="{{ vote.content }}" /> {% if vote.hate %} {{ vote.hate }} {% else %} 0 {% endif %}</td> <td align="center"><input type="checkbox" name="dislike" value="{{ vote.content }}" /> {% if vote.dislike %} {{ vote.dislike }} {% else %} 0 {% endif %}</td> </tr> {% endfor %} <tr align=center> <td colspan=5><input type="submit" value="投票" style="width: 100px; height: 25px" /></td> </tr> </table> <input type="hidden" name="id" value="{{ id }}"> </div> </form><br /> <div> {% if chart_target2_url %} <p><img src="{{ chart_target2_url }}" /></p> {% endif %} {% if chart_target4_url %} <p><img src="{{ chart_target4_url }}" /></p> {% endif %} </div> コメント記入: <span style="font-size:70%;color:#666666;">リンク: [link]～[/link], ソースコード: [code]～[/code], 1,000文字まで</span><br /> <form action="/vote/comment" method="post"> <div><textarea name="content" rows="5" cols="60" onkeyup="resize_textarea(event)"></textarea></div> 名前: <input type="text" name="username" size="31" maxlength="255" value="{{ username }}"></input> <input type="submit" value="コメント" /> <span style="font-size:70%;color:#666666;">無記名で匿名投稿</span> <input type="hidden" name="id" value="{{ id }}"> </form> <div> {% for comment in comments %} {{ comment.username }} [{{ comment.date.year }}年{{ comment.date.month }}月{{ comment.date.day }}日{{ comment.date.hour }}時{{ comment.date.minute }}分{{ comment.date.second }}秒]: <blockquote>{{ comment.content }}</blockquote> {% endfor %} </div>  <div><img src="http://code.google.com/appengine/images/appengine-silver-120x30.gif" alt="Powered by Google App Engine" /> <span style="font-size:70%;color:#666666;"><a href="http://handasse.blogspot.com/">ソースコードおよびその解説</a></span><br /><span style="font-size:70%;color:#666666;">Copyright © 2011 <a href="http://handasse.blogspot.com/">nox</a>. All rights reserved.</span></div> </body> </html>

コンピュータにラストワンを解かせてみた

2011-10-19T00:07:00.006+09:00

先日、地元のまつりがあった。そこの会場となっている区民館では子供用ボーリングやプラ板遊びなどの催しが開かれていたのだが、その中の一つに「ひとりぼっち」というゲームを行なっているのを見つけたので、一緒にいた小4の自分の娘に「このゲーム面白そうだね」と言ったところ、「ラストワンでしょ」と返され、よく知っているゲームとのことだった。遊び方は次の通り。全部で33のマスがあり、真ん中以外の32個のマスにコマを置く。コマは縦・横方向に隣のコマを一つ飛び越えて進むことができる。飛び越えられたコマは取り除かれる。これを繰り返して、最後のコマを真ん中のマスに置けばクリアとなる。32コマを使うステージ以外にもT字型やピラミッド型にコマを配置するなど、さまざまなバリエーションがある。

ネットで調べたところ、1985年にバンダイから同名の電子ゲームが出ていたようだ。リンク先では動画もあるのでそれを見てもらえば遊び方は一目瞭然だろう。普通に解いても面白そうだが、コンピュータを使って解かせたくなったので、早速プログラムを作ってみた。

余談だが、子供のころ、コンピュータは何でも解いてくれる魔法の箱だと思っていた。円周率を何桁まで解いたと聞いて、ワクワクしたものだ。ラストワンのようなゲームをコンピュータに解かせたいという気持ちは、子供のころのコンピュータに対する憧れから来るのかもしれない。

閑話休題。ラストワンは33マスあり、コマが「ある」「ない」の2状態のみを持つので、33ビットを使って盤面の状態を表すことができる。そして、ある状態から取り得る次の状態をすべて求めて、それを優先順位付きキューに入れて探索した。キューが空になるか、ゴールの状態が見つかるまで探索を行う。優先順位付きキューにしたのは探索を短縮するためにヒューリスティックな関数でスコアを決めようと思ったからなんだけど、32コマあるステージも含め、どれも一瞬で解けてしまうので、どうやら高度なヒューリスティック関数を用意しなくても問題なかったらしい。

上図のように初期配置としてT字型にコマを置く場合、以下に示すような入力データを用意して、これをプログラムに渡す。o (オー)でコマのあるマスを表し、. (ドット)で空のマスを表している。

lastone.dat

... ... ....... ..ooo.. ...o... .o. ...

入力データのファイル名が lastone.dat であれば、以下のように実行すればよい。

% ./lastone lastone.dat

実行結果は以下のようになる。

... ... ....... ..ooo.. ...o... .o. ... ... ... ....... .o..o.. ...o... .o. ... ... ... ....... .o.oo.. ....... ... ... ... ... ....... .oo.... ....... ... ... ... ... ....... ...o... ....... ... ...

最後に作成したコードを示す。

lastone.cpp

// Last One solver by nox, 14 Oct. 2011 #include <iostream> #include <fstream> #include <string> #include <vector> #include <queue> #include <algorithm> #include <utility> using namespace std; typedef unsigned long long state_t; typedef int score_t; const int N = 33; // number of cells class LastOne { private: vector<vector<pair<int, int> > > D; // table of directions state_t start, goal; vector<state_t> ans; // solution public: LastOne(const string datafile=""); ~LastOne() { } void read(const string datafile); int movable(state_t state); void next(state_t state, vector<state_t>& neighbors); bool search(); void show(state_t state); void answer(); }; // initialize and make table LastOne::LastOne(const string datafile) { if (!datafile.empty()) read(datafile); vector<pair<int, int> > v; v.push_back(make_pair(1, 2)); v.push_back(make_pair(3, 8)); D.push_back(v); v.clear(); v.push_back(make_pair(4, 9)); D.push_back(v); v.clear(); v.push_back(make_pair(1, 0)); v.push_back(make_pair(5, 10)); D.push_back(v); v.clear(); v.push_back(make_pair(4, 5)); v.push_back(make_pair(8, 15)); D.push_back(v); v.clear(); v.push_back(make_pair(9, 16)); D.push_back(v); v.clear(); v.push_back(make_pair(4, 3)); v.push_back(make_pair(10, 17)); D.push_back(v); v.clear(); v.push_back(make_pair(7, 8)); v.push_back(make_pair(13, 20)); D.push_back(v); v.clear(); v.push_back(make_pair(8, 9)); v.push_back(make_pair(14, 21)); D.push_back(v); v.clear(); v.push_back(make_pair(3, 0)); v.push_back(make_pair(7, 6)); v.push_back(make_pair(9, 10)); v.push_back(make_pair(15, 22)); D.push_back(v); v.clear(); v.push_back(make_pair(4, 1)); v.push_back(make_pair(8, 7)); v.push_back(make_pair(10, 11)); v.push_back(make_pair(16, 23)); D.push_back(v); v.clear(); v.push_back(make_pair(5, 2)); v.push_back(make_pair(9, 8)); v.push_back(make_pair(11, 12)); v.push_back(make_pair(17, 24)); D.push_back(v); v.clear(); v.push_back(make_pair(10, 9)); v.push_back(make_pair(18, 25)); D.push_back(v); v.clear(); v.push_back(make_pair(11, 10)); v.push_back(make_pair(19, 26)); D.push_back(v); v.clear(); v.push_back(make_pair(14, 15)); D.push_back(v); v.clear(); v.push_back(make_pair(15, 16)); D.push_back(v); v.clear(); v.push_back(make_pair(8, 3)); v.push_back(make_pair(14, 13)); v.push_back(make_pair(16, 17)); v.push_back(make_pair(22, 27)); D.push_back(v); v.clear(); v.push_back(make_pair(9, 4)); v.push_back(make_pair(15, 14)); v.push_back(make_pair(17, 18)); v.push_back(make_pair(23, 28)); D.push_back(v); v.clear(); v.push_back(make_pair(10, 5)); v.push_back(make_pair(16, 15)); v.push_back(make_pair(18, 19)); v.push_back(make_pair(24, 29)); D.push_back(v); v.clear(); v.push_back(make_pair(17, 16)); D.push_back(v); v.clear(); v.push_back(make_pair(18, 17)); D.push_back(v); v.clear(); v.push_back(make_pair(13, 6)); v.push_back(make_pair(21, 22)); D.push_back(v); v.clear(); v.push_back(make_pair(14, 7)); v.push_back(make_pair(22, 23)); D.push_back(v); v.clear(); v.push_back(make_pair(15, 8)); v.push_back(make_pair(21, 20)); v.push_back(make_pair(23, 24)); v.push_back(make_pair(27, 30)); D.push_back(v); v.clear(); v.push_back(make_pair(16, 9)); v.push_back(make_pair(22, 21)); v.push_back(make_pair(24, 25)); v.push_back(make_pair(28, 31)); D.push_back(v); v.clear(); v.push_back(make_pair(17, 10)); v.push_back(make_pair(23, 22)); v.push_back(make_pair(25, 26)); v.push_back(make_pair(29, 32)); D.push_back(v); v.clear(); v.push_back(make_pair(18, 11)); v.push_back(make_pair(24, 23)); D.push_back(v); v.clear(); v.push_back(make_pair(19, 12)); v.push_back(make_pair(25, 24)); D.push_back(v); v.clear(); v.push_back(make_pair(22, 15)); v.push_back(make_pair(28, 29)); D.push_back(v); v.clear(); v.push_back(make_pair(23, 16)); D.push_back(v); v.clear(); v.push_back(make_pair(24, 17)); v.push_back(make_pair(28, 27)); D.push_back(v); v.clear(); v.push_back(make_pair(27, 22)); v.push_back(make_pair(31, 32)); D.push_back(v); v.clear(); v.push_back(make_pair(28, 23)); D.push_back(v); v.clear(); v.push_back(make_pair(29, 24)); v.push_back(make_pair(31, 20)); D.push_back(v); } // read LastOne data void LastOne::read(const string datafile) { fstream fs(datafile.c_str(), ios_base::in); string line; goal = 0x10000; start = 0ULL; while (getline(fs, line)) { for (string::iterator p = line.begin(); p != line.end(); ++p) { if (*p == 'o') { start <<= 1; start |= 1ULL; } else if (*p == '.') start <<= 1; } } fs.close(); } // number of movable pieces int LastOne::movable(state_t state) { int s = 0; for (int i = 0; i < N; i++) if ((state >> i) & 1) for (vector<pair<int, int> >::iterator p = D[i].begin(); p != D[i].end(); ++p) s += ((state >> p->first) & 1) & !((state >> p->second) & 1); return s; } // next states void LastOne::next(state_t state, vector<state_t>& neighbors) { neighbors.clear(); for (int i = 0; i < N; i++) if ((state >> i) & 1) for (vector<pair<int, int> >::iterator p = D[i].begin(); p != D[i].end(); ++p) if (((state >> p->first) & 1) & !((state >> p->second) & 1)) neighbors.push_back(state ^ (1ULL << p->first) ^ (1ULL << p->second) ^ (1ULL << i)); } // search solution bool LastOne::search() { vector<state_t> checked(1, start); priority_queue<pair<score_t, vector<state_t> > > queue; queue.push(make_pair(1, checked)); vector<state_t> neighbors; while (!queue.empty()) { pair<score_t, vector<state_t> > q(queue.top()); queue.pop(); state_t last = q.second.back(); if (last == goal) { ans = q.second; return true; } next(last, neighbors); for (vector<state_t>::iterator p = neighbors.begin(); p != neighbors.end(); ++p) { if (binary_search(checked.begin(), checked.end(), *p)) continue; if (movable(*p) == 0 && *p != goal) continue; checked.insert(upper_bound(checked.begin(), checked.end(), *p), *p); vector<state_t> path(q.second); path.push_back(*p); queue.push(make_pair(static_cast<score_t>(path.size()), path)); } } return false; } // show state void LastOne::show(state_t state) { string line; while (state) { if (state & 1ULL) line.push_back('o'); else line.push_back('.'); state >>= 1; } int n = N - line.size(); for (int i = 0; i < n; i++) line.push_back('.'); reverse(line.begin(), line.end()); cout << " " << line.substr(0, 3) << endl; cout << " " << line.substr(3, 3) << endl; cout << line.substr(6, 7) << endl; cout << line.substr(13, 7) << endl; cout << line.substr(20, 7) << endl; cout << " " << line.substr(27, 3) << endl; cout << " " << line.substr(30, 3) << endl; } // show solution void LastOne::answer() { for (vector<state_t>::iterator p = ans.begin(); p != ans.end(); ++p) { show(*p); cout << endl; } } int main(int argc, char* argv[]) { if (argc < 2) { cerr << "Usage: " << argv[0] << " datafile" << endl; exit(1); } LastOne lastone(argv[1]); if (lastone.search()) lastone.answer(); else cout << "No solution." << endl; return 0; }

オフィスビル内の最短経路

2011-10-14T01:03:00.006+09:00

現在のオフィスでは、エントランスからどの通路を通るのが最も近いのか、未だに話題になることがある。エントランスからオフィスにつながるエレベータまでの道が二通りあり、どちらも似たような距離なので同じオフィスに行く人達なのにそこで別々になってしまうこともしばしば。左の図が問題のフロアなんだけど、エントランスから青丸で示したエレベータまで行く必要がある。だったらコンピュータに解かせてしまえばいいじゃない、ということでプログラムを作って最短経路と正確な距離を調べてみた。定規で測ったほうが早いという意見は聞こえません。

以前、Python: 画像で与えられた迷路に対し2点間の最短経路を求めるというブログ記事で、画像から直接最短距離を求めるプログラムを書いたことがあるので、まずはそれを使って調べてみた。図面の邪魔な文字だけ消して、あとはスタート地点とゴール地点の座標を引数で指定するだけだから簡単なんだけど、これだと問題があることに気がついた。というのはCCL (connected component labeling; 連結成分ラベリング)で移動できる領域を調べて、それをA*で解いているのだけど、隣接するノード(ピクセル)を上下左右斜めの8方向のみで調べているから正しい距離を出すことができないのだ。実際に作成した図は以下のようにギザギザになってしまい最短ルートを通らない。なので通り道の分岐や方向が変化する箇所をノードにしてそれをA*で求めることにした。

全部で10個のノード(画像のピクセル座標で指定)を作って調べたところ、以下のような結果になった。左側を通る通路の距離が324.53、右側を通る通路の距離が322.51となり僅かに右側の通路のほうが近かった。ただし、右側の方は途中でフロア案内と少し重なるし、6つあるエレベータのどれを使うかによっても結果が変わってしまうぐらいなので、実質的には同じ距離といってしまっても差し支えないと思う。

結局、それぞれの距離にはほとんど差がないので、結論としては「好きな方を使え」ということになるだろう。自分は広い通路の方が好みなので右側の通路を利用している。最後にソースコードとその使い方を示しておく。

nodes.datに、一行を"ピクセルX座標ピクセルY座標隣接ノード番号リスト"としてノード数の分だけ記述する。ノード番号は0から始まり、先頭行と最終行のノードはそれぞれスタート地点、ゴール地点を表している。また、フロアの図面画像をinput.pngとして渡すと、最短距離のルートが書きこまれた画像をoutput.pngとして出力する。

% ./route_solver.py nodes.dat input.png output.png

nodes.dat

27 273 1 3 6 21 128 0 2 125 23 1 9 117 221 0 4 5 6 141 178 3 7 167 178 3 7 195 178 0 3 7 192 110 4 5 6 8 193 91 7 9 151 41 2 8

route_solver.py

#!/usr/bin/env python # -*- coding: utf-8 -*- import sys, os, math, heapq, Image, ImageDraw class Node: def __init__(self): self.pos = (0, 0) self.neighbors = [] self.dist = float("inf") self.path = [] # A* Search Algorithm class AStar: def __init__(self, start, goal): self.start, self.goal = start, goal self.start.dist = 0.0 self.start.path = [self.start] def distance(self, node1, node2): return math.sqrt((node1.pos[0] - node2.pos[0])**2 + (node1.pos[1] - node2.pos[1])**2) def heuristic(self, node): return self.distance(node, self.goal) def search(self): queue = [] heapq.heappush(queue, (self.heuristic(self.start), self.start)) while queue: score, last = heapq.heappop(queue) if last == self.goal: return last.path, last.dist for nb in last.neighbors: newdist = last.dist + self.distance(last, nb) if nb.dist < newdist: continue nb.dist = newdist nb.path = last.path + [nb] heapq.heappush(queue, (nb.dist + self.heuristic(nb), nb)) return [], 0.0 def draw_path(in_image, out_image, path): im = Image.open(in_image) im = im.convert("RGB") draw = ImageDraw.Draw(im) draw.line([(int(p.pos[0]), int(p.pos[1])) for p in path], fill=255, width=2) im.save(out_image) def main(args): if len(args) < 4: print >>sys.stderr, "Usage: %s datafile in_image out_image" % os.path.basename(args[0]) sys.exit(1) datafile, in_image, out_image = args[1:4]; print "Reading nodes data..." data = [map(int, l.strip().split()) for l in file(datafile).readlines()] nodes = [Node() for i in range(len(data))] for i, node in enumerate(nodes): node.pos = tuple(data[i][:2]) for j in data[i][2:]: node.neighbors.append(nodes[j]) print " Number of nodes: %d" % len(nodes) print "A* searching phase..." start, goal = nodes[0], nodes[-1] print " Start: (%d, %d), Goal: (%d, %d)" % (start.pos + goal.pos) astar = AStar(start, goal) path, dist = astar.search() if path: print " Found route:" for p in path: print " (%d, %d)" % p.pos print " Distance: %f" % dist else: print " No route." print "Drawing path on the imagefile..." draw_path(in_image, out_image, path) if __name__ == "__main__": main(sys.argv)

追記 (2011/10/17): ソースコードが間違っていたので修正。今回の結果には影響なし。

GoogleのURL短縮サービスgoo.glのAPIをPythonで利用する

2011-09-27T04:06:00.002+09:00

しばらく前からgoo.glのAPI (Google URL Shortener API)が使えるようになっていたことは知っていたけど、実際に使ったことなかったので試しに使ってみた。import文を含めなければ3行で短縮URLの作成・復元の自動判別を行うことができた。条件演算子などを使えば1行にまとめられる。簡単。

ただし、正規表現は適当だし、エラー処理はしてないので、ちゃんと使う場合はその辺の処理を行う必要あり。あと、本格的に使うのであればAPIキーを取得すべき。また、Google APIs Client Library for Pythonを使う方法もある。

http://handasse.blogspot.com/ を短縮URLに変換:

% googl.py http://handasse.blogspot.com/ http://goo.gl/RiIiD

http://goo.gl/RiIiD を元のURLに戻す:

% googl.py http://goo.gl/RiIiD http://handasse.blogspot.com/

googl.py

import sys,re from urllib2 import urlopen as U, Request as R from json import loads as J API,URL="https://www.googleapis.com/urlshortener/v1/url",sys.argv[1] if re.match('http://goo\.gl/.+',URL):print J(U(API+'?shortUrl=%s'%URL).read())['longUrl'] else:print J(U(R(API,'{"longUrl":"%s"}'%URL,{'Content-Type':'application/json'})).read())['id']

暇潰しで書いたプログラム

2011-08-08T00:48:00.003+09:00

ちょっと出先で手持ち無沙汰になったとき、なにかコードが書きたくなることってあると思う。その時に書くプログラムは何でもよくて、言語も選ばない。でも、駅で電車を待っている間とか、注文したメニューが来るまでとか、ノートPCを引っ張り出してまでやりたくはない。そんなとき、Android端末を片手にSL4Aでコードを書くっていうのは丁度よい。

というわけで、ちょっと外出したときの暇な時間にSL4AのPythonで書いたコードが以下のコード。本当にくだらないプログラムなわけだけど、暇潰しにはなった。何をするプログラムか興味のある方は読み解いて欲しい。暇潰しぐらいにしかならないけど。まあ、勘のよい人ならファイル名だけでわかってしまうかも。

Android端末を持っている方なら、SL4Aのメニューを開いてAddを選択し、Scan Barcodeで冒頭のQRコードを読み込むことでソースコードを取得できる。SL4Aで書いたプログラムだけど、Android端末以外でもPythonの動作する環境なら大抵は実行できると思う。

Zm9yIGkgaW4gcmFuZ2UoMSwxMDEpOnByaW50J0ZpenonKigxLWklMykrJ0J1enonKigxLWklNSlvciBp.py

exec(r"""%s'''gzga*%%%%,hmkl*ocr*nco`fc"a8ajp*mpf*a+\\0+.p%%%s'kormpv"mq.`cqg469gzga*`cqg46,fgamfgqvpkle*mq,rcvj,`cqglcog*]]dkng]]+Y8/1_++')))%%+++''')))"""%(lambda _:(_,_))("exec(''.join(map(lambda _:chr(ord(_)^2),"))

Scalaのアクターモデルでマンデルブロ集合を並列計算

2011-07-11T03:24:00.012+09:00

最近、本格的にScalaを使用するつもりで環境を整えた。ビルドツールとしてSimple Build Tool (sbt)を利用し、エディタはensimeを入れたEmacsにしている。利用するに当たって.emacsに必要な記述を加えておくこと。初めてのプロジェクトの場合、適当に作成したディレクトリ内でsbtを起動してプロジェクトの雛形を作った後、Emacsを立ち上げて M-x ensime-config-gen で下準備をする。ここまでは初回のみの作業となる。その後は M-x ensime を実行して、src/main/scala/内でコードを書くだけ。これで、コーディング中にタブで補完してくれるし、文法などが間違っている場合に赤でハイライトもしてくれる。コンパイルや実行などは、C-c C-v s とすればsbtがEmacs上で立ち上がるので compile や run するだけ。簡単。

Scalaと言えばアクターでしょ、やっぱり。ということで今回はアクターモデルを使用したコードを書いてみた。自分はScalaをいじるよりも前にErlangをいじっていたので余計にそう考えてしまうのかもしれない。それでもマルチコアやらメニーコアが溢れているこの時代、並行処理の重要性は誰もが認識しているはず。

書いたコードはマンデルブロ集合の計算だ。毎回飽きもせずにまたそれかと思うかもしれないが、並列処理させるのが簡単だし、いつも同じ内容にしておけば比較も容易。なによりもマンデルブロ集合の画像はともて魅力的だと自分では思っているので、今回もマンデルブロ集合だ。冒頭に作成した画像を載せたけど、やっぱり美しいと思う。

今回のアクターモデルでは、scala.actors.Actorから派生させずに、scala.actors.Actor.actorを使用した。クラスを作るほど大行ではないし、その方がスッキリするからだ。そして、計算のループ部分は末尾再帰とパターンマッチを使っている。関数型言語として使うならやっぱりその方がしっくりくる。ただ、ちゃんと末尾再帰させるように、final修飾子をつけるなど、気をつけること。それと@tailrecアノテーション(scala.annotation.tailrec)は常に付けたほうが良い。@tailrecアノテーションを末尾再帰させたい関数につけておけば、末尾再帰としてコンパイルされなかった時にエラーを返してくれる。アクターを使用しないコードもついでに作成した。画像の色付け部分はScalaでMandelbrot、時間測定は関数の実行時間を計測するには？を参考にさせてもらった。

実行環境としてXeon X5650@2.67GHz * 2 (12コア/24スレッド; メモリ48GB)を使用した。マンデルブロ集合の条件としては、画像の大きさが4,800 x 4,800ピクセルで、(-0.005, -0.005)から(0.005, 0.005)を計算の範囲とし、繰り返し数10,000で10.0を閾値としている。因みにこの範囲は集合に含まれるので計算量としては最大となる(画像としては真っ黒なので面白くはないが)。実行すると最後に画像ファイル(mandelbrot.png)を出力して終了する。

実行した結果、アクターを使用しなかったコードの実行時間が1007.18秒だったのに対し、アクターを使用したコードでは51.636秒であった。約20倍の高速化である。コア数12・スレッド数24であることを考えても、この高速化は十分なのではないだろうか。ところで、アクターを使用しないシングルスレッドでのコードでも以前作成したC++のコード(1067.39秒)より速かった。それに、TBBを使用した並列化したコードでも56.8956秒の計算時間がかかっており、アクターを使用したScalaのコードはそれよりも速い。色の作成の部分など少し異なるところもあるのでそのまま比較することはできないかもしれないが、少なくとも今回の場合ではScalaで十分な速度を得られることは確認できた。余談だが、Telsaのボードを2枚挿ししたマシン上で実行したCUDAのコードでは3.73秒なので次元が違ったりする。

しかし、実際にコードを書くときは注意深くなる必要があるかもしれない。例えば以下のコードがある。

i match { case MAX_LOOP => -1 case _ if zr2 + zi2 >= TH => i case _ => { val zrzi = zr * zi calcLoop(i + 1, cr, ci, zr2 - zi2 + cr, zrzi + zrzi + ci) } }

これを以下のように変更する。

(i, zr2 + zi2) match { case (MAX_LOOP, _) => -1 case (_, z) if z >= TH => i case _ => { val zrzi = zr * zi calcLoop(i + 1, cr, ci, zr2 - zi2 + cr, zrzi + zrzi + ci) } }

これだけのことで実行速度が6倍程遅くなる。これに気付かずにいると本来のパフォーマンスを出すことができない。予想よりもプログラムが遅いと感じた場合は再度コードを確認したほうがいいだろう。

自分は普段は主にC++とPythonを使っていて、目的によって使い分けている。ある程度しっかりした作りで高速に動作させたい場合はC++だし、プロトタイプとして作ったり、結果の解析用コードをサクっと作りたい場合はPythonを使う。Scalaはどのような用途に使えるのか。まず、Javaの資産を使えるのは大きい。ネットワーク処理や画像処理などをある程度本格的につくろうとしたときに便利そうだ。あとは言語の仕様として処理を簡潔に書き表せるという点が良い。ライブラリが強力で簡潔に書ける。この点だけで十分に利用する価値があるだろう。

最後に自分の持っているScalaの書籍を2つ挙げておく。Scalaプログラミング入門は実践的だし、Scalaスケーラブルプログラミングは網羅的なので、どちらも持っていて損はないと思う。

作成したコードを以下に示しておく。

mandelbrot.scala (アクターあり; 並行処理)

// mandelbrot.scala with actor by nox, 2011.07.09 import scala.actors._, Actor._ import scala.annotation.tailrec import java.io.FileOutputStream import java.awt.image.BufferedImage import java.awt.Color import javax.imageio.ImageIO import scala.testing.Benchmark /** * マンデルブロ集合. * SW : 画像の幅. * SH : 画像の高さ. * T : 集合の上の位置. * L : 集合の左の位置. * W : 集合の幅. * H : 集合の高さ. * MAX_LOOP : イテレーションの最大回数. * TH : 閾値. */ final class Mandelbrot(SW: Int, SH: Int, T: Double, L: Double, W: Double, H: Double, MAX_LOOP: Int, TH: Double) { /** * イテレーションの回数から色を決定して任意のピクセルにセットする. */ def setPixel(x: Int, y: Int, a: Any, image: BufferedImage) = a match { case -1 => image setRGB(x, y, 0) case i: Int => image setRGB(x, y, Color HSBtoRGB(i / 100.0f, 1.0f, 1.0f)) } /** * マンデルブロ集合の計算部分. */ @tailrec def calcLoop(i: Int, cr: Double, ci: Double, zr: Double, zi: Double): Int = { val zr2 = zr * zr val zi2 = zi * zi i match { case MAX_LOOP => -1 case _ if zr2 + zi2 >= TH => i case _ => { val zrzi = zr * zi calcLoop(i + 1, cr, ci, zr2 - zi2 + cr, zrzi + zrzi + ci) } } } /** * アクター. * ある幅に存在するピクセルの計算を受け持つ. */ def calc = actor { react { case (ix: Int, image: BufferedImage) => { for (iy <- 0 until SH) setPixel(ix, iy, calcLoop(0, L + (ix.toDouble / SW) * W, T + (iy.toDouble / SH) * H, 0.0, 0.0), image) reply(ix) } } } /** * 幅のピクセル数分だけアクターにメッセージを送る. */ @tailrec def runLoop(ix: Int, results: Array[Future[Any]], image: BufferedImage): Unit = ix match { case SW => results foreach(_ apply) case _ => { results(ix) = calc !! ((ix, image)) runLoop(ix + 1, results, image) } } /** * 実行. * 計算部分の処理時間計測および画像ファイルの書き出し. */ def run = { val results = new Array[Future[Any]](SW) val image = new BufferedImage(SW, SH, BufferedImage TYPE_3BYTE_BGR) val t = (new Benchmark { def run = runLoop(0, results, image) } runBenchmark 1)(0) / 1000.0 println("Time: " + t + " s") val out = new FileOutputStream("mandelbrot.png") ImageIO write(image, "png", out) out close } } object MandelbrotMain { def main(args: Array[String]) = new Mandelbrot(4800, 4800, -0.005, -0.005, 0.01, 0.01, 10000, 10.0) run //new Mandelbrot(640, 480, -1.0, -2.0, 2.6666667, 2.0, 1000, 10.0) run //new Mandelbrot(800, 800, 0.025185, -1.401565, 0.0005, 0.0005, 10000, 10.0) run }

mandelbrot.scala (アクターなし; 逐次処理)

// mandelbrot.scala without actor by nox, 2011.07.09 import scala.annotation.tailrec import java.io.FileOutputStream import java.awt.image.BufferedImage import java.awt.Color import javax.imageio.ImageIO import scala.testing.Benchmark /** * マンデルブロ集合. * SW : 画像の幅. * SH : 画像の高さ. * T : 集合の上の位置. * L : 集合の左の位置. * W : 集合の幅. * H : 集合の高さ. * MAX_LOOP : イテレーションの最大回数. * TH : 閾値. */ final class Mandelbrot(SW: Int, SH: Int, T: Double, L: Double, W: Double, H: Double, MAX_LOOP: Int, TH: Double) { /** * イテレーションの回数から色を決定して任意のピクセルにセットする. */ def setPixel(x: Int, y: Int, a: Any, image: BufferedImage) = a match { case -1 => image setRGB(x, y, 0) case i: Int => image setRGB(x, y, Color HSBtoRGB(i / 100.0f, 1.0f, 1.0f)) } /** * マンデルブロ集合の計算部分. */ @tailrec def calcLoop(i: Int, cr: Double, ci: Double, zr: Double, zi: Double): Int = { val zr2 = zr * zr val zi2 = zi * zi i match { case MAX_LOOP => i case _ if zr2 + zi2 >= TH => i case _ => { val zrzi = zr * zi calcLoop(i + 1, cr, ci, zr2 - zi2 + cr, zrzi + zrzi + ci) } } } def calc(cr: Double, ci: Double): Int = calcLoop(0, cr, ci, 0.0, 0.0) /** * 画像のピクセル数分だけループする. */ @tailrec def runLoop(ix: Int, iy: Int, image: BufferedImage): Unit = (ix, iy) match { case (SW, _) => None case (_, SH) => runLoop(ix + 1, 0, image) case (_, _) => { setPixel(ix, iy, calc(L + (ix.toDouble / SW) * W, T + (iy.toDouble / SH) * H), image) runLoop(ix, iy + 1, image) } } /** * 実行. * 計算部分の処理時間計測および画像ファイルの書き出し. */ def run = { val image = new BufferedImage(SW, SH, BufferedImage TYPE_3BYTE_BGR) val t = (new Benchmark { def run = runLoop(0, 0, image) } runBenchmark 1)(0) / 1000.0 println("Time: " + t + " s") val out = new FileOutputStream("mandelbrot.png") ImageIO write(image, "png", out) out close } } object MandelbrotMain { def main(args: Array[String]) = new Mandelbrot(4800, 4800, -0.005, -0.005, 0.01, 0.01, 10000, 10.0) run //new Mandelbrot(640, 480, -1.0, -2.0, 2.6666667, 2.0, 1000, 10.0) run //new Mandelbrot(800, 800, 0.025185, -1.401565, 0.0005, 0.0005, 10000, 10.0) run }

CUDA 4.0でマルチGPU化が限りなく簡単になっているという話

2011-06-06T03:22:00.004+09:00

以前、複数のGPUでマンデルブロ集合を並列計算というブログ記事を書いた。このときはTeslaが1枚で7.45秒、Teslaが2枚で4.26秒で計算できたと報告したが、マルチGPU化は多少面倒だったし、ある程度のオーバーヘッドが掛かっていた。

しかし、CUDA 4.0がリリースされてから状況が一変した。自由にcudaSetDeviceが呼び出せるようになり、またUVA (Unified Virtual Addressing)を利用することにより、それはそれは簡単にマルチGPU化や、ホスト・複数GPU間での一元的なメモリの参照を実現できることになった。

というわけで、CUDA 4.0を使ったマンデルブロ集合のプログラムを以下に示す。シングルGPUからマルチGPUへ変更した部分については赤字で示してある。ただし、簡便のために、GPUデバイスは2枚で決め打ちとし、マンデルブロ集合の幅は2の倍数のピクセルとなるようにしてある。また、UVAは使わなくても良かったのだが、使い方を示すために利用している。

CUDA 4.0によるマルチGPU化によりマンデルブロ集合計算の実行時間(計算条件は前回と同じ)は7.45秒から3.73秒となった。ほぼ2倍の速度である。シングルGPUからの修正箇所はほんの僅か。カーネル関数に至っては一文字たりとも変更していない。良い時代になったものだ。

mandelbrot_multigpu.cu

// madelbrot using multi GPU devices by nox, 2011.06.06 // nvcc -lcutil_x86_64 -arch sm_13 -use_fast_math -prec-sqrt=false -keep -L ~/NVIDIA_GPU_Computing_SDK/C/lib -I ~/NVIDIA_GPU_Computing_SDK/C/common/inc -g mandelbrot_multigpu.cu -o mandelbrot_multigpu #include <iostream> #include <fstream> #include "cutil_inline.h" using namespace std; const int BLOCK_SIZE_X = 16; const int BLOCK_SIZE_Y = 16; __device__ uchar4 coloring(int n, int b) { int d = n % b; d *= 256 / b; int m = static_cast<int>(d / 42.667f); switch (m) { case 0: return make_uchar4(0, 6 * d, 255, 0); case 1: return make_uchar4(0, 255, 255 - 6 * (d - 43), 0); case 2: return make_uchar4(6 * (d - 86), 255, 0, 0); case 3: return make_uchar4(255, 255 - 6 * (d - 129), 0, 0); case 4: return make_uchar4(255, 0, 6 * (d - 171), 0); case 5: return make_uchar4(255 - 6 * (d - 214), 0, 255, 0); default: return make_uchar4(0, 0, 0, 0); } } __global__ void mandelbrot(float t, float l, float w, float h, int sw, int sh, int max_iter, float th, uchar4* d_color) { int ix = blockIdx.x * blockDim.x + threadIdx.x; int iy = blockIdx.y * blockDim.y + threadIdx.y; if (ix >= sw || iy >= sh) return; float ci = t + (static_cast<float>(iy) / sh) * h; float cr = l + (static_cast<float>(ix) / sw) * w; float zi = 0.0f; float zr = 0.0f; float zrzi, zr2, zi2; for (int i = 0; i < max_iter; i++) { zrzi = zr * zi; zr2 = zr * zr; zi2 = zi * zi; zr = zr2 - zi2 + cr; zi = zrzi + zrzi + ci; if (zi2 + zr2 >= th) { d_color[ix*sh+iy] = coloring(i, 256); return; } } d_color[ix*sh+iy] = make_uchar4(0, 0, 0, 0); } void write_mandelbrot(const string outfile, float t, float l, float w, float h, int sw, int sh, int max_iter=256, float th=2.0f) { dim3 num_blocks((sw - 1) / BLOCK_SIZE_X + 1, (sh - 1) / BLOCK_SIZE_Y + 1, 1); dim3 num_threads(BLOCK_SIZE_X, BLOCK_SIZE_Y, 1); uchar4* h_color; uchar4* d_color[2]; cudaSetDevice(0); cudaMallocHost((void**)&h_color, sizeof(uchar4) * sw * sh); for (int i = 0; i < 2; i++) { cudaSetDevice(i); cudaMalloc((void**)&d_color[i], sizeof(uchar4) * sw * sh / 2); } unsigned int timer; cutCreateTimer(&timer); cutStartTimer(timer); for (int i = 0; i < 2; i++) { cudaSetDevice(i); mandelbrot<<<num_blocks, num_threads>>>(t, l + (w / 2) * i, w / 2, h, sw / 2, sh, max_iter, th, d_color[i]); } cudaThreadSynchronize(); cutStopTimer(timer); cout << "Time: " << cutGetTimerValue(timer) / 1000 << endl; for (int i = 0; i < 2; i++) cudaMemcpy(h_color + sw * sh / 2 * i, d_color[i], sizeof(uchar4) * sw * sh / 2, cudaMemcpyDefault); fstream fs(outfile.c_str(), ios_base::out); fs << sw << endl; fs << sh << endl; for (int i = 0; i < sw * sh; i++) fs << h_color[i].x << h_color[i].y << h_color[i].z; fs.close(); for (int i = 0; i < 2; i++) { cudaSetDevice(i); cudaFree(d_color[i]); } cudaSetDevice(0); cudaFreeHost(h_color); } int main(int argc, char* argv[]) { string outfile("mandelbrot.dat"); if (argc >= 2) outfile = argv[1]; // for UVA cudaSetDevice(0); cudaDeviceEnablePeerAccess(1, 0); cudaSetDevice(1); cudaDeviceEnablePeerAccess(0, 0); // write_mandelbrot(output filename, // top position, // left position, // width, // height, // screen width, // screen height, // max number of iterations [256] // threshold [2.0]); //write_mandelbrot(outfile, -1.0f, -1.5f, 2.0f, 2.0f, 480, 480, 100); //write_mandelbrot(outfile, 0.57f, 0.34f, 0.036f, 0.027f, 6400, 4800, 1000); write_mandelbrot(outfile, -0.005f, -0.005f, 0.01f, 0.01f, 4800, 4800, 10000); return 0; }

出力ファイルの画像への変換は複数のGPUでマンデルブロ集合を並列計算の記事に記載されているread_mandelbrot.pyが利用できる。

C++: Base64エンコード・デコードとURLエンコード

2011-05-13T01:26:00.002+09:00

覚書。Base64エンコード・デコードを行う関数とURLエンコードを行う関数をどんな環境でもすぐに参照できるように書いておく。ただし、短いコードのままにしておきたかったので、まったくもって安全ではない。入力前にチェックを入れるとか、関数内で制限を掛けるとか、引数に最大文字数を渡すとか、適当な処理を入れること。よく分からない場合は使わないのが吉。

#include <iostream> #include <iomanip> #include <sstream> #include <algorithm> #include <cstring> using namespace std; int base64encode(const char* p, char* buf) { const char b64[] = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/="; const int in_size = strlen(p); if (in_size == 0 || p == buf) return 0; int cnt = 0; for (int i = 0; i < (in_size - 1) / 3 + 1; i++) { const unsigned char* c = reinterpret_cast<const unsigned char*>(&p[i*3]); for (int j = 0; j < 4; j++) if (in_size >= i * 3 + j) buf[cnt++] = b64[(c[j-1]<<(6-j*2) | c[j]>>(j*2+2)) & 0x3f]; else buf[cnt++] = '='; } buf[cnt] = '\0'; return cnt; } int base64decode(const char* p, char* buf) { char b64[128] = {}; for (char n = 0, *w = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/="; *w; b64[*w++] = n++ & 0x3f); char c[4]; int i = 0, j, k; while (*p && *p != '=') { for (j = 0; j < 4 && *p != '='; j++) c[j] = b64[*p++]; for (k = 0; k < j - 1; k++) buf[i++] = c[k]<<(k<<1)+2 | c[k+1]>>(2-k<<1); } buf[i] = '\0'; return i; } string urlencode(const string& text) { const string url_letters("-.0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ_abcdefghijklmnopqrstuvwxyz~"); stringstream ss; for (string::const_iterator p = text.begin(); p != text.end(); ++p) { if (binary_search(url_letters.begin(), url_letters.end(), *p)) ss << *p; else ss << "%" << setw(2) << setfill('0') << hex << static_cast<int>(*p); } return ss.str(); } int main() { // Base64エンコードでは入力文字数の4/3倍ほどの領域が必要. // 文字数が少なかったり改行を入れるともっと必要. char buf[256]; // 256は安全ではない. base64encode("test", buf); // (buf, buf)はダメ. cout << buf << endl; // dGVzdA== base64decode(buf, buf); // 邪悪. cout << buf << endl; // test cout << urlencode("user@test.com") << endl; // user%40test.com return 0; }

タンパク質分子において水素原子の位置が異なるアミノ酸構造の同型判定

2011-04-24T02:00:00.004+09:00

今回は興味を持ってもらえる人が限定される記事だと思うけど、以前作ったコードを腐らせてしまうのも勿体無いので敢えて晒してみる。

生体内のタンパク質構造をX線回折やNMRで解析したデータの多くはPDB (Protein Data Bank)データとして登録される。以下に示すように原子タグ、原子の通し番号、原子名、アミノ酸名、アミノ酸の通し番号、原子の座標などがテキストで書かれている。そして、機能の解明などのために分子動力学(MD; molecular dynamics)計算プログラムなどでそれらのPDBデータは利用される。MD計算プログラムは世に沢山あるが、自分がよく使っていたのはAmberというソフトウェアだ。

PDBデータの一部

ATOM 1439 N ILE 212 52.408 -3.243 59.013 1.00 40.03 N ATOM 1440 CA ILE 212 52.511 -3.151 57.556 1.00 33.72 C ATOM 1441 C ILE 212 51.464 -2.243 56.911 1.00 34.65 C ATOM 1442 O ILE 212 51.733 -1.619 55.886 1.00 38.03 O ATOM 1443 CB ILE 212 52.482 -4.572 56.921 1.00 38.88 C ATOM 1444 CG1 ILE 212 53.615 -4.703 55.919 1.00 40.75 C ATOM 1445 CG2 ILE 212 51.129 -4.901 56.281 1.00 39.55 C ATOM 1446 CD1 ILE 212 54.931 -4.446 56.550 1.00 46.31 C ATOM 1447 N HIS 213 50.308 -2.142 57.570 1.00 36.88 N ATOM 1448 CA HIS 213 49.160 -1.334 57.169 1.00 37.60 C ATOM 1449 C HIS 213 49.523 0.121 56.879 1.00 39.63 C ATOM 1450 O HIS 213 48.887 0.773 56.028 1.00 39.63 O ATOM 1451 CB HIS 213 48.115 -1.389 58.289 1.00 44.39 C ATOM 1452 CG HIS 213 46.795 -0.746 57.947 1.00 55.55 C ATOM 1453 ND1 HIS 213 46.364 -0.536 56.651 1.00 54.19 N ATOM 1454 CD2 HIS 213 45.800 -0.306 58.748 1.00 53.97 C ATOM 1455 CE1 HIS 213 45.166 0.002 56.670 1.00 51.63 C ATOM 1456 NE2 HIS 213 44.787 0.157 57.930 1.00 44.85 N ATOM 1457 N CYS 214 50.530 0.634 57.584 1.00 37.10 N ATOM 1458 CA CYS 214 50.986 2.011 57.385 1.00 37.27 C ATOM 1459 C CYS 214 51.504 2.255 55.949 1.00 38.90 C ATOM 1460 O CYS 214 51.699 3.400 55.518 1.00 39.15 O ATOM 1461 CB CYS 214 52.037 2.389 58.443 1.00 36.90 C ATOM 1462 SG CYS 214 53.736 1.793 58.215 1.00 34.05 S

タンパク質はアミノ酸の集合体である。アミノ酸の分子構造はよく知られているが、一部のアミノ酸については水素が結合する位置が異なることがある。例えばヒスチジン(HIS)というアミノ酸では、以下の3種が存在することが知られている(図中の3文字記号はAmberで使われる名称)。

ここでタンパク質に対するMD計算について考えてみる。MD計算ではアミノ酸ごとに計算のためのデータベースを持っており、それを利用して計算される。なので、同じヒスチジンでも水素の付加の位置によって異なるデータが使われる。しかし、PDBデータの多くは水素が付加されておらず(X線結晶構造解析では水素の位置は特定できない)、計算前にアミノ酸の配置や想定されるpHなどから水素を付加させる必要がある。そして、ヒスチジン毎に異なる位置に水素が付加されるわけだ。

異なる位置に水素が付加されたヒスチジンに対して、正しい計算データをMD計算プログラムに伝えるためにそのアミノ酸の名前を変更する必要があるのだが、これが結構な手間となる。例えば、1000個以上のタンパク質構造からヒスチジン分子をビューアで確認してその水素の位置からアミノ酸の名前を付け替えるという作業なんて誰もやりたくないだろう。

そこで、水素の位置の異なるアミノ酸を自動的に判定してアミノ酸の名前を付け直すプログラムを作った。このコードでは部分グラフ同型判定アルゴリズムを利用している。使用したアルゴリズムをここで説明するのは面倒なので、興味のある方はV. Lipets, N. Vanetik, and E. Gudes. Subsea: an efficient heuristic algorithm for subgraph isomorphism. Data Min. Knowl. Disc. 19. 320-350 (2009)あたりを参考にしてほしい。

使い方は次の通り。以下に示す例では、input.pdbが対象とするPDBデータで、名前がHISとなっているアミノ酸について判定する。判定するためのリファレンス構造は3種類で、HID.pdb、HIE.pdb, HIP.pdbの3つのPDB構造に対して行う。構造と一致したら、それぞれアミノ酸名をHID、HIE、HIPに置き換える。最終的に修正した構造をoutput.pdbとして出力する。

% matching_residue input.pdb output.pdb HIS HID HID.pdb HIE HIE.pdb HIP HIP.pdb

標準出力には以下のような表示が出る。この表示の場合、入力PDBファイルには6個のHISがあり、それぞれ17, 66, 132, 146, 167, 261番目のアミノ酸で、HIEとHIPに変換されたことを示している。ここでは判定するための対象としてヒスチジンを例に取っているが、アスパラギン酸やリシンでも構わないし、アミノ酸でなくてもいい。

Number of HIS: 6 HIS 17 -> HIE HIS 66 -> HIE HIS 132 -> HIE HIS 146 -> HIP HIS 167 -> HIE HIS 261 -> HIP

今回に処理については、必ずしも部分グラフとして判定する必要はないのだが、今後の拡張のため、例えばアミノ酸の一部から正しい構造を判別する場合などについても考慮して部分グラフとして扱えるようにしている。

最後に今回のプログラムのソースコードを示す。

matching_residue.cpp

// matching_residue.cpp by nox, 2011.04.18 #include <iostream> #include <fstream> #include <sstream> #include <string> #include <vector> #include <map> #include <algorithm> #include <utility> #include <iomanip> #include <limits> #include <cmath> using namespace std; struct Node { vector<Node*> nb; // Node list of neighbor atoms ([Node]) int idx; // index of the atom in the residue (int) int d; // index of traverse history (int) vector<int> t; // neighbors of traverse history ([int]) string atom; // atom type (string) int res_id; // residue id of the PDB (int) vector<double> crd; // coordinate of the atom ([float,float,float]) Node(int idx_, string atom_, int res_id_, vector<double>& crd_) : idx(idx_), d(-1), atom(atom_), res_id(res_id_), crd(crd_) { } }; struct PdbData { string atom; int res_id; vector<double> crd; PdbData(string line) { stringstream ss; double d; atom = line.substr(76, 2); atom.erase(0, atom.find_first_not_of(' ')); atom.erase(atom.find_last_not_of(' ') + 1); ss << line.substr(20, 6); ss >> res_id; ss.str(""); ss.clear(); ss << line.substr(30, 8); ss >> d; crd.push_back(d); ss.str(""); ss.clear(); ss << line.substr(38, 8); ss >> d; crd.push_back(d); ss.str(""); ss.clear(); ss << line.substr(46, 8); ss >> d; crd.push_back(d); ss.str(""); ss.clear(); } }; // comparison function for sorting of traverse history class LessNeighborD { public: bool operator()(const Node* x, const Node* y) { int x_min_d, y_min_d; x_min_d = y_min_d = numeric_limits<int>::max(); for (vector<Node*>::const_iterator p = x->nb.begin(); p != x->nb.end(); ++p) { if ((*p)->d == -1) continue; x_min_d = min(x_min_d, (*p)->d); } for (vector<Node*>::const_iterator p = y->nb.begin(); p != y->nb.end(); ++p) { if ((*p)->d == -1) continue; y_min_d = min(y_min_d, (*p)->d); } return x_min_d < y_min_d; } }; class GreaterNbSize { public: bool operator()(const Node* x, const Node* y) { return x->nb.size() > y->nb.size(); } }; class LessD { public: bool operator()(const Node* x, const Node* y) { return x->d < y->d; } }; class Matching { private: // visit time of traverse history int vtime; // mapping between target and the replacing residue ((Node,Node)) vector<pair<Node*, Node*> > mapping; map<pair<string, string>, double> bond_dist; public: Matching(); double get_bond_dist(const Node* v1, const Node* v2); double distance(const Node* v1, const Node* v2); void connect(vector<Node*>& nodes); void traverse_history(Node* node); void clear_traverse_history(vector<Node*>& nodes); vector<pair<string, vector<string> > > parse_pdb(string inpdb); vector<vector<Node*> > create_nodes_list(vector<pair<string, vector<string> > >& all_lines, vector<string>& rep_res); bool match(Node* g, vector<Node*>& h, int depth); }; Matching::Matching() : vtime(0) { // table of max bond distances bond_dist[make_pair("C", "C")] = 2.0; bond_dist[make_pair("C", "N")] = 1.8; bond_dist[make_pair("C", "O")] = 1.8; bond_dist[make_pair("C", "H")] = 1.2; bond_dist[make_pair("N", "N")] = 1.8; bond_dist[make_pair("N", "O")] = 1.8; bond_dist[make_pair("H", "N")] = 1.2; bond_dist[make_pair("O", "O")] = 1.8; bond_dist[make_pair("H", "O")] = 1.2; } double Matching::get_bond_dist(const Node* v1, const Node* v2) { pair<string, string> atom_pair(make_pair(min(v1->atom, v2->atom), max(v1->atom, v2->atom))); if (bond_dist.find(atom_pair) != bond_dist.end()) return bond_dist[atom_pair]; return 0.0; } double Matching::distance(const Node* v1, const Node* v2) { double d = 0.0; for (int i = 0; i < 3; i++) { double dv = v1->crd[i] - v2->crd[i]; d += dv * dv; } return sqrt(d); } // create connect list for neighbor atoms void Matching::connect(vector<Node*>& nodes) { for (vector<Node*>::iterator p = nodes.begin(); p != nodes.end(); ++p) { for (vector<Node*>::iterator q = nodes.begin(); q != nodes.end(); ++q) { if (*p == *q || (*p)->idx > (*q)->idx) continue; if (distance(*p, *q) < get_bond_dist(*p, *q)) { (*p)->nb.push_back(*q); (*q)->nb.push_back(*p); } } } } // traverse history, similar to canonical labeling void Matching::traverse_history(Node* node) { node->d = vtime; vtime++; vector<Node*> nb; for (vector<Node*>::iterator p = node->nb.begin(); p != node->nb.end(); ++p) { if ((*p)->d == -1) nb.push_back(*p); else node->t.push_back((*p)->d); } sort(node->t.begin(), node->t.end()); sort(nb.begin(), nb.end(), LessNeighborD()); for (vector<Node*>::iterator p = nb.begin(); p != nb.end(); ++p) if ((*p)->d == -1) traverse_history(*p); } void Matching::clear_traverse_history(vector<Node*>& nodes) { for (vector<Node*>::iterator p = nodes.begin(); p != nodes.end(); ++p) { (*p)->d = -1; (*p)->t.clear(); } mapping.clear(); } vector<pair<string, vector<string> > > Matching::parse_pdb(string inpdb) { int res_id, prev_res_id = -1; vector<string> lines; vector<pair<string, vector<string> > > all_lines; string res, line; stringstream ss; fstream fs(inpdb.c_str(), ios_base::in); while (getline(fs, line)) { ss.str(""); ss.clear(); if (line.length() > 20 && line.substr(0, 4) == "ATOM") { ss << line.substr(20, 6); ss >> res_id; } else res_id = -1; if (prev_res_id == res_id) lines.push_back(line); else { if (!lines.empty()) all_lines.push_back(make_pair(res, lines)); lines.clear(); lines.push_back(line); } if (line.length() > 20 && line.substr(0, 4) == "ATOM") { res = line.substr(17, 3); res.erase(0, res.find_first_not_of(' ')); res.erase(res.find_last_not_of(' ') + 1); } else res = ""; prev_res_id = res_id; } all_lines.push_back(make_pair(res, lines)); return all_lines; } vector<vector<Node*> > Matching::create_nodes_list(vector<pair<string, vector<string> > >& all_lines, vector<string>& rep_res) { vector<vector<Node*> > nodes_list; vector<vector<PdbData> > pdb_data; for (vector<pair<string, vector<string> > >::iterator p = all_lines.begin(); p != all_lines.end(); ++p) { string res(p->first); vector<PdbData> pdbs; for (vector<string>::iterator q = p->second.begin(); q != p->second.end(); ++q) { // for l in lines if (q->length() > 78 && q->substr(0, 4) == "ATOM" && find(rep_res.begin(), rep_res.end(), res) != rep_res.end()) pdbs.push_back(PdbData(*q)); } pdb_data.push_back(pdbs); } for (vector<vector<PdbData> >::iterator p = pdb_data.begin(); p != pdb_data.end(); ++p) { if (p->empty()) continue; vector<Node*> nodes; int idx = 0; for (vector<PdbData>::iterator q = p->begin(); q != p->end(); ++q) nodes.push_back(new Node(idx++, q->atom, q->res_id, q->crd)); connect(nodes); vtime = 0; traverse_history(nodes[0]); sort(nodes.begin(), nodes.end(), LessD()); nodes_list.push_back(nodes); } return nodes_list; } bool Matching::match(Node* g, vector<Node*>& h, int depth) { for (vector<Node*>::iterator p = g->nb.begin(); p != g->nb.end(); ++p) if ((*p)->d != -1) g->t.push_back((*p)->d); if (h[depth]->t.size() != g->t.size() || h[depth]->atom != g->atom) { g->t.clear(); return false; } g->d = depth; sort(g->t.begin(), g->t.end()); if (g->t == h[depth]->t) { mapping.push_back(make_pair(h[depth], g)); if (mapping.size() == h.size()) return true; vector<Node*> nb(mapping[h[depth+1]->t[0]].second->nb); sort(nb.begin(), nb.end()); vector<Node*>::iterator end = nb.end(); for (int i = 1; i < h[depth+1]->t.size(); i++) { vector<Node*> nb2(mapping[h[depth+1]->t[i]].second->nb); sort(nb2.begin(), nb2.end()); end = set_intersection(nb.begin(), end, nb2.begin(), nb2.end(), nb.begin()); } nb.erase(end, nb.end()); sort(nb.begin(), nb.end(), GreaterNbSize()); for (vector<Node*>::iterator p = nb.begin(); p != nb.end(); ++p) if ((*p)->d == -1 && match(*p, h, depth + 1)) return true; mapping.pop_back(); } g->d = -1; g->t.clear(); return false; } int main(int argc, char* argv[]) { string inpdb, outpdb, target; vector<pair<string, string> > res_pdb_list; if (argc < 6 || (argc & 1)) { cerr << "Usage: " << argv[0] << " input_pdb output_pdb target_res replace_res1 replace_res1_pdb [replace_res2 replace_res2_pdb...]" << endl; cerr << " ex.) " << argv[0] << " input.pdb output.pdb HIS HID HID.pdb HIE HIE.pdb HIP HIP.pdb" << endl; exit(1); } inpdb = argv[1]; outpdb = argv[2]; target = argv[3]; for (int i = 4; i < argc; i += 2) res_pdb_list.push_back(make_pair(argv[i], argv[i+1])); Matching m; // calculate nodes of replacing residues map<string, vector<Node*> > rep_res; for (vector<pair<string, string> >::iterator p = res_pdb_list.begin(); p != res_pdb_list.end(); ++p) { vector<pair<string, vector<string> > > all_lines(m.parse_pdb(p->second)); vector<string> res; res.push_back(p->first); vector<vector<Node*> > nodes_list(m.create_nodes_list(all_lines, res)); rep_res[p->first] = nodes_list[0]; } // calculate nodes of target residues in the PDB vector<pair<string, vector<string> > > all_lines(m.parse_pdb(inpdb)); vector<string> res; res.push_back(target); vector<vector<Node*> > nodes_list(m.create_nodes_list(all_lines, res)); cout << "Number of " << target << ": " << nodes_list.size() << endl; // matching residues vector<string> result; bool is_found = false; for (vector<vector<Node*> >::iterator p = nodes_list.begin(); p != nodes_list.end(); ++p) { is_found = false; for (map<string, vector<Node*> >::iterator q = rep_res.begin(); q != rep_res.end(); ++q) { if (p->size() != q->second.size()) continue; m.clear_traverse_history(*p); for (vector<Node*>::iterator r = p->begin(); r != p->end(); ++r) { if (m.match(*r, q->second, 0)) { cout << target << " " << setw(4) << (*r)->res_id << " -> " << q->first << endl; result.push_back(q->first); is_found = true; break; } } if (is_found) break; } if (!is_found) { cout << target << " " << setw(4) << (*p)[0]->res_id << " -> Not found." << endl; result.push_back(target); } } // write PDB fstream fs(outpdb.c_str(), ios_base::out); int idx = 0; for (vector<pair<string, vector<string> > >::iterator p = all_lines.begin(); p != all_lines.end(); ++p) { if (p->first == target) { for (vector<string>::iterator q = p->second.begin(); q != p->second.end(); ++q) { size_t pos = q->find(target); if (pos != string::npos) q->replace(pos, target.size(), result[idx]); fs << *q << endl; } idx++; } else { for (vector<string>::iterator q = p->second.begin(); q != p->second.end(); ++q) fs << *q << endl; } } return 0; }

東北地方太平洋沖地震可視化地図

2011-03-22T01:22:00.005+09:00

東日本大震災(東北関東大震災)により被害を受けられた方々には心よりお見舞い申し上げます。

以前、日本全国コンビニ店舗分布地図をProcessingで作ったが、今回の地震の震源とその大きさについて視覚的に表した地図を作成した。少しでも何かの役に立てば良いのだが。

震源とその大きさを日本地図上に円として表現している。円の大きさはマグニチュードと震源の深さに依存している(これは大まかな目安であり、揺れた地域や震度・エネルギーに正確に対応しているわけではない)。また、震源の深さによって円の色が変わり、浅ければ赤に、深ければ緑に近づく。海の色は時刻を現しており、正午が最も明るい青で表現され、深夜であれば真っ黒となる。データについては、日本気象協会が提供している3月9日から20日までの地震情報を利用させて頂いた。

操作方法は、スペースキーでポーズ、'N'キーで3時間進め、'B'キーで3時間戻る。'+'キーで時間の進みが速くなり、'-'キーで遅くなる。マウスの左クリックでドラッグすれば地図を動かすことができ、右クリックで上下にドラッグすれば拡大・縮小となる。

This browser does not have a Java Plug-in.
Get the latest Java Plug-in here.

可視化地図から、3月11日14時46分のマグニチュード9.0の地震の起こる二日ほど前から、三陸沖で中規模の地震が頻発していることが分かる。ところが、M9.0の地震の数時間前からは揺れが全て途絶え、嵐の前の静けさの様相となる。そして、M9.0の地震の直後からはひっきりなしに揺れが続き、数日してやや沈静化してきている。ただ、M6程度の地震は未だに起こっているので、安心するにはまだ早いかもしれない。最近の地震では福島県沖や茨城県沖に多く、ややと南下している様子が分かる。

以下、ソースコードを示す。

earthquake.pde

/* earthquake.pde by nox, 2011.3.22 */ String convData = "quake.tsv.gz"; String japanMap = "japan.svg"; PShape mapShape; int totalCount; Place[] places; int placeCount = 0; final float minX = -0.19834; final float maxX = 0.2425; final float minY = -0.1875; final float maxY = 0.1845; PImage mapImage; PFont font; float offsetX = 0.0; float offsetY = 0.0; int centerX = 0; int centerY = 0; float zoom = 1.0; int mxStart, myStart, myPos; int startTime, currentTime, stopTime; int month_, day_, hour_, minute_; boolean is_paused = false; int speed = 10; public void setup() { mapShape = loadShape(japanMap); smooth(); loop(); size(int(mapShape.width), int(mapShape.height), JAVA2D); // 539, 563 shapeMode(CORNER); mapShape.disableStyle(); font = loadFont("CourierNewPSMT-14.vlw"); textMode(SCREEN); textFont(font); readData(); startTime = millis(); loop(); } public void draw() { if (!mousePressed) currentTime = millis() - startTime; int currentDate = currentTime + (hour_ * 60 + minute_) * speed; int mon_ = month_; int d_ = day_ + currentDate / (24 * 60 * speed); int h_ = currentDate / (60 * speed) % 24; int m_ = currentDate / speed % 60; if (d_ >= 21 || d_ <= 8 || h_ < 0 || m_ < 0) startTime = millis(); background(color(0, 0, (720 - abs(h_ * 60 + m_ - 720)) * 0.1)); noStroke(); fill(32); shape(mapShape, int(offsetX * zoom) + centerX, int(offsetY * zoom) + centerY); fill(127); String timeFormat = nf(mon_, 2) + "/" + nf(d_, 2) + " " + nf(h_, 2) + ":" + nf(m_, 2) + " speed: " + nf(10.0 / speed, 1, 2); text(timeFormat, 15, 20); for (int i = 0; i < placeCount; i++) places[i].draw(); } float TX(float x) { float offset = width * (1.0 - zoom) * 0.5; return map(x, minX, maxX, offset, width - offset); } float TY(float y) { float offset = height * (1.0 - zoom) * 0.5; return map(y, minY, maxY, height - offset, offset); } void mousePressed() { if (!is_paused) { mxStart = int(mouseX - offsetX * zoom); myStart = int(mouseY - offsetY * zoom); myPos = mouseY; stopTime(); loop(); } } void mouseReleased() { if (!is_paused) startTime(); } void mouseDragged() { if (is_paused) return; if (mouseButton == LEFT) { offsetX = (mouseX - mxStart) / zoom; offsetY = (mouseY - myStart) / zoom; } else if (mouseButton == RIGHT) { if (mouseY - myPos > 4) { float zoomOut = 9.8 / 10.0; mapShape.scale(zoomOut); zoom *= zoomOut; centerX = int(width * (1.0 - zoom) * 0.5); centerY = int(height * (1.0 - zoom) * 0.5); myPos = mouseY; } else if (mouseY - myPos < -4) { float zoom_in = 10.0 / 9.8; mapShape.scale(zoom_in); zoom *= zoom_in; centerX = int(width * (1.0 - zoom) * 0.5); centerY = int(height * (1.0 - zoom) * 0.5); myPos = mouseY; } } } void startTime() { startTime += millis() - stopTime; loop(); } void stopTime() { noLoop(); stopTime = millis(); } void keyPressed() { if (key == ' ') { if (is_paused) { startTime(); is_paused = false; } else { stopTime(); is_paused = true; } } else if (key == 'n' || key == 'N') startTime -= 180 * speed; else if (key == 'b' || key == 'B') startTime += 180 * speed; else if (key == '+' && speed > 3) speed -= 1; else if (key == '-' && speed < 30) speed += 1; } void readData() { new Slurper(); } Place parsePlace(String line) { String pieces[] = split(line, '\t'); int mins = int(pieces[0]); int mon = int(pieces[1]); int d = int(pieces[2]); int h = int(pieces[3]); int m = int(pieces[4]); float x = float(pieces[5]); float y = float(pieces[6]); float magnitude = float(pieces[7]); float depth = float(pieces[8]); String name = pieces[9]; return new Place(mins, mon, d, h, m, x, y, magnitude, depth, name); }

Place.pde

class Place { int mins; int mon, d, h, m; float x, y; float magnitude; float depth; String name; public Place(int mins, int mon, int d, int h, int m, float x, float y, float magnitude, float depth, String name) { this.mins = mins; this.mon = mon; this.d = d; this.h = h; this.m = m; this.x = x; this.y = y; this.magnitude = magnitude; this.depth = depth; this.name = name; } public void draw() { int xx = (int)TX(this.x) + int(offsetX * zoom); int yy = (int)TY(this.y) + int(offsetY * zoom); int a = mins * speed + 255 - currentTime; if (magnitude == 0.0 || a < 0 || a > 255) return; float r = pow(5.0, (magnitude / 2.7)) / sqrt(depth / 10 + 1); float m = r * ((255 - a) / 50.0) * zoom; fill(color(255 - this.depth * 2, this.depth * 2, 0), a); ellipse(xx, yy, m, m); } }

Slurper.pde

class Slurper implements Runnable { Slurper() { Thread thread = new Thread(this); thread.start(); } public void run() { try { BufferedReader reader = createReader(convData); String line = reader.readLine(); totalCount = int(line); places = new Place[totalCount]; line = reader.readLine(); places[placeCount++] = parsePlace(line); month_ = places[0].mon; day_ = places[0].d; hour_ = places[0].h; minute_ = places[0].m; while ((line = reader.readLine()) != null) places[placeCount++] = parsePlace(line); } catch (IOException e) { e.printStackTrace(); } } }

開発エンジニアの世界へ

2011-03-07T01:18:00.002+09:00

昨年は開発エンジニアが転職するという話題が多かったように思う。それに触発されたというわけではないが、自分も昨年11月に開発エンジニアとして転職した。そしてつい先日、試用期間の3ヶ月が過ぎた。これで何かが変わったというわけではないが、正式に採用されたということで、転職して思うことなどをブログに書くことにした。転職先については敢えて名前を出さないが、主にマルチコアやGPGPUなどの並列処理を扱うベンチャー企業といえばピンとくる人もいるかも知れない。

自分はこれまでずっとアカデミックな研究所に所属していたのだけど、少々居座りすぎてしまったことは否めない。基本的に研究者は流動的であることが推奨される。そして、所属していた研究所は所長でさえも任期制で、研究員は普段から職探しをするのが当たり前になっている。しかし、アカデミックなポストは空きも少なく、枠が一人のところに100人200人と応募してくることはザラで、終身雇用の職を得るのはかなり難しい。

そんな中、自分はほとんど職探しをしていなかった。第一の理由として、自分が専攻した薬学の分野でバリバリとコードを書くことと研究が両立できるか疑問だったことがある。ただでさえ狭き枠にそのような特殊な環境を求めるのが非常に厳しいものに思えたからだ。第二の理由として、所属していた研究所ではメインでHPCを扱っており薬学に関連した研究を遂行するためのプログラムを自由に書くことができ、それが求められていたことがある。相手の要求と自分の希望が合致していた。

そうは言っても、ここ最近の政治的判断による不透明さや年齢に伴うマネージメントの必要性など、当たり前だが要求は厳しくなってくる。また、地理的な面でも大きく変わることになったし、こちらの事情で現在の住処を離れたくないということもあった。研究所で一緒に仕事をしていた人たちには大変お世話になっていたので少々迷うところもあったのだが、最終的に転職することにした。

自分の仕事選びの基準は単純で「楽しめるかどうか」だけだ。楽しめればどんなにきつい仕事でも苦にならないし、逆にきつければきついほどチャレンジングであり、やりがいを感じられる。特に開発エンジニアの方なら、自分の技術で困難な問題を克服する達成感、創造する喜び、知識を得る楽しみなどについて分かってもらえるのではないかと思う。それに、企業としても生産性が上がるわけだから、まさにWin-Winの関係だ。もし、エンジニアでこれらの喜びや楽しみを見いだせない人がいたとしたら、何故、極端な専門職であるエンジニアを選んだのか知りたいところだ。

今の職場は自分自身の意志による最初のエントリーだったが、有難い事にそこで働けることになった。何年も前から知っていて、とても技術力のある企業だと思ったからここを選んだ。そして、そう思ったことは間違っておらず、想像していたより遥かに楽しんでいる自分がいる。大企業とは違って小回りはきくし、比較的やりたい事をやらせてもらえるし(もちろん責任は伴う)、別プロジェクトの開発者とは同じフロアにいるので交流し易い。そしてなにより、この職場ではプログラミングコンテスト優勝者やICPC関係者、ネットで時々名前を見かけるような技術力の高い人たちがいて話を聞くだけでも楽しい。示し合わせたわけでもないのに自分を含めて数人、先日のBoost.勉強会に参加している事実を以てしても、技術に対して真摯であることが伺える(参加はしなかったがライブ配信を見ていたという人たちもいたようだ)。それに、個人だと到底いじることができないような特殊な環境に触れることができるのも良い(まあ、特殊な環境という意味では研究所にいたころも複数のスーパーコンピュータをいじっていたわけで、それはそれで楽しかったけど)。ついでに、報酬や待遇も悪くないと思う。

最近では若い人たちを積極的に採用しているようで会社説明会も開いている。プログラミング(特に並列処理)に興味を持っている方に参加してもらえると嬉しい。

複数のGPUでマンデルブロ集合を並列計算

2011-02-15T02:39:00.002+09:00

範囲(-0.005, -0.005, 0.005, 0.005)のマンデルブロ集合を描画サイズ4,800x4,800、繰り返しの上限10,000として計算させてみた。C++でコードを書いてXeon X5650 1コアで走らせたところ942.97秒かかった(SIMD最適化はしていない)。TBBを利用した12論理コアの並列計算では88.68秒だった。次いでCUDAを使ってTeslaで走らせてみたが7.45秒まで短縮された。Teslaパない。そして贅沢にも2枚のTeslaをスレッドで並列化して使ってみたら4.26秒で計算できた。実にXeon 1コアの220倍の速度が出たわけだ。カリカリチューンをしなくてもこの程度の高速化ができるということが重要だ。

因みにマンデルブロ集合の上記の範囲は数値が発散しない集合部分であり、描画させてみても真っ黒なので面白くはない。これは並列化した際に計算が偏らないようにしたかったのでこのような範囲を指定している。プログラムで出力させたファイルは色の生データなのでそのままでは表示できない。一応、画像表示するためのPythonコードも付け加えておく。

以下に、GPU2枚を利用してマンデルブロ集合を計算するCUDAコードを示しておく。

mandelbrot_thread.cu

// Mandelbrot set using GPGPU by nox, 2011.02.12 // nvcc -lcutil_x86_64 -arch sm_13 -use_fast_math -prec-sqrt=false -keep -L ~/NVIDIA_GPU_Computing_SDK/C/lib -I ~/NVIDIA_GPU_Computing_SDK/C/common/inc -g mandelbrot_thread.cu -o mandelbrot_thread #include <iostream> #include <fstream> #include <cutil_inline.h> #include <multithreading.h> using namespace std; const int BLOCK_SIZE_X = 16; const int BLOCK_SIZE_Y = 16; struct MandelbrotParam { int dev; // GPU device id uchar4* h_color; // image buffer float t, l, w, h; // top, left, width, height int sw, sh; // screen width, screen height int max_iter; // max number of iterators float th; // threshold }; __device__ uchar4 coloring(int n, int b) { int d = n % b; d *= 256 / b; int m = static_cast<int>(d / 42.667f); switch (m) { case 0: return make_uchar4(0, 6 * d, 255, 0); case 1: return make_uchar4(0, 255, 255 - 6 * (d - 43), 0); case 2: return make_uchar4(6 * (d - 86), 255, 0, 0); case 3: return make_uchar4(255, 255 - 6 * (d - 129), 0, 0); case 4: return make_uchar4(255, 0, 6 * (d - 171), 0); case 5: return make_uchar4(255 - 6 * (d - 214), 0, 255, 0); default: return make_uchar4(0, 0, 0, 0); } } __global__ void mandelbrot(float t, float l, float w, float h, int sw, int sh, int max_iter, float th, uchar4* d_color) { int ix = blockIdx.x * blockDim.x + threadIdx.x; int iy = blockIdx.y * blockDim.y + threadIdx.y; if (ix >= sw || iy >= sh) return; float ci = t + (static_cast<float>(iy) / sh) * h; float cr = l + (static_cast<float>(ix) / sw) * w; float zi = 0.0f; float zr = 0.0f; float zrzi, zr2, zi2; for (int i = 0; i < max_iter; i++) { zrzi = zr * zi; zr2 = zr * zr; zi2 = zi * zi; zr = zr2 - zi2 + cr; zi = zrzi + zrzi + ci; if (zi2 + zr2 >= th) { d_color[ix*sh+iy] = coloring(i, 256); return; } } d_color[ix*sh+iy] = make_uchar4(0, 0, 0, 0); } CUT_THREADPROC mandelbrot_thread(void* args) { MandelbrotParam* param = (MandelbrotParam*)args; cudaSetDevice(param->dev); uchar4* h_color = param->h_color; float t = param->t; float l = param->l; float w = param->w; float h = param->h; int sw = param->sw; int sh = param->sh; int max_iter = param->max_iter; float th = param->th; dim3 num_blocks((sw - 1) / BLOCK_SIZE_X + 1, (sh - 1) / BLOCK_SIZE_Y + 1, 1); dim3 num_threads(BLOCK_SIZE_X, BLOCK_SIZE_Y, 1); uchar4* d_color; cudaMalloc((void**)&d_color, sizeof(uchar4) * sw * sh); mandelbrot<<<num_blocks, num_threads>>>(t, l, w, h, sw, sh, max_iter, th, d_color); cudaThreadSynchronize(); cudaMemcpy(h_color, d_color, sizeof(uchar4) * sw * sh, cudaMemcpyDeviceToHost); cudaFree(d_color); CUT_THREADEND; } // outfile : output filename // t : top position // l : left position // w : width // h : height // sw : screen width // sh : screen height // max_iter : max number of iterations [256] // th : threshold [2.0] void write_mandelbrot(const string outfile, float t, float l, float w, float h, int sw, int sh, int max_iter=256, float th=2.0f) { MandelbrotParam param[2]; uchar4* h_color; cudaMallocHost((void**)&h_color, sizeof(uchar4) * sw * sh); // using 2 GPUs for (int i = 0; i < 2; i++) { param[i].dev = i; param[i].h_color = h_color; param[i].t = t; param[i].l = l; param[i].w = w / 2.0f; param[i].h = h; param[i].sw = sw / 2; param[i].sh = sh; param[i].max_iter = max_iter; param[i].th = th; } param[1].h_color = h_color + sw * sh / 2; param[1].l = l + w / 2.0f; unsigned int timer; cutCreateTimer(&timer); cutStartTimer(timer); CUTThread threads[2]; for (int i = 0; i < 2; i++) threads[i] = cutStartThread((CUT_THREADROUTINE)mandelbrot_thread, (void*)&param[i]); cutWaitForThreads(threads, 2); cutStopTimer(timer); cout << "Time: " << cutGetTimerValue(timer) / 1000 << endl; fstream fs(outfile.c_str(), ios_base::out); fs << sw << endl; fs << sh << endl; for (int i = 0; i < sw * sh; i++) fs << h_color[i].x << h_color[i].y << h_color[i].z; fs.close(); cudaFreeHost(h_color); } int main(int argc, char* argv[]) { string outfile("mandelbrot.dat"); if (argc >= 2) outfile = argv[1]; // write_mandelbrot(output filename, // top position, // left position, // width, // height, // screen width, // screen height, // max number of iterations [256] // threshold [2.0]); //write_mandelbrot(outfile, -1.0f, -1.5f, 2.0f, 2.0f, 480, 480, 100); //write_mandelbrot(outfile, 0.57f, 0.34f, 0.036f, 0.027f, 6400, 4800, 1000); write_mandelbrot(outfile, -0.005f, -0.005f, 0.01f, 0.01f, 4800, 4800, 10000); return 0; }

表示用のPythonコード。

read_mandelbrot.py

#!/usr/bin/env python import sys, os, Image def main(args): if len(args) < 2: print >>sys.stderr, "%s datafile [imagefile]" % os.path.basename(args[0]) sys.exit() datafile = args[1] imagefile = args[2] if len(args) > 2 else "" f = file(datafile) sw = int(f.readline()) sh = int(f.readline()) data = map(ord, f.read()) im = Image.new("RGB", (sw, sh)) for x in range(sw): for y in range(sh): pos = (x * sh + y) * 3; im.putpixel((x, sh - y - 1), tuple(data[pos:pos+3])) if imagefile: im.save(imagefile) im.show() if __name__ == "__main__": main(sys.argv)

2010年から2011年へ

2011-01-01T01:36:00.002+09:00

明けましておめでとうございます。

今年は2011年で素数。前回の素数の年は8年前の2003年、次の素数の年は6年後の2017年。だからどうと言うわけでもないのだけど、なんとなく特別な年であるように思えてくる。昨年は自分にとっては大きな節目の年であった。環境も大きく変わって、なんちゃってプログラマから「なんちゃって」を外すことができたのではないかと思う。そして今年は、どんな数にも割り込まれず自分自身を失わない2011年のように、自らの意志をしっかり持って行動する年にしたい。

ところで、冒頭のQRコードだけど、いつものようにAndroid SL4Aのソースコードになっている。SL4Aを起動して、メニューからAddを選択し、Scan Barcodeで取り込むと new_year.py が作られる。大したコードではないのだけど、当ブログからのメッセージが入っている。音が出るので注意。

これからもどうぞよろしくお願いします。

ある重さを量るのに使う錘の組み合わせは何通り?

2010-12-29T22:16:00.003+09:00

問題: 1, 5, 10, 50, 100, 500グラムの6種類の錘があります。それぞれの錘はいくつでも使うことができます。ある重さを量るときに使う錘の組み合わせは何通りになりますか。それを求めるプログラムを書いてください。ここで量る重さはグラム単位の整数とし、最大で100キログラムとします。10グラムの重さを量る場合、10グラムの錘が1個、5グラムの錘が2個、5グラムの錘1個と1グラムの錘が5個、1グラムの錘が10個の組み合わせになり、全部で4通りとなります。

以下、解答例。

weights.cpp

// 指定した重さを量るのに使う錘の組み合わせの数を求めるプログラム. // 錘は 1g, 5g, 10g, 50g, 100g, 500g の6種類. // 重さ 700,000g 程度までなら桁あふれせずに計算できる. #include <iostream> #include <map> #include <algorithm> #include <cstdlib> using namespace std; const int weights[] = { 1, 5, 10, 50, 100, 500 }; // 錘(昇順). const int N = sizeof(weights) / sizeof(int); // 錘の種類. // 求めた錘の組み合わせの数のメモ. // 下位3ビットは使用する錘(solveのidx)を表す. // 残りのビットは重さ(solveのv)を表す. map<int, unsigned long long> memo; // 指定した重さに対する錘の組み合わせの数を求める. // v : 重さ // idx : 使用する錘 // N-1の場合はweights[0]からweights[N-1]までの錘を使用する(すべての錘). // 2の場合はweights[0]からweights[2]までの錘を使用する(1, 5, 10の錘). // 戻り値: 組み合わせの数 unsigned long long solve(int v, int idx=N-1) { // 既に計算済みであるならその結果を返す. if (memo.find(v<<3|idx) != memo.end()) return memo[v<<3|idx]; // 重さが0になったのならば新たな組み合わせが1つ見つかった. if (v == 0) return 1; unsigned long long cnt = 0; // 錘の種類だけループを回す. for (int i = idx; i >= 0; i--) // 重さが錘よりも軽い場合は次の錘. if (v >= weights[i]) // 求めた組み合わせの数をカウントに加える. cnt += solve(v - weights[i], i); // 求めた組み合わせの数をメモしておく. memo[v<<3|idx] = cnt; return cnt; } int main(int argc, char* argv[]) { if (argc < 2) { cerr << "Usage: " << argv[0] << " [weight]" << endl; exit(1); } cout << solve(atoi(argv[1])) << endl; return 0; }

この手のアルゴリズムの問題に慣れた人なら簡単だと思う。自分はこれと同類の問題を初めて聞いたときに即座に書けなかったので自戒を込めてここで書いてみた。

ところで、このコードで使っているメモ化だが、これをしないと実用的には使うことはできない。例えば、2,000グラムの組み合わせを求めた場合、メモ化していれば自分の環境では0.002秒で答えが出るが、メモ化していないと85秒も掛かる。因みにこの場合の組み合わせは4,443,355通り。

Android端末による自動通訳を一行のPythonコードで実装する

2010-11-08T00:43:00.009+09:00

最近このブログではAndroidのSL4Aネタが多いのだけど、それだけ遊べるのだから仕方がない。SL4AのPythonを使えば実質一行で自動通訳プログラムを作ることもできる。日本語で喋った文章が翻訳されて英語の音声で返ってくる。

import android,urllib,urllib2,simplejson;droid=android.Android();droid.ttsSpeak(simplejson.loads(urllib2.urlopen('http://ajax.googleapis.com/ajax/services/language/translate?v=1.0&q=%s&langpair=%s%%7C%s'%(urllib.quote(droid.recognizeSpeech().result.encode('utf-8')),'ja','en')).read())['responseData']['translatedText'])

このプログラムでは日本語を英語に変換するが、コード中の en を変更すれば別の外国語に通訳することもできる。例えば fr に変更すればフランス語に通訳される。ただし、通訳した外国語はGoogleによる翻訳の精度に依存するので、実用的に用いるにはもう少し精度が良くなって欲しいところだ。それでもこれだけ簡単に自動通訳プログラムを作れるのだからAndroidとSL4Aは大したものだと思う。

以下にもう少し分かりやすいコードを示しておく。ついでに翻訳結果をダイアログに表示するように変更してある。

translator.py

# -*- coding: utf-8 -*- import android,urllib,urllib2,simplejson def translator(text,from_lang,to_lang): url='http://ajax.googleapis.com/ajax/services/language/translate?v=1.0&q=%s&langpair=%s%%7C%s'%(urllib.quote(text.encode('utf-8')),from_lang,to_lang) data=simplejson.loads(urllib2.urlopen(url).read()) return data['responseData']['translatedText'] droid=android.Android() text=droid.recognizeSpeech().result t=translator(text,'ja','en') droid.ttsSpeak(t) droid.dialogCreateAlert(u'翻訳結果',u"%s\n\n%s"%(text,t)) droid.dialogShow()

SL4AのPythonを使ってAndroid端末に日本語を喋らせてみた

2010-11-02T01:19:00.006+09:00

先日、ドコモのGALAXY Sを購入した。丁度1年前に購入したHT-03Aからの機種変更になる。Androidのバージョンは1.6から2.2となり、性能は格段に良くなった。この1年での技術の進歩には驚かされる。GALAXY SでSL4Aが利用できるかは気になるところだが、実は購入する前に既に動作することを確認していたので、その点については心配なかった。もしSL4Aが使えなかったら、多分購入しなかったと思う。

この新しいAndroid機を使って、SL4AのPythonで日本語を喋らせてみることにした。英語であればttsSpeakのAPIを使えば一発なのだが漢字かな混じりの日本語では簡単には行かない。まずは日本語の発音を取得しなくてはならないが、それについてはYahoo! デベロッパーネットワークの日本語形態素解析を使うことにした。これなら助詞の「は」も「わ」という発音であることがわかるし、後々、応用が効くだろう。

作成したソースコードは最後に示してあるが、短いコードで簡単に実装できた。使い方も簡単で、入力ダイアログから喋らせたい文章を入力するだけだ。それを形態素解析のWeb APIでXMLとして取得し、Beautiful Soupで解析している。取得した平仮名をその発音に近い英語に直すだけだ。ローマ字に置き換えるだけでは日本語として正しく発音されないので、適当にいじってある。

実用的なプログラムにしたければ、Galatea Projectなどを利用して、ちゃんとした日本語を喋らせるようにしたほうが良いのだろうけど、形態素解析を使ってみたかったし、英語を無理やり日本語にするところも面白かったので、今回はこれで良しとした。やっぱり自分が楽しめないとね。

例によって、このプログラムを使って子供相手に遊んでみた。元の文章を知っていれば問題なく聞き取れるのだが、知らないと思ったよりも聞き取れないことを逆手に取って、何を喋っているかを当てるゲームをしてみた。こんな単純なことなのだが、子供たちは思いのほか楽しんでいたようだ。インチキ外国人ぽい雰囲気が面白いらしい。

作成したソースコードは以下の通り。

speak_ja.py

# -*- coding: utf-8 -*- import android import sys,os,urllib,urllib2 from BeautifulSoup import BeautifulSoup YAHOO_APP_ID='Yahoo!デベロッパーネットワークのアプリケーションID' KEITAISO_API='http://jlp.yahooapis.jp/MAService/V1/parse?appid=%s&results=ma&sentence=%s' KANA=[u'きゃ',u'きぃ',u'きゅ',u'きぇ',u'きょ', u'くぁ',u'くぃ',u'くぅ',u'くぇ',u'くぉ', u'ぎゃ',u'ぎぃ',u'ぎゅ',u'ぎぇ',u'ぎょ', u'ぐぁ',u'ぐぃ',u'ぐぅ',u'ぐぇ',u'ぐぉ', u'しゃ',u'しぃ',u'しゅ',u'しぇ',u'しょ', u'すぁ',u'すぃ',u'すぅ',u'すぇ',u'すぉ', u'じゃ',u'じぃ',u'じゅ',u'じぇ',u'じょ', u'ちゃ',u'ちぃ',u'ちゅ',u'ちぇ',u'ちょ', u'てゃ',u'てぃ',u'てゅ',u'てぇ',u'てょ', u'とぁ',u'とぃ',u'とぅ',u'とぇ',u'とぉ', u'ぢゃ',u'ぢぃ',u'ぢゅ',u'ぢぇ',u'ぢょ', u'でゃ',u'でぃ',u'でゅ',u'でぇ',u'でょ', u'どぁ',u'どぃ',u'どぅ',u'どぇ',u'どぉ', u'にゃ',u'にぃ',u'にゅ',u'にぇ',u'にょ', u'ひゃ',u'ひぃ',u'ひゅ',u'ひぇ',u'ひょ', u'ふぁ',u'ふぃ',u'ふぅ',u'ふぇ',u'ふぉ', u'びゃ',u'びぃ',u'びゅ',u'びぇ',u'びょ', u'ぴゃ',u'ぴぃ',u'ぴゅ',u'ぴぇ',u'ぴょ', u'みゃ',u'みぃ',u'みゅ',u'みぇ',u'みょ', u'りゃ',u'りぃ',u'りゅ',u'りぇ',u'りょ', u'うぁ',u'うぃ',u'うぇ',u'うぉ'] PRON=['kya','kyi','kyu','kyei','kio', 'qa','qi','qwu','qei','qo', 'gya','gyi','gyu','gyei','gyo', 'gwa','gwi','gwu','gwei','gwo', 'sha','syi','shu','shei','sho', 'swa','swi','swu','swei','swo', 'ja','zee','juu','jei','jo', 'cha','tyi','chu','chei','cho', 'tha','thi','thu','thei','tho', 'twa','twi','two','twei','two', 'dya','dyi','dyu','dyei','dyo', 'dha','dhi','dhu','dhei','dho', 'dwa','dwi','dwu','dwei','dwo', 'nya','nyi','nyu','nyei','nyo', 'hya','hyi','hyu','hyei','hyo', 'fa','fi','foo','fei','fo', 'bya','byi','byu','byei','byo', 'pya','pyi','pyu','pyei','pyo', 'mya','myi','myu','myei','myo', 'rya','ryi','ryu','ryei','ryo', 'wha','wi','wei','wo'] KANA+=u'あいうえおかきくけこさしすせそたちつてとなにぬねのはひふへほまみむめもやゆよらりるれろわゐゑをんがぎぐげござじずぜぞだぢづでどばびぶべぼぱぴぷぺぽぁぃぅぇぉ' PRON+=['a','ee','oo','ae','o', 'ka','kee','koo','kei','ko', 'sa','she','soo','sei','so', 'ta','chee','tsu','tei','toe', 'na','nee','nuu','neigh','no', 'ha','hee','foo','hey','ho', 'ma','mee','moo','mei','mo', 'yah','you','yor', 'ra','ree','roo','rei','ro', 'wa','ee','ae','wo','nn', 'ga','gee','goo','gei','go', 'za','zee','zoo','zei','zo', 'da','zee','doo','dei','do', 'ba','bee','boo','bei','bo', 'pa','pee','poo','pei','po', 'a','ee','oo','ae','o'] def get_keitaiso(text): xml=urllib2.urlopen(KEITAISO_API % (YAHOO_APP_ID,urllib.quote(text.encode('utf-8')))).read() ret='' for data in BeautifulSoup(xml)('ma_result'): for r,p in zip(data('reading'),data('pos')): d,x=r.renderContents(),p.renderContents() if x=='助詞' and d=='は': ret+='わ' elif x!='特殊': ret+=d ret=ret.decode('utf-8') T={} for i in range(86): T[ord(u'ァ')+i]=unichr(ord(u'ぁ')+i) ret=ret.translate(T) for k,r in zip(KANA,PRON): ret=ret.replace(k,r+' ') rett=ret; for i,c in enumerate(ret): c=c.encode('utf-8') if c=='ー': ret=ret.replace(u'ー',rett[i-2]+' ',1) if c=='っ': if len(rett)>i+1: ret=ret.replace(u'っ',rett[i+1],1) else: ret=ret.replace(u'っ','',1) return ret droid=android.Android() text=droid.dialogGetInput(u'日本語を喋ります',u'何を喋らせますか?').result.strip() droid.ttsSpeak(get_keitaiso(text)) droid.makeToast(text)

インチキ外国人なら喋る内容もインチキっぽくしようと思い付いたので、入力した文章をGoogleの翻訳APIで英訳し、それをまた和訳するという処理を挟んでみた。例えば「一番いいのを頼む。」と入力したら「最高のお問い合わせください。」と喋る。まあ、これはジョークプログラムにしかならないけど、形態素解析を利用した人工無脳に仕立て上げたりするのも楽しいかもしれない。

上記のspeak_ja.pyに以下の赤で示したコードを追加すればいい。

fake_japanese.py

# -*- coding: utf-8 -*- import android import sys,os,urllib,urllib2,simplejson from BeautifulSoup import BeautifulSoup ### 途中省略 def translator(text,from_lang,to_lang): url='http://ajax.googleapis.com/ajax/services/language/translate?v=1.0&q=%s&langpair=%s%%7C%s' % (urllib.quote(text.encode('utf-8')),from_lang,to_lang) data=simplejson.loads(urllib2.urlopen(url).read()) return data['responseData']['translatedText'] droid=android.Android() text=droid.dialogGetInput(u'日本語を喋ります',u'何を喋らせますか?').result.strip() text=translator(translator(text,'ja','en'),'en','ja') droid.ttsSpeak(get_keitaiso(text)) droid.makeToast(text)

Android端末上に電子掲示板システムを構築する方法

2010-10-09T05:46:00.007+09:00

最近になって日本においてもAndroid端末が続々と発表されて巷で賑わいを見せている。ドコモからはGALAXY S、auからはIS03、ソフトバンクからはDesire HDと立て続けに発売される。このほかにも年末までにタブレット端末を含めた複数のAndroid端末が発売されるようで結構なことだ。

Androidも盛り上がってきたし、Android端末を使って手軽で役に立つことができないか考えてみた。そこで今回、Android端末をウェブサーバにして、そこに電子掲示板システム(BBS)を構築してみた。これさえあれば不意にプライベートなBBSを使いたくなったときにいつでも利用することができる。たとえばライトニングトークやセミナーなどのようなイベントの参加者からその場でちょっとしたアンケートや感想を貰いたいときに便利ではないかと思う。ちょっとした話題作りにもなるかも。

電子掲示板システムの作成に必要なものはAndroid端末とSL4A/Pythonだけ。あとは今回作成した android_bbs.py を使えばいい。そして、SL4Aを使ってサーバを立ち上げてから、android_bbs.pyを起動すれば完了だ。SL4Aによるサーバの起動方法とアドレス取得についてはPythonを使ってAndroid端末を5分でリモートカメラにする方法で書いたのでそちらを参考にして欲しい。

今回の電子掲示板システムはPythonを使って即席で作ったこともあってエラー処理などを入れずに30行ちょいのシンプルな作りになっている。sqlite3モジュールによるSQLiteデータベースで記事を管理し、wsgiref.simple_serverモジュールを使ってウェブサーバ構築した。簡単だ。ただ、Android独自の機能は使っていないのでAndroid端末専用というわけではないけど。Android独自の機能を入れるとしたら、たとえばTwitterなどの投稿者の位置情報表示に対抗して、投稿者ではなくサーバの位置、さらに向きや速度も一緒に表示されるようにするとか。誰得な機能だけど。

以下にソースコードを示す。

android_bbs.py

# -*- coding: utf-8 -*- import cgi,sqlite3,datetime from wsgiref.simple_server import make_server LIMIT=50 # 最大表示記事数. DB_FILE='/sdcard/bbs.sqlite' con=sqlite3.connect(DB_FILE) cur=con.cursor() cur.execute('CREATE TABLE IF NOT EXISTS bbs (id INTEGER NOT NULL PRIMARY KEY AUTOINCREMENT, user TEXT, datetime TEXT, data TEXT)') INSERT_DB='INSERT INTO bbs VALUES(NULL,?,?,?)' def post(user,data): if data=='': return if user=='': user='匿名' dt=datetime.datetime.today().strftime('%Y-%m-%d %H:%M:%S') cur.execute(INSERT_DB,(cgi.escape(user.decode('utf-8')),dt,cgi.escape(data.decode('utf-8')).replace('\n','<br />'))) con.commit() def bbs(environ,start_response): if environ['PATH_INFO']=='/': if environ['REQUEST_METHOD']=='POST': fs=cgi.FieldStorage(fp=environ['wsgi.input'],environ=environ,keep_blank_values=1) post(fs.getfirst('user','').strip(),fs.getfirst('data','').strip()) data=u'<html><head><title>BBS by Android</title></head><body><form action="/" method="post"><div><textarea name="data" cols="40" rows="5"></textarea></div><span>名前:<input type="text" name="user" size="20" maxlength="30" /></span> <span><input type="submit" name="submit" value="送信" /></span> <span><input type="button" value="更新" onclick="location.reload(true);" /></span></form>' cur.execute('SELECT * FROM bbs ORDER BY id DESC') for i, row in enumerate(cur): if i>=LIMIT: break data+=('<div><p>%d <b>%s</b> %s</p><p>%s</p></div>' % row) data+='</body></html>' start_response('200 OK',[('Content-type','text/html;charset=utf-8')]) return [data.encode('utf-8')] httpd=make_server('',8080,bbs) httpd.serve_forever()

Pythonを使ってAndroid端末を5分でリモートカメラにする方法

2010-09-14T01:54:00.005+09:00

Android端末をリモートカメラにしてしまう方法「Spycam」という記事経由でTurn your Android Phone Into a Remote Spy Camera with Ruby in 15 Minutesを知った。SL4AのJRubyを使ってAndroid端末を15分で遠隔操作のスパイカメラにしてしまえるらしい。これは面白い。そこで、Rubyが15分ならPythonを使って5分でリモートカメラにしてしまおうと思い立った。

まず、Pythonでは標準モジュールのSimpleHTTPServerやwsgiref.simple_serverを使って簡単にWebサーバを構築することができる。そしてSL4Aを使えばAndroid端末をそのままサーバとして起動させることができる。これを組み合わせればできたも同然だ。

それで書いたのが以下のコードだ。10行そこそこでAndroid端末をWebサーバに仕立て上げ、Webブラウザ経由で写真を撮ることができる。こんなちっこい端末がWebサーバになるなんて世の中進歩したものだ。

remote_camera.py

import android from wsgiref.simple_server import make_server droid=android.Android() pic='/sdcard/snapshot.jpg' def camera(env,res): if env['PATH_INFO']=='/': droid.cameraCapturePicture(pic) res('200 OK',[('Content-type','image/jpeg')]) return [file(pic).read()] httpd=make_server('',9998,camera) httpd.serve_forever()

使い方は次の通り。まず、SL4Aを起動し、メニューボタンから"View"を選ぶとダイアログが出てくるので"Interpreters"を選択する。

再度、メニューボタンから今度は"Start Server"、"Public"を選択する。これでAndroid端末がサーバとして機能する。

次に、Android画面上部のインジケータ部分を開き、"SL4A Service"をタップする。そうするとScript Monitorが立ち上がるので、Serverのアドレスを確認する。それから先ほど作成したPythonスクリプト(remote_camera.py)を起動する。

サーバのアドレスの最後にソースコードで指定したポート(上記のコードでは9998)を加えたURLをWebブラウザに入力する。例えばサーバのアドレスが your.address.net だとすれば、 http://your.address.net:9998/ がWebブラウザに入力するURLとなる。これで遠隔操作による撮影が可能になった。ページをリロードすればその度に写真が撮影され表示される。試しに最近購入した書籍などを撮影。

これを使って次のような遊びをしてみた。Android端末を見つかりにくいところに隠し、あとでWebブラウザから写真を撮る。その画像とかすかに聞こえるシャッター音を頼りに隠したAndroid端末を探すというゲームだ。子供たち相手にやってみたが皆大喜びだった。もっと広い場所でやれば本当に楽しそうだ。必要なものはAndroid端末とWebブラウザの使えるデバイスだけだ。デバイスもPCではなくAndroid端末のようなスマートフォンで良いのだから手軽だ。

これは使い方の一例だが、Android端末とSL4Aを使えば可能性が本当に広がってくる。

Android端末で青空プログラミング! SL4Aの導入からアプリケーションの作成・公開まで

2010-09-13T04:32:00.014+09:00

以前、Android上でPython、Lua、JavaScriptなどを実行するスクリプティング環境ASE (Android Script Environment)について記事にした。現在ASEはSL4A (Scripting Layer for Android)に変更され、機能がさらに進化している。APIの充実やインターフェイスの改良、スクリプト環境は独立になり、HTMLインタプリタ導入やAndroidパッケージ(APK)の作成などもできるようになった。そこで改めてSL4Aのインストール方法、使い方、Pythonによるアプリケーションの作成、QRコードによるソースコードの公開方法などを紹介する。

導入

まず、SL4Aの公式サイトで最新版のSL4Aをダウンロードする。現時点ではsl4a-r2.apkだが、頻繁に更新されるので注意すること。さらに必要なスクリプト環境をダウンロードする。BeanShell, JRuby, Lua, Perl, Python, Rhino (JavaScript)などがあるが、ここではPythonを選んだ。現時点での最新版はpython_for_android_r1.apkになる。SL4Aとスクリプト環境は独立しているのでそれぞれをインストールする。

これらのAndroidパッケージは公式のものではないので、ダウンロード後インストールするためには、Android端末の設定で「アプリケーション」の「提供元不明のアプリ」にチェックを入れておく必要がある。

これでSL4AでPythonを使用するための準備は整った。

スクリプトの作成

SL4Aをインストールすると左のようなアイコンが出てくるのでそれをタップして起動する。Pythonスクリプトファイルの作成するには、メニューボタンから"Add"を選択し(スクリーンショット左側)、表示されるダイアログから"Python"を選ぶ(スクリーショット左から2番目)。そうすると、Pythonスクリプトの雛形を伴った編集画面になるので(スクリーンショット中央)、それを更新して作成する(スクリーンショット右から2番目)。ファイル名は自由に付けることができ、作成したスクリプトファイルは"Save & Run"ですぐに起動できる(スクリーンショット右側)。編集画面時のメニューボタンから"API Browser"を選択するとAPI一覧が表示される。これはコードを書く上で非常に役に立つ。

さて、ここで実際にアプリを作ってみる。しばらく前にPythonワンライナーで数独ソルバを作成したのでそれをAndroidアプリとして作り替えてみた。ワンライナーではプログラム中に問題を埋め込んでいたが、Androidではそれダイアログから入力するように変えた。入力時に電話のテンキーにすれば素早く片手で入力できるようになるが、HT-03Aではなぜか全角文字になってしまったのでそれをASCII文字に変換するテーブルも追加した。さらに、ワンライナーのようなコンソールへの出力ではバックグラウンドでの動作ができないので、ダイアログで表示させるように変更した。作成したのが以下のスクリプトだ。

sudoku_solver.py

# -*- coding: utf-8 -*- import sys,android droid=android.Android() L=[] def S(D): if 0 in D: L.append(D.index(0)) A=D[L[-1]//9*9:L[-1]//9*9+9] B=D[L[-1]%9:81:9] C=[d for n in(0,1,2)for d in D[L[-1]//27*27+L[-1]%9//3*3+n*9:L[-1]//27*27+L[-1]%9//3*3+n*9+3]] for i in set(range(1,10))-set(A+B+C): D[L[-1]]=i S(D) D[L.pop()]=0 else: M=''.join(['%d'%d+('\n' if i%9==8 else ' ')for i,d in enumerate(D)]).rstrip() droid.dialogCreateAlert(u'解答',M) droid.dialogShow() sys.exit() T={ord(u'\n'):None,ord(u' '):None,ord(u'＊'):u'0',ord(u'*'):u'0',ord(u'．'):u'0',ord(u'.'):u'0'} for i in range(10): T[ord(u'０')+i]=u'%d'%i P=droid.dialogGetInput(u'数独ソルバ',u'問題を入力してください:').result.strip().translate(T) S(map(int,P))

sudoku_solver.pyを起動するにはファイル一覧からsudoku_solver.pyをタップする。すると以下のような5つのアイコン(左から順に、コンソール上での起動、バックグラウンドでの起動、編集、ファイル名の変更、削除)が現れるのでそのうち左の2つのアイコンのどちらかを選ぶことで起動できる。今回はバックグラウンドで起動した。

起動後、以下のようなダイアログが出てくるので問題となる数独を入力する。空白部分は * もしくは . とする。

以下が入力が完了した状態。ここでOKボタンを押すと解析が開始される。

解析が完了すると以下のような解答が表示される。

スクリプトの共有

これでスクリプトによるAndroidアプリを作成することができた。作成したアプリを別の人にも使ってもらうために公開したい場合はどうすればよいのだろうか。ソースコードをそのまま公開することもできるが、それだと一々Android端末にコピーしなくてはならず、場合によっては打ち込み直すはめになり、面倒だ。そこで、QRコードを使ったスクリプトの共有がある。4,296文字という制限があるが、今回のような短いコードでは十分だ。

QRコードを作成するためにQR Code Generatorを利用する。ここのサイトで"Contents"を"Text"とし、"Text content"に、先頭行をファイル名(上述のスクリプトの場合 sudoku_solver.py )としたスクリプトのソースコードを入れる。"Barcode size"は"L"とする。これで"Generate"ボタンを押せばQRコードが生成される。

次にQRコードからソースファイルに戻す方法だが、Android端末でSL4Aを起動し、メニューボタンから"Add"を選ぶ。表示されるリストから"Scan Barcode"でQRコードを読み込むだけだ。ただし、Android 1.6以前ではバーコードスキャナーが入っていないので、Android MarketからZXingのQRコードスキャナー(無料)をインストールしておくこと。

これで簡単にコードを共有することができた。因みにこの記事の先頭に表示しているQRコードは今回作成した数独ソルバのソースコードになっている。

***

まだドラフト段階だがAndroidパッケージ(APK)の作成も可能だし、前回ではPCからadbによるコマンドラインでの操作を取り上げたが、いずれもPCとAndroid端末を繋いでの操作になり青空プログラミングという今回の趣旨から外れてしまうし、一回で説明するには記事が長くなってしまうので今回は割愛することにした。それらについては別の機会に書くかもしれない。

アルゴリズムの素晴らしさに気付かせてくれたのはエラトステネスの篩だった

2010-09-07T01:59:00.006+09:00

Haskellによるエラトステネスの篩(sieve of Eratosthenes)の美しい実装を見て、初めてアルゴリズムの素晴らしさに気付かせてくれたのがエラトステネスの篩だったことを思い出した。たしか中学生の頃だ。そこで、当時を懐かしみながら簡単な実装を書き留めておくことにした。とりあえず、Haskell, C++, Pythonの実装を以下に示す。コードは比較的短いが、実行効率を優先させているわけではない。

Haskell

これはHaskellのサンプルコードでよく出てくる無限リストと遅延評価による実装だが、とても分かりやすいし、美しいコードだと思う。

primes = sieve [2..] sieve (p:xs) = p : sieve [x | x <- xs, x `mod` p /= 0]

以下のように関数takeを使って必要な分だけ素数を取り出すことができる。ただし、実行効率はあまり良くない。

take 10 primes [2,3,5,7,11,13,17,19,23,29]

C++

次にC++を使って実装してみた。ここではC++0xを使っている。そのほうが簡潔で分かりやすく書けるし、これからはC++0xがより使われ、普及して欲しいという意味もある。因みにgccではバージョン4.5以降、Intelコンパイラではバージョン11.0以降、Visual C++では2010(16.0)以降でコンパイルできる。

std::vector<int> primes; for (int i = 3; i < 100; i += 2) primes.push_back(i); auto end = primes.end(); for (auto x = primes.begin(); *x * *x <= *(end-1); ++x) end = std::remove_if(x + 1, end, [&x](int p){ return p % *x == 0; }); primes.erase(end, primes.end()); for (auto p = primes.begin(); p != primes.end(); ++p) std::cout << *p << " "; std::cout << std::endl;

上記のコードでは3から100までの素数を表示する。ノートPC (Core 2 Duo T9800 2.93 GHz / Visual Studio 2010)を使って1000万までの素数を生成してファイルに書き出すのにかかった時間は約2秒だった。

そういえば以前にC++のテンプレートで素数を求めたことがあったな。エラトステネスの篩ではなかったけど。

Python

最後にPythonによる実装を示す。効率はあまり良くないかも。

primes = range(3, 100, 2) for i in range(len(primes)): if primes[i]**2 > primes[-1]: break primes[i+1:] = filter(lambda p: p % primes[i] != 0, primes[i+1:]) print primes

これをそのままワンライナーに。

python -c "import sys;globals().__setitem__('P',range(3,100,2));[P.__setslice__(i+1,len(P),filter(lambda p:p%P[i]!=0,P[i+1:]))for i in range(len(P))if i<len(P)and P[i]**2<=P[-1]];[sys.stdout.write('%d '%p)for p in P]"

上記のコードではそれぞれ、赤字の数値が求める素数の上限値となっている。

Pythonワンライナーで数独を解いてみた

2010-08-23T22:20:00.002+09:00

GIGAZINEに数学のエキスパートが3ヶ月かけて作成した「世界一難しい数独」なるものがあったので、即席でPythonワンライナー(一行プログラム)を作ったら1秒かからず解けた。問題を作るのは大変でも解析プログラムで一瞬とは儚い。

python -c "import sys;L=[];S=lambda D:(0in D)and[L.append(D.index(0)),[(D.__setitem__(L[-1],i),S(D),D.__setitem__(L.pop(),0))for i in set(range(1,10))-set(D[L[-1]/9*9:L[-1]/9*9+9]+D[L[-1]%9:81:9]+[d for n in(0,1,2)for d in D[L[-1]/27*27+L[-1]%9/3*3+n*9:L[-1]/27*27+L[-1]%9/3*3+n*9+3]])]]or([sys.stdout.write('%d'%d+('\n'if i%9==8 else' '))for i,d in enumerate(D)],sys.exit());S([int(c)if c!='.'else 0for c in'..53.....8......2..7..1.5..4....53...1..7...6..32...8..6.5....9..4....3......97..'])"

コードの最後のリスト内の文字列が9行9列の数独の問題となっていて、上の行の数字から順に入っている。未知の部分はドット(.)で表している。上記のコードではGIGAZINEの問題となっている。

因みにPythonによるもっと効率の良いアルゴリズムについてはSolving Every Sudoku Puzzleが参考になるかも。

以下、ワンライナーによる出力結果。

1 4 5 3 2 7 6 9 8 8 3 9 6 5 4 1 2 7 6 7 2 9 1 8 5 4 3 4 9 6 1 8 5 3 7 2 2 1 8 4 7 3 9 5 6 7 5 3 2 9 6 4 8 1 3 6 7 5 4 2 8 1 9 9 8 4 7 6 1 2 3 5 5 2 1 8 3 9 7 6 4

日本全国ハンバーガーショップ分布地図

2010-07-21T00:25:00.023+09:00

以前、Processingを使って日本全国のコンビニ店舗の分布地図を作成したが、今回はハンバーガーショップの分布地図を作成してみた。

個人的にハンバーガーショップには小さい頃から思い入れがあって、小学生の頃、初めてマクドナルドのハンバーガーを食べたときに「なんて美味しいんだろう」と感動した覚えがある。しかし、今でこそ安価な食べ物という認識だが、当時は他の食べ物に比べて割高であまり頻繁に食べられなかった。

その後はだんだんとハンバーガーから離れていったが、モスバーガーと出会ったときに二度目の感動を覚えた。冷たくてジューシーな野菜と熱々のハンバーグが絶妙にマッチしてそれまで食べたことのないハンバーガーだった。少々食べにくくはあったが、逆にそれが溢れる美味しさを表現していたようにも思う。

最近気に入っているハンバーガーは、アトレヴィ秋葉原2階にあるChelsea Marketのアボガドバーガーだ。少々値は張るが、普通のチェーン店に比べて味は飛び抜けていると思う。チェーン店ではないハンバーガー専門店なら他にも美味しいハンバーガーがいろいろとありそう。

閑話休題。以下に作成したプログラムを示す。

This browser does not have a Java Plug-in.
Get the latest Java Plug-in here.

左上の店名をクリック: 分布の表示・非表示を切り替える。起動時はマクドナルドのみ表示。右クリックしたままマウス移動: 地図を平行移動する。左クリックしたままマウス上下移動: 地図を拡大・縮小する。

プログラムの作成方法は前回のコンビニ店舗分布地図を作成した方法とほとんど変わらない。まず、住所をネットから取得する。それをGoogle Maps APIで緯度経度変換し、さらにPythonスクリプトでUTM図法に合わせてXY座標変換する。そのデータをtar/gzipでアーカイブし、Processingを使って読み込み、日本地図に表示する。ブログへの貼り付けはProcessingでJavaアプレットにエクスポートできるのでそれを使う。

今回の分布地図を見て、マクドナルドよりもかなり後に出てきたモスバーガーの店舗が思ったより多く、全国的に展開していて驚いた。また、子供の頃に食べた森永LOVEは既に存在せずロッテリアに買収されたことも今回作成する過程で知った。他には東京に最近出現してきたバーガーキングや沖縄のみに存在するA&Wがやや気になった。沖縄のA&Wへは簡単には行けないが、バーガーキングは今度行ってみよう。

住所データさえあればコンビニ店舗やハンバーガーショップに限らずどんな分布地図でも作れることだし、何か面白い題材ないかな。

以下、ソースコード。

fastfood.pde

String shopData = "convert_xy.tsv.gz"; String japanMap = "japan.svg"; PShape mapShape; int totalCount; Place[] places; int placeCount = 0; final float minX = -0.19834; final float maxX = 0.2425; final float minY = -0.1875; final float maxY = 0.1845; PImage mapImage; PFont font; float offset_x = 0.0; float offset_y = 0.0; int center_x = 0; int center_y = 0; float zoom = 1.0; int mx_start, my_start, my_pos; String[] shopName = { "McDonald", "MOS", "Lotteria", "Freshness", "First Kitchen", "DOMDOM", "Burger King", "A&W", "Becker's" }; color[] shopColor = { #ff0000, #007fff, #00ff00, #ffff00, #ff00ff, #00ffff, #7f0000, #0000ff, #007f00 }; boolean[] shopIds = { true, false, false, false, false, false, false, false, false }; int numShops = 9; public void setup() { mapShape = loadShape(japanMap); smooth(); loop(); size(int(mapShape.width), int(mapShape.height), JAVA2D); // 539, 563 shapeMode(CORNER); mapShape.disableStyle(); font = loadFont("CourierNewPSMT-14.vlw"); textMode(SCREEN); textFont(font); readData(); } public void draw() { background(0); noStroke(); fill(32); shape(mapShape, int(offset_x * zoom) + center_x, int(offset_y * zoom) + center_y); for (int i = 0; i < placeCount; i++) places[i].draw(); for (int i = 0; i < numShops; i++) { fill(shopColor[i]); text(shopName[i], 15, 15 * (i + 1)); if (shopIds[i]) text("*", 5, 15 * (i + 1)); } } float TX(float x) { float offset = width * (1.0 - zoom) * 0.5; return map(x, minX, maxX, offset, width - offset); } float TY(float y) { float offset = height * (1.0 - zoom) * 0.5; return map(y, minY, maxY, height - offset, offset); } void mousePressed() { mx_start = int(mouseX - offset_x * zoom); my_start = int(mouseY - offset_y * zoom); loop(); for (int i = 0; i < numShops; i++) if (mouseX < shopName[i].length() * 8 + 15 && mouseY > 15 * i && mouseY < 15 * (i + 1)) shopIds[i] = !shopIds[i]; my_pos = mouseY; } void mouseReleased() { noLoop(); } void mouseDragged() { if (mouseButton == LEFT) { offset_x = (mouseX - mx_start) / zoom; offset_y = (mouseY - my_start) / zoom; } else if (mouseButton == RIGHT) { if (mouseY - my_pos > 4) { float zoom_out = 9.8 / 10.0; mapShape.scale(zoom_out); zoom *= zoom_out; center_x = int(width * (1.0 - zoom) * 0.5); center_y = int(height * (1.0 - zoom) * 0.5); my_pos = mouseY; } else if (mouseY - my_pos < -4) { float zoom_in = 10.0 / 9.8; mapShape.scale(zoom_in); zoom *= zoom_in; center_x = int(width * (1.0 - zoom) * 0.5); center_y = int(height * (1.0 - zoom) * 0.5); my_pos = mouseY; } } } void readData() { new Slurper(); } Place parsePlace(String line) { String pieces[] = split(line, '\t'); int id = int(pieces[0]); String name = pieces[1]; float x = float(pieces[2]); float y = float(pieces[3]); return new Place(id, name, x, y); }

Place.pde

class Place { int id; String name; float x, y; public Place(int id, String name, float x, float y) { this.id = id; this.name = name; this.x = x; this.y = y; } public void draw() { if (shopIds[this.id]) { int xx = (int)TX(this.x) + int(offset_x * zoom); int yy = (int)TY(this.y) + int(offset_y * zoom); set(xx, yy, shopColor[this.id]); } } }

Slurper.pde

class Slurper implements Runnable { Slurper() { Thread thread = new Thread(this); thread.start(); } public void run() { try { BufferedReader reader = createReader(shopData); String line = reader.readLine(); totalCount = int(line); places = new Place[totalCount]; while ((line = reader.readLine()) != null) { places[placeCount] = parsePlace(line); placeCount++; } } catch (IOException e) { e.printStackTrace(); } noLoop(); } }

2次元セルオートマトンとエントロピー

2010-07-13T22:36:00.012+09:00

2状態の2次元セルオートマトン(Cellular Automaton)をActionScript 3.0 (AS3)で作ってみた。2次元セルオートマトンで最も有名なのはライフゲーム(Conway's Game of Life)だろう。プログラムでは初期ルールをライフゲームとしている。初めにC++で書こうと思ったのだけど、Web上でグラフィカルに操作できないとつまらないと思い、AS3でFlashとして作成しwonderflに登録することにした。ついでに時間的なエントロピー変化を視覚的に認識できたら面白そうだと思ったので、それについても実装した。

今回、セルオートマトンのコードを書こうと思ったのはTCO Marathon Round 2の問題として出されたからだ。2次元セルオートマトンのサイズと初期配置、それにルールが与えられ、指定した世代で生存セルが最大になるように初期配置を変更しろという問題だ。そして、問題を解くために色々と調べているうちにセルオートマトンが面白く感じられたのでブログ記事にしてみた。とは言っても今回のコードはコンテストのような特別なチューンなどはしていない。ビット配列や剰余テーブルなどは使っているがどちらかというと読みやすさを優先させている。

作成したプログラムを以下に示す。

Cellular Automaton - wonderfl build flash online

1-9 : ルール設定 - セルの周りの生存セル数(0-8)に対応 : '.' 死亡, '&' 変化, '+' 誕生, '=' 維持 SPACE : 一時停止 ENTER : リセット V : メッセージ表示/非表示 Z : 初期生存セルの割合を減少 X : 初期生存セルの割合を増加

最初に実行されるルールはライフゲームだ。つまり、セルの回りに2つの生存セルがあった場合、そのセルは現状「維持」となり、3つの生存セルがあればそこに生存セルが「誕生」する。生存セルが1つ以下か4つ以上の場合は死亡セルとなる。また、上端と下端、右端と左端は繋がっていて周期境界条件となっている。現在のルール設定はFlash画面の左下に[..=+.....]と表示される。[]内の9つの文字はそれぞれ左から順に、セルの回りに生存セルがない場合、1つある場合、2つある場合、…周りがすべて生存セル(8つ)の場合を表していて、. は「死亡」(死亡セルとなる)、+ は「誕生」(生存セルとなる)、= は「維持」(現在のセルのまま)、& は「変化」(死亡セルであれば生存セルとなり、生存セルであれば死亡セルとなる)となっている。ルールの変更はキーボードの1～9キーに対応しており、キーを押す毎に、. → & → + → = と変化していく。

ルールの右隣にある数値は初期状態の生存セルの割合で、その右隣の数値は現在の生存セルの割合を示している。初期状態の生存セルの割合はXキーで増加、Zキーで減少させることができる。また、一番上に書かれているFPSは1秒間に表示されるフレーム数を示し、Nは現在の生存セル数、Hはエントロピーを示す。

ここでエントロピーについての説明をしておく。時間的なエントロピーHについては下記の情報エントロピーの式を用いた。

1世代におけるセルの変化は0→0、0→1、1→0、1→1の4通りあり、それらの確率P^kからエントロピーを求めている。またlogの底を4とすることでHを0～1にスケールしている(参考: 2次元セルオートマトンの相転移と結晶化)。

表示されるセルの色は生存セル数が多いほど赤く、少ないほど青く表示される。また、背景色はエントロピーに比例しており、エントロピーが高いほど明るい緑となり、低いほど暗くなる。

以下にいくつかのルールによる変化を例示する。

ルール [..=+.....] / 初期生存セルの割合 0.3

これはライフゲームのルールであり、初期生存セル数の割合は0.3としている。最初は生存セル数が多くエントロピーが高いので背景は比較的明るい緑となっているが、徐々に生存セル数およびエントロピーが減ってきて暗くなってきている。5万ほどいた生存セルも1万を切るぐらいに減ってしまい、活動しているセルも縮小していることが分かる。

ルール [..=++....] / 初期生存セルの割合 0.9

これはライフゲームのルールに周りが4つのセルで「誕生」するルールを加えたものだ。初期生存セル数の割合を0.9と高くして最初にほとんどのセルを死滅させている(周りの生存セル数が高いと次の世代で「死亡」するため)。これにより非常に少ない生存セルから始めることができる。このルールではほんの僅かに残った生存セルからでも驚異的な再生力を示し、最終的にはすべてに生存セルが生息し、エントロピーは0.98以上と非常に高い値を示す。

ルール [..=+====.] / 初期生存セルの割合 0.1

これは現状維持の性質を非常に強く持ったルールで、初期生存セル数の割合を0.1から始めるとスピードは遅いが侵食するように生存セルが繁殖していき、最終的には全体の75%ほどを生存セルで占める。動きはほとんど見られないのでエントロピーは0.4ほどであるが、生存セル数が多いので画面は赤くなる。

この他にも[..+=.....] 0.9、[..=+=....] 0.9、[..=+&....] 0.9なども面白いので試してみて欲しい。セルの繁殖する様は、実際の細胞増殖を顕微鏡で眺めているかのようであり、とても興味深い。

小学3年生の授業参観でアルゴリズムに出会った

2010-06-14T01:19:00.003+09:00

小学3年生の娘の日曜授業参観に行ってきた。算数の授業だ。授業の後半、以下のような問題が出された。

問題: ゴマダラチョウとトノサマバッタがあるゲームをしている。0から9までの数字の書かれたカードがそれぞれ一枚ずつ全部で10枚あって、それを使って3桁の数を2つ作り、その差をできるだけ小さくした方が勝ちとなるゲームだ。ただし百の位は0にできない。できるだけ小さくするにはどのようにカードを選べばよいだろうか。

これを約30人の生徒に考えさせていた。解き方を先に教えるということはしない。生徒が問題を考えている間、先生は生徒たちを見回り、質問などに答える。しばらくするといろいろと答えが挙がってきた。自分の娘は以下のように考えたようだ。

百の位は差が1であればどの数字でも良いので、まず十の位を最小にする数字を考えてみると、最小の数字0から最大の数字9を引いた場合が最も小さくなる。同様に一の位では0と9以外の最小・最大の数字を選ぶ。つまり1から8を引いた場合が最小になる。百の位は残りの数字カードから差が1となるものを選ぶ。解答例は「501-498」や「701-698」となり、差は3になる。

これはまさにアルゴリズムだ。Pythonであれば以下のコードと同じだろう。

digits = range(10) ten = (digits.pop(), digits.pop(0)) one = (digits.pop(), digits.pop(0)) idx = random.randrange(len(digits) - 1) hund = (digits.pop(idx), digits.pop(idx)) a = reduce(lambda x, y: x * 10 + y, map(array, (hund, ten, one))) print "%d - %d = %d" % (a[1], a[0], a[1] - a[0])

出力例:

601 - 598 = 3

小学3年生の算数だと思ってそれほど期待せずに観に行ったのだが、生徒たちはみな楽しそうに問題に取り組んでいたし、なかなか面白い授業をしているようで何だか安心した。因みに、今回のようなクラス全員で考える問題は普段からよく行っているとのことだった。

スーパーコンピュータとプログラミング言語

2010-06-03T01:37:00.003+09:00

世の中には星の数ほどのプログラミング言語があるかもしれないが、スーパーコンピュータで利用するとなるとかなり限られてくる。ライフサイエンス分野のデータの処理にはPython、Ruby、Perlなどのいわゆるスクリプト言語はよく使われるし、データベース関連だとJavaなどもあるだろう。しかし科学技術計算に限れば、FortranやC/C++が多数を占めると思う。やはり実行効率と既存資産の存在は大きい。

数値計算プログラムでは、とにかく速さが求められる。どれだけの速さがあれば十分かだって? この質問はナンセンスだと思う。たとえ現在の最高速度を誇るスーパーコンピュータの1億倍の速度があったとしても十分ではない。使える資源でできる範囲の計算をするだけなのだから。

自分の携わる分野では一回の計算に半年かかることもざらなので、計算速度は死活問題だ。1分で終わる処理なら倍に高速化したとしても差は30秒でしかない。しかし、半年となるとその差は3ヶ月にもなる。だから、Fortranを使うにしても、よりモダンなFortran90/95だけではなく、古めかしいが実行速度の速いFORTRAN77もよく使われる。まあ、最近は速度差も縮まってきているのでそこまでFORTRAN77にこだわらなくなってきているけど。本当にクリティカルな部分にはアセンブリ言語なども使われている。

また、汎用コンピュータのコンパイラに比べてスーパーコンピュータに最適化されたコンパイラではバグの入っていることが多く、C++でもBoostなどの外部ライブラリは避けた方が無難だ。使うにしてもGoogleのC++コーディング規約のように一部に限定して使う方が良い。実際にBoost絡みのコンパイラバグによる混乱を見るに、STLなどの標準ライブラリのみをシンプルに利用していた方がまだ安全だ(それでもバグるけど)。そうは言ってもBoostは便利なのでできるだけ早くC++0xの標準化がされてほしい。標準化されていればコンパイラベンダも言い訳できないしね。

そういえばFortressなんて言語もあるね。面白い試みではあるけれど現状で利用するのは難しいような気がするなぁ。特に冒頭でも述べた、Fortranと同程度の実行効率が出せるかという点と既存資産の代替が存在するのかという点で。因みにFortressでの"Hello, World!"は以下のように書くみたい。

hello.fss

component hello export Executable run() = println("Hello, World!") end

OAuthを使ってAndroidからPythonでTwitterに投稿する

2010-05-16T01:23:00.010+09:00

以前、ASE (Android Scripting Environment)を使って「AndroidからPythonでTwitterに投稿する」という記事を書いたが、来月末にTwitterのBASIC認証が廃止されるので使えなくなる。そこで、OAuthを利用するコードに書き直してみた。最近はAndroidのtwiccaがとても使いやすいのでPythonスクリプトによるTwitterへの投稿もあまりないかもしれないが、Android端末単体でOAuthを利用したTwitterの認証ができることを示す意味でも公開することにした。

まず、「コマンドラインで動作するOAuth対応TwitterクライアントをPythonで作ってみた」という記事で用意したoauth.pyとoauthtwitter.pyをAndroid機の/sdcard/ase/scripts/ディレクトリにコピーする。これはadb pushでコピーしてもいいし、SDカードに直接コピーしてもいい。oauthtwitter.pyは一部修正してあるので上述記事の該当箇所を参照して書き直して欲しい。

次に、それらのライブラリを利用して以下のようなコードを書いた。赤字で示した認証コードの部分はTwitterのサイトのOAuthクライアント登録で取得する必要がある。

tw_oauth_ase.py

#!/usr/bin/env python # -*- coding: utf-8 -*- import os, pickle, time, android from oauthtwitter import * CONSUMER_KEY = "CONSUMER_KEY" CONSUMER_SECRET = "CONSUMER_SECRET" KEY_FILE = "/sdcard/ase/scripts/twitter_key.dat" droid = android.Android() def twitter(): if os.path.isfile(KEY_FILE): access_token = pickle.load(file(KEY_FILE)) else: tw = OAuthApi(CONSUMER_KEY, CONSUMER_SECRET) request_token = tw.getRequestToken() authorization_url = tw.getAuthorizationURL(request_token) droid.view(authorization_url) tw = OAuthApi(CONSUMER_KEY, CONSUMER_SECRET, request_token) time.sleep(60) oauth_verifier = droid.getInput(u"What is the PIN?", u"暗証番号を入力してください")["result"].strip() access_token = tw.getAccessTokenWithPin(oauth_verifier) pickle.dump(access_token, file(KEY_FILE, "w")) return OAuthApi(CONSUMER_KEY, CONSUMER_SECRET, access_token) def main(): tw = twitter() post = droid.getInput(u"Tweet", u"いまどうしてる?")["result"].strip() if post: tw.PostUpdate(post.encode("utf-8")) droid.makeToast(post) if __name__ == "__main__": main()

使い方は以下の通り。一番最初の起動時だけOAuthによる認証をする必要がある。

まずはASEを起動して以下の画面で先に示したtw_oauth_ase.pyを実行する。

実行させると以下のようにブラウザが起動してTwitterのOAuth認証画面が表示される。

「許可する」を選ぶと以下の画面が表示される。

表示された暗証番号をメニューボタンから「テキストを選択してコピー」を選び、番号をコピーする。ここまでの作業を一分以内に完了させる必要がある。ただし、tw_oauth_ase.pyのtime.sleep(60)の数値(秒)を設定することで完了させるまでの時間を変更することができる。

一分後に以下のダイアログボックスが表示されるので、クリップボードにコピーした暗証番号を入力する。クリップボードから入力するにはテキストエリアを長押しすれば良い。

認証作業が完了すると以下のメッセージ入力ダイアログボックスが表示される。

入力したメッセージがAndroid画面に表示され、Twitterに投稿される。次以降の起動時には最初から上記のダイアログボックスが表示され、認証作業の必要はない。

追記(2010/5/16):

twitter.pyは日本語だと140文字の半分ほどでツイートできなくなってしまうので、文字コードをutf-8、len(status)をlen(status.decode("utf-8"))に変更してバイトコンパイル、Android端末の/sdcard/ase/extras/にコピーして使っている。

C++0xでYコンビネータ

2010-05-12T01:06:00.007+09:00

stackoverflow.comのFixed point combinators in C++ (C++による不動点結合子)に載っていたC++とboostで書かれたYコンビネータ(Y combinator)のサンプルコードをC++0xを使って書き直してみた。C++0xだと標準ライブラリだけでこれだけ簡潔に書ける。

#include <iostream> #include <functional> using namespace std; // Y-combinator for the int type function<int(int)> y(function<int(function<int(int)>, int)> f) { return bind(f, bind(&y, f), placeholders::_1); } int main() { // Y-combinator compatible factorial auto fact = [](function<int(int)> f, int v){ return v == 0 ? 1 : v * f(v - 1); }; auto factorial = y(fact); cout << factorial(5) << endl; return 0; }

一行でテキストに含まれるURLをすべて短縮URLに変換するPythonスクリプト

2010-05-06T01:20:00.009+09:00

テキストに含まれるURLをすべてbit.lyの短縮URLに変換するPythonワンライナーを書いた。使用しているモジュールはre、urllib、urllib2、simplejson。コードに一行追加するだけだし、Twitterなどのメッセージを処理するのに便利だと思う。

for link in sorted(re.findall(r"(http(?:s?)\:\/\/(?!bit\.ly[\/\ ])[^\/\ ]+\/?.*?)(?:[\ <>\"\{\}\|\\\^\[\]\`]|$)", msg), reverse=True): msg = (lambda x: re.sub(re.escape(x), (lambda y: str(simplejson.loads(urllib2.urlopen("http://api.bit.ly/shorten?version=2.0.1&longUrl=%s&login=BITLY_ID&apiKey=BITLY_API_KEY" % urllib.quote(y)).read())["results"][y]["shortUrl"]))(x), msg))(link)

bit.lyのAPIキーは別途取得しておく必要がある。

msg = u"ここのブログのURLはhttp://handasse.blogspot.com/ です。記事のURLはhttp://handasse.blogspot.com/2010/05/urlurlpython.html です。"

としてURLを含むメッセージを処理すると以下のように変換される。

print msg ここのブログのURLはhttp://bit.ly/PQa9F です。記事のURLはhttp://bit.ly/cVRVu6 です。

上記のコードを展開したものが以下のコード。簡単なエラー処理を追加してある。

def bitly(x): try: data = urllib2.urlopen("http://api.bit.ly/shorten?version=2.0.1&longUrl=%s&login=BITLY_ID&apiKey=BITLY_API_KEY" % urllib.quote(x)).read() return str(simplejson.loads(data)["results"][x]["shortUrl"]) except: return x replace_url = lambda x: re.sub(re.escape(x), bitly(x), msg) links = sorted(re.findall(r"(http(?:s?)\:\/\/(?!bit\.ly[\/\ ])[^\/\ ]+\/?.*?)(?:[\ <>\"\{\}\|\\\^\[\]\`]|$)", msg), reverse=True) for link in links: msg = replace_url(link)

コマンドラインで動作するOAuth対応TwitterクライアントをPythonで作ってみた

2010-05-02T00:07:00.007+09:00

6月末にTwitter APIのBASIC認証が終了してしまうので、OAuth対応のTwitterクライアントを作ってみることにした。とりあえず最もシンプルだと思われるコマンドラインで動作するクライアントをPythonで作成してみた。

まず、Twitterクライアントを作成する前に、TwitterのサイトでOAuthクライアントの登録を行わなくてはならない。ここで、「アプリケーーション名」、「アプリケーションの説明」、「アプリケーションのウェブサイトURL」を記入する必要がある。また、今回はPC上で実行するクライアントで読み書きを行いたかったので、「あなたの招待状」には「送信」、"Default Accdess type"には"Read & Write"を選択した。

登録を済ますと、"Application Details"のページで"Consumer key"と"Consumer secret"が与えられるので、これを作成するアプリケーションで利用する(CONSUMER_KEY, CONSUMER_SECRET)。

次にコーディングだが、できるだけ短くシンプルに作りたかったので、Python外部モジュールのtwitter、oauth、oauthtwitterを利用させてもらうことにした。ただ、作者のページのコードでは途中でエラーになってしまうので、 oauthtwitter.pyのOAuthApiクラスのgetAccessTokenメソッドの下に以下のgetAccessTokenWithPinメソッドを追加した。

def getAccessTokenWithPin(self, pin, url=ACCESS_TOKEN_URL): token = self._FetchUrl(url, parameters={"oauth_verifier": pin}, no_cache=True) return oauth.OAuthToken.from_string(token)

今回作成したTwitterクライアントの使い方だが、

tw.py

で最新のタイムラインを表示する。取得件数はここでは20件にしているが、ソースコード中の引数で変更することができる。Twitterへの投稿は以下のようにすれば良い。

tw.py "つぶやき"

最初の起動時に、アクセストークンを取得するための認証URLが表示される。それをブラウザで開いて表示された認証番号(PIN)を入力する必要がある。取得したアクセストークンは指定されたファイル(KEY_FILE)に保存され、次回以降はそのファイルからアクセストークンを取得する。

ソースコードを以下に示す。

tw.py

#!/usr/bin/env python # -*- coding: utf-8 -*- import sys, os, pickle from oauthtwitter import * CONSUMER_KEY = "CONSUMER_KEY" CONSUMER_SECRET = "CONSUMER_SECRET" KEY_FILE = "twitter_key.dat" def twitter(): if os.path.isfile(KEY_FILE): access_token = pickle.load(file(KEY_FILE)) else: tw = OAuthApi(CONSUMER_KEY, CONSUMER_SECRET) request_token = tw.getRequestToken() authorization_url = tw.getAuthorizationURL(request_token) print authorization_url tw = OAuthApi(CONSUMER_KEY, CONSUMER_SECRET, request_token) oauth_verifier = raw_input("What is the PIN? ") access_token = tw.getAccessTokenWithPin(oauth_verifier) pickle.dump(access_token, file(KEY_FILE, "w")) return OAuthApi(CONSUMER_KEY, CONSUMER_SECRET, access_token) def main(args): tw = twitter() if len(args) < 2: for status in tw.GetFriendsTimeline(count=20): print status.GetUser().GetScreenName() + ":", status.GetText().encode("cp932", "replace") else: post = " ".join(args[1:]) tw.PostUpdate(post.decode("cp932").encode("utf-8")) if __name__ == "__main__": main(sys.argv)

Google App EngineとSafe Browsing APIを利用して短縮URLチェッカーを作ってみた

2010-04-29T21:24:00.010+09:00

最近、Twitterやはてなブックマークなどを使うことが多くなり、字数制限付きのコメントを書くことが増えた。コメント中にURLを入れたいこともままあるのだが、長いURLだと字数をオーバーしてしまう。そのため短縮URLを使っているが、コメント内に直接短縮URLを入れるのがやっかいだった。そこで、Google App Engine (GAE)を使ってシンプルで高速な短縮URL変換ツールを作成してみた。

しかし、短縮URLは悪意のあるサイトの判別が難しいという欠点がある。見た目で判断できないので開くのを躊躇してしまう。そこで、今回作成したツールでは、短縮URLに変換するだけではなく、それを元のURLに戻す機能も追加した。さらに、Google Safe Browsing APIを利用してフィッシングサイトなどの悪意あるサイトの判別も試みている。

短縮URLチェッカー

使い方はシンプルで、テキストボックスに変換したいURLを入力すればbit.lyの短縮URLがテキストボックス表示され、bit.lyの短縮URLを入力すればもとのURLが表示される。テキストボックスをクリックすれば表示されているURLが選択されるのでクリップボードへのコピーも簡単だ。テキストボックスの下には展開されたURLがリンク付きで表示されるが、もしフィッシングサイトだと疑われる場合は、以下のように警告してくれる。

さて、今回のコード作成だが、bit.lyによる短縮URLの変換は簡単だった。というのも以前にPythonスクリプトで作ったことがあるからだ。それをそのままGAEに載せればいい。しかし、Safe Browsing APIによる悪意あるサイトの検出は思ったよりも面倒だった。まず、APIの使い方がよく分からない。使う前は任意のURLをAPIで確認するのかと思っていたのだが、そうではなく、MD5でハッシュ化したリストをダウンロードして、調べたいURLをハッシュ化してそれと照らし合わせなくてはならない。今回問題になったのはそのダウンロード容量で、フィッシングサイト用データが700KB程、マルウェア用データが10MBを超えていた。GAEでは一回のダウンロード容量の上限が1MBと決まっており、フィッシングサイト用データは何とかダウンロードできても、マルウェア用データは途中で切れてしまった。仕方がないので今回はフィッシングサイト用のみを使うことにした。ただし現在、Safe Browsing APIの新しいバージョンが開発中であり、それを使えば何とかなるかもしれない。自分がちょっと試したときには何故か新しいAPIが使えなかったので、今回は見送ることにした。気が向いたら試してみるかも。

APIによりダウンロードされるリストはMD5でハッシュ化されているが、ハッシュ化される前のURLは標準化された参照URLだ。そこで、調べるURLについても標準化して参照URLを作成しなくてはならない。あまり時間を掛けたくなかったので、今回は標準化については実装しなかった。参照URLの作成についてはThejaswi Puthraya氏が作成したコードを利用させてもらった。URLの標準化についてはGoogleのサイトにも参考例が載っているので、時間ができたら作ってみたい。

ダウンロードされたリストはデータストアに格納している。ハッシュ化されたURLを個別にデータストアに入れるとデータ数が非常に多くなってしまうので、ハッシュ化リストの先頭の2桁(16進数)をインデックスにし、256分割のデータとして格納した。また、リスト更新中にデータストア上のURLの参照が行われても問題が発生しないように、データモデルを2つ用意して更新は交互に行うことにした。加えて、データストアへのアクセスを減らすためMemcacheを利用している。

フィッシングサイト用リストはcronを使って30分毎に更新している。しかし、リスト更新の際に処理が30秒を超えることがあり、そのため更新に失敗してしまうことがある。これはGAEの制限なのだが、前述のデータ取得の容量制限と合わせて、このあたりが改善されるとより素晴らしくなるのだけどなぁ。無料で使わせてもらっているのに贅沢かもしれないけど。

追記(2010/5/2): リスト更新の半分以上が30秒を超えてエラーになったので、TaskQueueによる処理に変更した。

最後に今回作成したソースコード(実装したクラスのみ)を示しておく。

class Bitly(): def __init__(self): self.apiurl = "http://api.bit.ly/%s?version=2.0.1&%s=%s&login=BITLY_ID&apiKey=BITLY_API_KEY" self.api_index = { "shorten": "longUrl", "expand": "shortUrl" } self.info_index = { "shorten": "shortUrl", "expand": "longUrl" } def is_error(self, url, url_info): return url_info["statusCode"] != "OK" or (url_info["results"][url].has_key("statusCode") and url_info["results"][url]["statusCode"] != "OK") def bitly(self, url, api): url_data = urllib2.urlopen(self.apiurl % (api, self.api_index[api], urllib.quote(url))).read() url_info = simplejson.loads(url_data) if api == "expand": url = url.replace("http://bit.ly/", "") if self.is_error(url, url_info): return "" return url_info["results"][url][self.info_index[api]] def get(self, url): if url.lower().split(":")[0] not in ("http", "https", "ftp"): url = "http://" + url bitly_url = "" if re.match(r"http://bit.ly/", url) and not re.search("[^a-z^A-Z^0-9]", url.replace("http://bit.ly/", "")): self.shorten_url = url bitly_url = self.bitly(url, "expand") self.long_url = bitly_url if not bitly_url: self.long_url = url bitly_url = self.bitly(url, "shorten") self.shorten_url = bitly_url return bitly_url class DataProperty(db.Model): phishing = db.IntegerProperty() malware = db.IntegerProperty() class PhishingDataA(db.Model): index = db.IntegerProperty() hash_urls = db.TextProperty() class PhishingDataB(db.Model): index = db.IntegerProperty() hash_urls = db.TextProperty() class MalwareDataA(db.Model): index = db.IntegerProperty() hash_urls = db.TextProperty() class MalwareDataB(db.Model): index = db.IntegerProperty() hash_urls = db.TextProperty() class ShortUrl(webapp.RequestHandler): def __init__(self): self.html = u"""<?xml version="1.0" encoding="UTF-8"?> <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd"> <html xmlns="http://www.w3.org/1999/xhtml" xml:lang="ja" lang="ja"> <head> <meta http-equiv="content-type" content="text/html; charset=utf-8" /> <meta http-equiv="content-script-type" content="text/javascript" /> <meta http-equiv="content-style-type" content="text/css" /> <link type="text/css" rel="stylesheet" href="/stylesheets/main.css" /> <title>短縮URLチェッカー</title> </head> <body> <form action="/short_url" method="post"> <div>URL: <input type="text" name="content" size="31" maxlength="1024" value="%s" onclick="this.select()" /> <input type="submit" value="変換" /></div> </form> %s <div style="font-size:xx-small;"><p>短縮URLの変換およびフィッシングサイトの判別を行います。[ver.20100502]<br /><a href="http://code.google.com/apis/safebrowsing/safebrowsing_faq.html#whyAdvisory">Advisory provided by Google.</a></p></div> </body> </html>""" def lookup_by_url(self, url): """from http://github.com/theju/safebrowsing-python""" url_re = re.compile("^(([^:/?#]+):)?(//([^/?#]*))?([^?#]*)(\?([^#]*))?(#(.*))?") url = url.lower() url_components = url_re.match(url).groups() lookup_list = set() hostname = url_components[3] hostname_comp = hostname.split(".") if not hostname_comp: raise AttributeError("Invalid URL.") for i in xrange(len(hostname_comp) - 1): filtered_hostname_comp = ".".join(hostname_comp[i:]) lookup_list.add(filtered_hostname_comp + "/") if url_components[4]: path = url_components[4].split('/') for j in xrange(len(path) + 1): filtered_paths = '/'.join(path[:j]) if not '.' in filtered_paths: lookup_list.add(filtered_hostname_comp + "%s/" % filtered_paths) lookup_list.add(filtered_hostname_comp + url_components[4]) if url_components[5]: lookup_list.add(filtered_hostname_comp + ''.join(url_components[4:6])) if url_components[7]: lookup_list.add(filtered_hostname_comp + ''.join(url_components[4:6]) + url_components[7]) return lookup_list def get(self): self.response.out.write(self.html % ("", "")) def post(self): content = self.request.get('content') bitly = Bitly() bitly_url = bitly.get(content) dp = memcache.get("dp") if not dp: dp = DataProperty().all().get() memcache.add("dp", dp) phishing, malware = dp.phishing, dp.malware P = PhishingDataA if phishing == 0 else PhishingDataB M = MalwareDataA if malware == 0 else MalwareDataB urls = self.lookup_by_url(bitly.long_url) hash_urls = [hashlib.md5(x).hexdigest() for x in urls] is_phishing, is_malware = False, False for hash_url in hash_urls: idx = int(hash_url[:2], 16) phishing_list = memcache.get("phishing_%d" % idx) if not phishing_list: phishing_list = P().all().filter("index =", idx).get().hash_urls memcache.add("phishing_%d" % idx, phishing_list) if re.search(hash_url, phishing_list): is_phishing = True """ malware_list = memcache.get("malware_%d" % idx) if not malware_list: malware_list = M().all().filter("index =", idx).get().hash_urls memcache.add("malware_%d" % idx, malware_list) if re.search(hash_url, malware_list): is_malware = True """ link = '<a href="%s">%s</a>' % (bitly.long_url, bitly.long_url) if is_phishing: link += u'<br />フィッシングサイトの疑いがあります。<span style="font-size:xx-small;color:gray;">詳しくは<a href="http://www.antiphishing.org">AntiPhishing.org</a>を参照してください。</span>' if bitly_url: self.response.out.write(self.html % (bitly_url, "<div><p>%s</p></div>" % link)) else: self.response.out.write(self.html % ("", u"<div><p>変換できませんでした。</p></div>")) class SafeBrowsing(webapp.RequestHandler): def __init__(self): self.urls = { "phishing": "http://sb.google.com/safebrowsing/update?client=api&apikey=SAFE_BROWSING_API_KEY&version=goog-black-hash:1:-1", "malware": "http://sb.google.com/safebrowsing/update?client=api&apikey=SAFE_BROWSING_API_KEY&version=goog-malware-hash:1:-1" } def get_data(self, target, selection): idx = 0 txt = "" all_data = urllib2.urlopen(self.urls[target]).read().split() for l in all_data: l = l.strip() if len(l) == 33 and l[0] == '+': current_idx = int(l[1:3], 16) if idx != current_idx: taskqueue.add(url="/short_url/safe_browsing/process", params={"target": target, "selection": selection, "idx": idx, "txt": txt}) txt = "" idx = current_idx txt += l taskqueue.add(url="/short_url/safe_browsing/process", params={"target": target, "selection": selection, "idx": idx, "txt": txt}) def get(self): target = self.request.get("target") if target in ("phishing", "malware"): dp = DataProperty().all().get() if not dp: dp = DataProperty(phishing=0, malware=0) dp.put() dp = dp.all().get() if target == "phishing": selection = abs(dp.phishing - 1) self.get_data(target, selection) dp.phishing = selection else: selection = abs(dp.malware - 1) self.get_data(target, selection) dp.malware = selection self.response.out.write("Done: %s, %d" % (target, selection)) dp.put() memcache.delete("dp") else: self.response.out.write("Incorrect: %s" % target) class SafeBrowsingProcess(webapp.RequestHandler): def __init__(self): self.data = { "phishing": lambda (idx): PhishingDataA if idx == 0 else PhishingDataB, "malware": lambda (idx): MalwareDataA if idx == 0 else MalwareDataB } def post(self): target = self.request.get("target") selection = int(self.request.get("selection")) idx = int(self.request.get("idx")) txt = self.request.get("txt") M = self.data[target](selection) model = M().all().filter("index =", idx).get() if not model: model = M(index=idx, hash_urls="") model.hash_urls = txt model.put() memcache.delete("phishing_%d" % idx)

一つのGoogle App Engineアプリケーションで複数のWaveボットを作成する

2010-04-14T23:24:00.007+09:00

Google App Engine (GAE)では現在10個までのアプリケーションを登録することができる。そして、GAEを利用してGoogle Waveのボットを作成することができる。しかし、多種多様な利用方法が存在するWaveボットをGAEアプリケーションとして登録していてはすぐに上限に達してしまうだろう。そこで、一つのGAEアプリケーションで複数のWaveボットを作成するためのいくつかの方法を利用することになる。サブドメインを利用する方法が一般的だろうか。

しばらく前からサブドメインを利用して複数のWaveボットを作成しようと思っていたのだが、ちょっと面倒に思えて手を付けていなかった。そうしたら、technohippy氏によるappengine_multi_robot_runnerというライブラリが公開され、それがとても便利そうだったので簡単なWaveボットを作成してみた。ただし、Google Wave Robots API v2が3月30日にアップデートされて実装の一部が変更されたことにより、appengine_multi_robot_runner.pyがそのままでは動作しなかったので該当箇所を修正した。それについては最後に記述しておく。

追記(2010/4/15): 現在、appengine_multi_robot_runnerは最新版に更新されているので、後述の修正は必要無くなっている。

作成したのはインチキ日本語ボット(fake-japanese.robotic-wave@appspot.com)とインチキ英語ボット(fake-english.robotic-wave@appspot.com)の二つのWaveボットだ。インチキ日本語ボットでは、書き込んだ日本語を一度Googleにより英語に翻訳し、それを再度日本語に翻訳し直して表示する。インチキ英語ボットは、日本語を英語に翻訳したものを表示する。インチキと書いたが、特にでたらめにするために細工しているわけではない。現在の翻訳技術ではインチキっぽく見えてしまうというだけである。因みに、これらのボットのアイコン画像はAtnet Japan!を利用させてもらった。

どのように動作するか、以下の例文を実際に入力して動作を見てみよう。

「花便り」
「ここ数日は暖かな日が続いていますが、その後いかがお過ごしでしょうか。」
「待ちに待った桜の花もそろそろ咲き始めております。近いうちにお花見にお誘いしようと思っておりますが、ご都合はいかがでしょうか。」

インチキ日本語ボット(fake-japanese.robotic-wave@appspot.com)では以下の通り。

インチキ英語ボット(fake-english.robotic-wave@appspot.com)では以下の通り。

後述のソースコードを見てもらっても分かるように、この程度の内容であれば非常に短いコードで済んでしまう。Waveボットは一般的なネットボットよりもインタラクティブに利用でき、効果も大きいので、このように簡単に作成できることは非常に重要だと思う。簡単に作成できると言えば、technohippy氏によるas-a-robot@appspot.comを利用することで、GAEを意識せずにGoogle Wave上で簡単にWaveボットを作成することができる。

以下にWaveボットのソースコードを示す。

robotic-wave.py

#!/usr/bin/env python # -*- coding: utf-8 -*- """robotic-wave.py by nox, 2010.4.14""" import urllib, urllib2 from waveapi import robot from waveapi import events from waveapi import simplejson import appengine_multi_robot_runner def Translate(text, from_lang, to_lang): url = "http://ajax.googleapis.com/ajax/services/language/translate?v=1.0&q=%s&langpair=%s%%7C%s" % (urllib.quote(text.encode("utf-8")), from_lang, to_lang) data = simplejson.loads(urllib2.urlopen(url).read()) return data["responseData"]["translatedText"] class FakeJapaneseRobot(robot.Robot): def __init__(self): robot.Robot.__init__(self, "FakeJapanese", image_url="http://robotic-wave.appspot.com/assets/edodaikan03i.gif", profile_url="http://robotic-wave.appspot.com/") self.register_handler(events.BlipSubmitted, self.OnBlipSubmitted) def OnBlipSubmitted(self, event, wavelet): blp = event.blip text = blp.text.strip() text = Translate(Translate(text, "ja", "en"), "en", "ja") blp.range(1, len(blp.text)).replace(text.encode("utf-8")) class FakeEnglishRobot(robot.Robot): def __init__(self): robot.Robot.__init__(self, "FakeEnglish", image_url="http://robotic-wave.appspot.com/assets/202aschwarzenegger.gif", profile_url="http://robotic-wave.appspot.com/") self.register_handler(events.BlipSubmitted, self.OnBlipSubmitted) def OnBlipSubmitted(self, event, wavelet): blp = event.blip text = blp.text.strip() text = Translate(text, "ja", "en") blp.range(1, len(blp.text)).replace(text.encode("utf-8")) def main(): appengine_multi_robot_runner.compound_and_run([ ("fake-japanese", FakeJapaneseRobot()), ("fake-english", FakeEnglishRobot()) ]) if __name__ == "__main__": main()

app.yaml

application: robotic-wave version: 1 runtime: python api_version: 1 handlers: - url: /_wave/(.*) script: robotic-wave.py - url: /assets static_dir: assets - url: /(.*) script: index.py

Google Wave Robots API v2が3月30日にアップデートされ実装が一部変更された。そのため、appengine_multi_robot_runner.pyが動作しなくなったのでそれを修正するために加えた変更を以下に示しておく。

変更箇所その1。

class GetHandler(appengine_robot_runner.GetHandler): def __init__(self, method, contenttype): appengine_robot_runner.GetHandler.__init__(self, method, contenttype) def get(self): self.response.headers['Content-Type'] = self._contenttype self.response.out.write(self._method(host=self.request.host))

上記のコードを以下のように変更する。

class CapabilitiesHandler(appengine_robot_runner.CapabilitiesHandler): def __init__(self, method, contenttype): appengine_robot_runner.CapabilitiesHandler.__init__(self, method, contenttype) def get(self): self.response.headers['Content-Type'] = self._contenttype self.response.out.write(self._method(host=self.request.host)) class ProfileHandler(appengine_robot_runner.ProfileHandler): def __init__(self, method, contenttype): appengine_robot_runner.ProfileHandler.__init__(self, method, contenttype) def get(self): self.response.headers['Content-Type'] = self._contenttype if self.request.get('name'): self.response.out.write(self._method(self.request.get('name'), host=self.request.host)) else: self.response.out.write(self._method(host=self.request.host))

変更箇所その2。

([('/_wave/capabilities.xml', lambda: GetHandler(robot.capabilities_xml, 'application/xml')), ('/_wave/robot/profile', lambda: GetHandler(robot.profile_json, 'application/json')),

上記のコードを以下のように変更する。

([('/_wave/capabilities.xml', lambda: CapabilitiesHandler(robot.capabilities_xml, 'application/xml')), ('/_wave/robot/profile', lambda: ProfileHandler(robot.profile_json, 'application/json')),

Android Scripting Environment (ASE) Python API簡易リファレンス

2010-04-06T02:30:00.005+09:00

Android Scripting Environment (ASE)について、「Android上でPython、Lua、JavaScriptなどを実行するスクリプティング環境が凄い」で紹介した。今回はAndroid端末の機能を利用するためのPython APIの使い方をリファレンスとしてまとめてみた。Python 2.6の標準モジュールは最初から利用できる。また、twitterモジュールなど、いくつかの標準外のモジュールがデフォルトでインストールされている。詳細については利用する環境で確認して欲しい。

ASE上のPythonスクリプトの編集画面でメニューボタンを押し、そこから"API Browser"で簡単なリファレンスを読むことができる。また、ASEのWikiとしてWiki pages - android-scripting、サンプルプログラムとしてtest.pyが参考になる。

以下にASE Python APIの簡易リファレンスを示すが、APIのすべてを記しているわけではない。足りない部分については随時追加していく予定だ。

Androidモジュールを使用する

import android droid = android.Android()

現在のクリップボード取得と貼り付け

clip = droid.getClipboard()["result"] droid.setClipboard("Hello, world!")

GDataの使用

import gdata.docs.service client = gdata.docs.service.DocsService() # クライアント. client.ClientLogin(username, password) # 接続. feed = client.GetDocumentListFeed() # ドキュメントリストのAtomをフィード.

GPSで現在の位置情報を取得

droid.startLocating() # 開始. location = droid.readLocation()["result"] lat = location["network"]["latitude"] # 緯度. lng = location["network"]["longitude"] # 経度. droid.stopLocating() # 停止.

位置情報取得などのイベントを受け取るタイプのAPIでは、開始直後にイベントを取得できない場合がある。そこで以下のように数回リトライできるようにする。

for i in range(10): location = droid.readLocation()["result"] if location: break time.sleep(1)

Android端末のセンサー情報を取得

droid.startSensing() # 開始. sensors = droid.readSensors()["result"] droid.stopSensing() # 停止.

センサー情報はディクショナリとして保存されている。

sensors accuracy 精度. azimuth 方位(0-360) pitch 縦の傾き. roll 横の傾き. xforce X方向の加速度. yforce Y方向の加速度. zforce Z方向の加速度. xmag X方向の磁場. ymag Y方向の磁場. zmag Z方向の磁場.

Android端末で音声出力

droid.speak("Hello, world!")

Android端末で音声認識

result = droid.recognizeSpeech()["result"] droid.makeToast(result) # 認識した語句を表示.

指定したURLでウェブブラウザを開く

droid.view("http://www.google.com/")

指定した語句をネット検索

result = droid.recognizeSpeech()["result"] # 音声認識で語句を指定. droid.webSearch(result)

通話状況の取得

droid.startTrackingPhoneState() # 開始. result = droid.readPhoneState()["result"] droid.stopTrackingPhoneState() # 停止.

サイレントモードのトグル

droid.toggleRingerSilentMode()

電話呼び出し音の音量情の取得と変更

vol = droid.getRingerVolume() droid.setRingerVolume(0) # 音量を0にする. droid.setRingerVolume(vol["result"]) # 元に戻す.

最後に取得した位置情報の取得

result = droid.getLastKnownLocation()

ジオコード情報を取得

result = droid.geocode(35.698, 139.774) # 緯度, 経度.

Wi-Fiのトグル

droid.toggleWifiState()

Android端末に文字を表示

droid.makeToast("Hello, world!")

Android端末を振動させる

droid.vibrate()

Android端末にメッセージを送る

droid.notify("Hello, world!")

実行中のAndroidパッケージの取得(com.android.phoneなど)

result = droid.getRunningPackages()

テキスト入力ダイアログの表示

result = droid.getInput("title", "message")["result"]

ボタン付きダイアログの表示

droid.dialogCreateAlert("title", "message") droid.dialogSetPositiveButtonText("Yes") droid.dialogSetNegativeButtonText("No") droid.dialogSetNeutralButtonText("Cancel") droid.dialogShow() response = droid.dialogGetResponse()["result"]

response["which"]には以下の値が入る: Yesボタン: "positive" Noボタン: "negative" Cancelボタン: "neutral"

指定したボタンが1つ(例えばdroid.dialogSetPositiveButtonText("Yes"))なら1つのボタンのみを表示する。

スピナープログレス(回転型進捗アイコン)付きダイアログ

droid.dialogCreateSpinnerProgress("title", "message") droid.dialogShow() time.sleep(2) droid.dialogDismiss()

プログレスバー付きダイアログ

droid.dialogCreateHorizontalProgress("title", "message", 50) # 50分割. droid.dialogShow() for i in range(50): time.sleep(0.1) droid.dialogSetCurrentProgress(i) droid.dialogDismiss()

リスト付きダイアログの表示

droid.dialogCreateAlert("title") droid.dialogSetItems(["foo", "bar", "baz"]) droid.dialogShow() response = droid.dialogGetResponse()["result"]

response["item"]にはリストの順に0からの数値が入る。

追記(2010/6/27):

ASE r22からreadLocation()のデータ構造が変更されたようなので、それに合わせて上述のコードを修正した。

Google Waveを使わないと人生損する

2010-03-16T04:29:00.008+09:00

「Google Waveを使わないと人生損する」…これはちょっと大げさかもしれないが、1年半前に書いたブログ記事「Evernoteを使わないと人生損する」で言及したEvernoteと同じぐらい、Google Waveが重要な技術になると感じたのは本当だ。当初、Google Waveは自分にとって、Google App Engine (GAE)などでプログラミングできる単なるおもちゃだった。しかしながら、今になってやっと、オンラインコラボレーションプラットフォームであるGoogle Waveの潜在能力の高さを知ることになった。

大量のメールに埋もれる情報と予定の立たないミーティング

最近、仕事上のメールのやりとりが頻繁ですぐに流されてしまうことが多く、大事な知らせを失念してしまったり、大量のメールから目的の情報を探し出さなくてはならなくなったりと、メールの扱いに手を焼いていた。さらに、直接顔を合わせるミーティングにおいても、この時期は皆忙しいようで、集まりたいときにすぐに集まれない状況が続き、何かと仕事が滞りがちになっていた。

そこで、昨年にアカウントを取得していたGoogle Waveに目を付けたのだ。今までGoogle Waveを仕事で利用しなかったのは、もともとGAEと連動させてWaveボットなどを開発するのが目的であり、コラボレーションツールとしてはあまり興味を持っていなかったからだ。それに、知人や同僚にもアカウントを持っている人がいなかった。

しかし、メールでのやりとりがひどく非効率に感じられ、必要なときにミーティングもできないというこの状況を打破すべく、Google Waveのアカウントを職場で配ってみることにした。そこでまずは、IT関連の最新技術に明るい同僚に利用してもらい、しばらく一緒に使ってみたのだが、特に問題となるような点もなく、使い勝手もそれほど悪くはなかったので、他のメンバーにもアカウントを配ることにした。

本当に新しいことは理解され難い

Google Waveアカウントを配ったメンバーに早速使ってみてもらったところ、おおむね好評を得られて…というほど甘くはなく、やはり第一印象は「難しい」、「使いづらい」、「メールでいいんじゃないの」という意見だった。誰もGoogle Waveの名前すら聞いたことがないというのだからそれも仕方が無いのだろう。これらの意見については、Google WaveコンプリートガイドによるGoogle Waveの紹介でも全く同じように述べられている。

“Google Wave の最大の欠点は、新しいユーザーが試しに使ってみた場合にあまりに理解しづらくて困惑してしまうことにあるといえます。EasierToUnderstandThanWave.comのようなパロディーサイトでは、炭素年代測定法や新古典派経済学、ポリモーダルな半音階理論といった頭脳を要求する話題でさえ、Wave に比べれば理解しやすいとされています。この冗談が真に迫っているのは、初めて Wave に触れたときにほとんどの人が困惑を経験するといえるからです。あなたがはじめて友人や同僚からうけとる wave は得てして、「なんだこれは」や「これは変なツールだね」といったものになることでしょう。” (Google Waveコンプリートガイドより引用)

そして、難しいと思わせる理由として以下の4つが挙げられている。

「ドキュメントが会話」という前例のない新しいパラダイム
無秩序な木構造の会話、ノンリニアなメッセージスレッド
ドキュメントのバージョン管理
Waveはまだ未完成、足りない機能の存在

確かにもっともな理由ではあるが、それでも使ってもらわないことには何も始まらないので、自分の関わっているプロジェクトのいくつかについてGoogle Waveを使ってもらうことにした。新しいパラダイムは常に受け入れられがたいものだ。

利用して初めて分かること

まず最初にしたことは、メンバーと共同で進めている自分の仕事の連絡をWaveで管理することだった。

今までは自分の担当分の結果が出たら、その報告と結果データの場所(通常はコンピュータ上のディレクトリ)などをメールで知らせていたのだが、そのやりとりが頻繁になると以前の報告やデータを把握しづらくなってくるし、ある仕事の成果を引き継いで別の仕事を行う場合、その対応付けも大変だった。また、別のメンバーが新たに参加する場合、これまでの進捗を説明するのも一苦労だ。

しかし、Waveを利用することによって、それぞれのメンバーの進捗状況は一目でわかるし、仕事のデータも簡単に取り出せる。画像やPDFなどのファイルもドラッグ&ドロップで簡単に共有できる。さらに、ToDoリストとして使うことで、既にメンバーの誰かが完了していた仕事を別のメンバーが繰り返したり、既にあるユーティリティスクリプトを作成してしまうことがなくなった。車輪の再発明の防止だ。加えて、他のメンバーの状況と照らし合わせて、ここまでは急ぎで行わなければならないとか、これはまだ急がなくても良いだろうとかの判断が、簡単にできるようになった。

次に、ある商品の名称を決める打ち合わせを例に挙げてみよう。

まずは、Waveを使わない通常のミーティングの場合、メンバー全員を同じ時間に拘束する必要があり、さらに、その時間内で名称候補を考えつかなくてはならない。しかしそれでは考えつくすべての候補が出る前に時間切れとなってしまうかもしれない。では、時間を決めずに各自に考えてもらってそれを持ち寄るのではどうだろうか。これだと、各個人がバラバラに考えているので、別メンバーのアイデアから触発されることはない。実際に自分の場合、ミーティングやメールでアイデアを募ってみたが、ほとんど反応はなかった。ミーティングでは時間が短すぎたし、メールでは良いアイデアを思いつかないまま別の仕事に追いやられてしまうわけだ。

ではWaveを使った場合はどうだろうか。まずはいくつのかの候補の議論がなされ、それに触発されて他のメンバーからも新たな候補が挙がるようになった。それによりさらにアイデアが浮かんでくる。まさにブレインストーミングだ。しかも、Waveであれば、全員が同じ情報を共有し漏れが無く、時間にも拘束されない。進行のまとめもWave上で編集していけばよいし、何かを決めるときには投票などのガジェットも使える。実際に上記で挙がった候補から最終的な名称を決めるために投票ガジェットは大いに役立った。

どれだけWaveが有用に使えるか、使用する前にすべてを見積もっていた訳ではない。車輪の再発明の防止やアイデアの触発などは、実際に導入して初めて実感できたことだった。頭では分かったつもりでも使ってみるまでは本当に分かったことにはならない。

TwitterとEvernoteで相乗効果

「iPhoneとツイッターで会社は儲かる」(*1)の著者であるEC Studioの山本氏によると、会社のコミュニケーションは電話、チャット、メール、Twitterで成り立っているそうだ。電話はSkypeでもGoogle Voiceもいいし、Twitterの替りにGoogle Buzzを使ってもいいだろう。しかし、チャットとメールはGoogle Waveに置き換えられていくのではないかと感じている。もちろん、すべてのメールとチャットが置き換わるとは思っていないが、多くの部分でWaveが使われるのではないだろうか。

そして、ここで重要になってくるのが、WaveとTwitterとの共存だ。Twitterは今までにないゆるいつながりのコミュニケーションツールとしての立場を確立してる。実際に自分も使っているが、コミュニケーションツールの他に情報収集の手段としてとても有用だ。しかし、Twitterの情報はノイズが多く発散しやすい。最新の情報を肌で感じることができても、それを保存して加工する目的には向いていない。しかし、Waveを使えばそれを補うことができる。例えば、重要だと思われるTwitterの発言があったらそのポインタだけ示しておけば、その情報を共有できる。そして、それが古くなったりただのノイズだと判断したのならそれを捨てればいいだけだ。編集可能なWaveでは、チャットやメールのスパムのように邪魔になったりしない。リアルタイムの今の情報を共有できるのだ。因みに、Wave上でTwitterを動作させるボットもあるし、特定のキーワードでつぶやきを表示させるガジェットもある。

さらに、Google WaveはEvernoteとも非常に相性が良い。というのもGoogle Wave自体が複数人で共有できるEvernoteのようなものだからだ。もともと個人のWebスクラップノートとして利用されているものだからEvernoteを複数人で共有して利用するのは難しいが、Waveを利用することでその弱点を克服できる。

自分の場合、仕事ごとにEvernoteのノートを作って管理している。そして、ある仕事が共同作業であった場合、Waveを作ってそのURLをEvernoteに貼り付けておく。個人的な細々したメモや形になっていないアイデアなどはEvernoteに書いておき、皆で共有する情報はWaveに書く。Waveには他のメンバーも書き込んだり、編集したりするので情報は常に遷移していくのだが、その遷移する情報のすべてを一つのURLだけで保存できる。そして、EvernoteからWaveの情報にアクセスするのはクリック一つだ。これは画期的だ。因みに、Wave上でEvernoteを動作させるガジェットも存在する。

ここで示したように、Google WaveとTwitterとEvernoteを活用することで、とても大きな効果を期待できるだろう。

使用するにあたって

Google Waveの導入について、セキュリティを心配する声を聞く。外部にデータを持つのは不安だという。この点についても問題ない。と言うのも、Waveサーバプロトコルが公開されているからだ。自社サーバでメールサーバを立ち上げるように、Waveサーバを立ち上げることができる。現在はプレビュー版ということもありGoogle以外での実装は見かけないが、将来的には普通に立ち上げることができるだろう。

もっとも、自社でサーバを持つことと、セキュリティが確保できることとは同義ではない。セキュリティを保つためにはそれ相応の技術が必要だ。その点で自社でサーバを管理するよりも、Googleなどのような高い技術を持つ企業に任せた方が安全であるとする見方もある。もし、Gmailなどを仕事で使っているのであれば、Google Waveもそれと同程度にはセキュリティが確保されていると考えられる。

Waveを使用するにあたり、次に問題になるのは、各ユーザが感じる使い勝手だろう。いくら便利だからといって、使い勝手が悪ければ使われない。例えば、SkypeやGmailであればチャットやメールが届いたときにその旨が画面にポップアップして知らせてくれるユーティリティがある。Google WaveにもFirefoxやGoogle Chrome用にブラウザ上で知らせてくれるAdd-onがあるが、それだと常時ブラウザを立ち上げている必要がある。また、新しいWaveが来たときにメールで知らせてくれるオプションもあるが、メールの代わりにWaveを使うという目的からして本末転倒だ。そこで、Google Wave Notifierの使用をお勧めしたい。これを使えば新しいWaveが届いたときにポップアップして通知してくれる。また、Mac OS XやiPhoneならWaveboardというWaveクライアントが利用でき、通知機能もあるようだ。

どちらにしろ現在はまだプレビュー段階であり、リリースまでにはもうしばらくかかるだろう。それまでにはもっと便利でより良い環境が揃ってくることになると思う。

最後に

Google Waveはまだ正式にリリースされたわけではない。まだまだ発展途上のプレビュー版だ。機能も不完全であり、開発環境も安定していない。なので、今すぐにWaveアカウントを手に入れられなくても気にすることはないと思う。将来のGoogle Waveがどのように使えて、どのように便利なのかを知ってもらい、Google Waveが利用されることなく廃れてしまうことが私たちにとってどれだけ「損する」ことなのかを理解してもらうことが、これを記した理由だ。なので、今すぐ使い始めなければ「損する」というわけではない。しかし、それでも今すぐに使いたい方もいると思う。残念ながら自分の持っている招待枠は使ってしまったので、「Waveプレビュー版の招待を得る」などを参考にアカウントを手に入れて欲しい。

参考サイト

Google Waveの最新情報や便利な使い方を知りたい場合には、以下のサイトが参考になる。

紹介ビデオ

Google Waveの使い方が簡潔にまとめられているビデオ(約5分半)。

(*1) 「iPhoneとツイッターで会社は儲かる」

ブログクラブより献本して頂いた。Twitterの利点がわかりやすくまとめられており、今回のテーマとも一部共通するので紹介させてもらった。Twitterの利点や利用方法を知りたい方は読んでおいて損はないと思う。個人的には最後の社員アンケートが面白かった。

Scratchでプログラミングする子供たち

2010-03-09T04:38:00.006+09:00

小学2年生の娘にスクラッチアイデアブックを渡したら、あっという間に読み終え、Scratchを使って自由気ままにいろいろなプログラムを作り始めた。書籍を参考にシューティングゲームを作ったり(砲台は戦闘機の替りに何故か女の子)、耳コピの「かえるのうた」を音の制御で鳴らして口パクで歌う女の子たちのアニメーションを作ったり(表情や髪型、足の微妙な動きなど、芸が細かい)、好きなように想像して、好きなように作っていた。保育園に通う息子は、書籍は読めないけど、Scratchで絵を描いたり、プログラムの部品をいじることはできるので、やはり多様な想像力を働かせて、大人では考えつかないようなスプライトを作り、回転させたり、大きくしたり、音を鳴らせたりして、楽しんでいた。

これはたった一日の出来事だ。子供の吸収力は凄いと感心させられる。以前、「Scratchで素数を求めてみた」というブログ記事で、Scratchによるプログラミングが子供の頃に遊んだレゴブロックみたいで楽しいと述べたのだが、その楽しさを表現する能力についてはやはり現役の子供には敵わなかったようだ。それにしても、子供たちが描いた絵が思うさまに動いているのを見ると、自分が子供の頃にもScratchがあったらなぁ、とつくづく思ってしまう。当時、自分で絵を描いたり、ブロックを組み立てたりすることだけでも楽しかったのに、それを好きなように動かせることができたのなら本当にワクワク・ドキドキしたことだったろう。

今回一つ思ったことは、子供たちには最小限のことだけを教えておいて、後は子供たちだけで何とかさせるというスタンスがとても良さそうであるということだ。疑問に思ったことは試行錯誤で解決しようとするし、それでも分からなければ本で調べる。ネットで調べてもいいのだけど、Scratchは日本語のまとまった資料が少ないのでそれが難しい。今後、多くの子供たちにScratchに触れてもらい、たくさんの人たちにScratchを知ってもらいたい。

以下に、参考サイトを挙げておく。

Scratch公式サイト - 想像・プログラム・共有
子どもたちがOSS活動、プログラミング言語「Scratch」が開く未来
非プログラマのためのプログラミング講座
こどもプログラミングサークル‘スクラッチ’
小学生にプログラミングの楽しさを伝えてみた

最後に、娘の作ったScratchプログラムの一つを載せておく。スペースキーを押せば始まるが、音が出るので注意して欲しい。

このプロジェクトについてもっと知る

Google Wave Robots API v2でボットを書き直してみた

2010-03-07T01:49:00.007+09:00

先日、Google WaveのRobots APIバージョン2がリリースされた。更新内容の概要は「Google Wave Robot API v2のリリースエントリを翻訳しました」が分かりやすい。そこで、以前に作成した「てめーはおれを怒らせた」ボットをバージョン2のAPIで書き直してみることにした。しかし、すぐに修正できるだろうとナメていたら意外と時間が掛かってしまった。

初っ端でいきなり動かない。ほとんどチュートリアルと同じ程度に削っても動かない。エラーを頼りにAPIのソースコードなどを読んだりしているうちに、自分のプログラムの問題ではないんじゃないかと思い、動作確認していた環境をSandboxからPreviewに変更してみたら、問題なく動くようになった。ここでかなりの時間ロス。さらに、インターフェースも大きく変わっていて、新しいAPIでどのように実装するのか調べるだけでも結構時間を取られた。

書き直したソースコードは以下の通り。本当にこれで良いのか自信はないが、ちゃんと動作するようだ。因みに、ボットのアカウントはbillowlet@appspot.comだ。Google WaveのContactsパネルから登録すれば使うことができる。

慣れていないので手こずってしまったが、以前のバージョンに比べて、できることは増えているし、APIの構成も分かりやすくなっている。それに、ちゃんとGoogle Wave Robot Python API v2のドキュメントが整備されているのが嬉しいところ。何か面白いボットを作ってみたいな。

追記(2010/3/15):

Sandboxでも正常に動作するようになったみたい。

billowlet.py

#!/usr/bin/env python # -*- coding: utf-8 -*- """billowlet.py by nox, 2010.3.6""" import re, urllib, urllib2, random from google.appengine.ext import db from waveapi import events from waveapi import robot from waveapi import blip from waveapi import appengine_robot_runner from waveapi import simplejson HIRAGANA = u"あいうえおかきくけこさしすせそたちつてとなにぬねのはひふへほまみむめもやゆよらりるれろわをん" KATAKANA = u"アイウエオカキクケコサシスセソタチツテトナニヌネノハヒフヘホマミムメモヤユヨラリルレロワヲン" class UserData(db.Model): user = db.StringProperty(multiline=False) status = db.StringProperty(multiline=False) def OnWaveletParticipantsChanged(event, wavelet): participants = event.participants_added for participant in participants: if participant != "billowlet@appspot.com": wavelet.reply(u"%s、おれを怒らせるなよ。" % participant.split("@")[0]) def OnWaveletSelfAdded(event, wavelet): wavelet.reply(u"おれはbillowlet。よろしくな。") def Translate(text, from_lang, to_lang): url = "http://ajax.googleapis.com/ajax/services/language/translate?v=1.0&q=%s&langpair=%s%%7C%s" % (urllib.quote(text.encode("utf-8")), from_lang, to_lang) data = simplejson.loads(urllib2.urlopen(url).read()) return data["responseData"]["translatedText"] def BeCat(text): text = re.sub(u"。", u"にゃ。", text) text = re.sub(u"？|\?", u"にゃぁ？", text) text = re.sub(u"！|\!", u"にゃっ！", text) text = re.sub(u"な", u"にゃ", text) if text[-1] not in (u"。", u"？", u"?", u"！", u"!"): text += u"にゃ" return text def DotMarks(text): from_kana = u"かきくけこさしすせそたちつてとはひふへほカキクケコサシスセソタチツテトハヒフヘホ" to_kana = u"がぎぐげござじずぜぞだぢづでどばびぶべぼガギグゲゴザジズゼゾダヂヅデドバビブベボ" for f, t in zip(from_kana, to_kana): text = text.replace(f, t) return text def Laugh(text, ch): for i in range(len(text), 0, -1): text = text[:i] + ch + text[i:] return text.replace(u"。", u"").replace(u"、", u"") + ch * random.randint(3, 10) def Kana(idx): return HIRAGANA[idx] + u"|" + KATAKANA[idx] def OnBlipSubmitted(event, wavelet): blp = event.blip user = blp.creator opq = wavelet.get_operation_queue() data = UserData.all().filter("user =", user).get() if data: status = data.status else: status = None text = blp.text.strip() if status and re.match(u"ごめんなさい|ゆるして", text): json = opq.blip_create_child(blp.wave_id, blp.wavelet_id, blp.blip_id) child_blp = blip.Blip(json, wavelet.blips, opq) child_blp.append(u"ゆるしてやる。やれやれだぜ。".encode("utf-8")) if data: data.delete() st = (u"ネコになれ。", # 0 u"英国紳士になれ。", # 1 u"台湾に住め。", # 2 u"インチキ日本人になれ。", # 3 u"大事なことは2回言え。", # 4 u"笑え。", # 5 u"濁れ。", # 6 u"逆さまになれ。", # 7 u"どもれ。", # 8 u"うざくなれ。") # 9 fn = {st[0]: BeCat, st[1]: lambda (text): Translate(text, "ja", "en"), st[2]: lambda (text): Translate(text, "ja", "zh-TW"), st[3]: lambda (text): Translate(Translate(text, "ja", "en"), "en", "ja"), st[4]: lambda (text): text + text + u"\n大事なことなので2回言いました。", st[5]: lambda (text): Laugh(text, u"ｗ"), st[6]: DotMarks, st[7]: lambda (text): text[::-1], st[8]: lambda (text): (text[0] + u"、") * 3 + text, st[9]: lambda (text): Laugh(text, u"っ")} angry = range(len(HIRAGANA)) random.shuffle(angry) if status: text = fn[status](text) blp.range(1, len(blp.text)).replace(text.encode("utf-8")) else: userdata = UserData() for i in range(len(st)): if re.search(Kana(angry[i]), text): status = st[i] break if status: json = opq.blip_create_child(blp.wave_id, blp.wavelet_id, blp.blip_id) child_blp = blip.Blip(json, wavelet.blips, opq) text = u"てめーはおれを怒らせた。%s" % status child_blp.append(text.encode("utf-8")) userdata.user = user userdata.status = status userdata.put() def main(): myRobot = robot.Robot("billowlet", image_url="http://billowlet.appspot.com/assets/icon.png", profile_url="http://billowlet.appspot.com/") myRobot.register_handler(events.WaveletParticipantsChanged, OnWaveletParticipantsChanged) myRobot.register_handler(events.BlipSubmitted, OnBlipSubmitted) myRobot.register_handler(events.WaveletSelfAdded, OnWaveletSelfAdded) appengine_robot_runner.run(myRobot) if __name__ == "__main__": main()

AndroidからPythonでTwitterに投稿する

2010-03-01T01:30:00.007+09:00

AndroidにASE (Android Scripting Environment)を入れてから楽しくてちょくちょくいじっているのだけど、Pythonに初めからtwitterモジュールが入っていることに気が付いたので使ってみた。

普段はAndroid端末(HT-03A)のTwitterクライアントとしてTwidroidを使っているのだけど、最初の立ち上げでタイムラインを取得しに行くのでちょっとだけ待たされる。あまり気にはならないけど、つぶやきをサクっと投稿したいだけならタイムライン取得は無駄なので、投稿専用のスクリプトを組んでみることにした。以下がそのコードだ。起動するとダイアログが出るのでつぶやきを書いて送信するだけだ。送信が完了したら画面に投稿したつぶやきが表示されて終了する。

# -*- coding: utf-8 -*- import android, twitter droid = android.Android() t = droid.getInput(u"Tweet", u"いまどうしてる?")["result"].strip() if t: api = twitter.Api("username", "password") api.PostUpdate(t) droid.makeToast(t)

これはすべてAndroid上でコーディングしたものだ。短いし、せいぜい数分もあれば書ける。書き終わったらそれをそのままホーム画面にショートカットアイコンとして登録すればいい。他にも、bit.lyのAPIを使って短縮URLを実装したり、サービスとして起動させ、特定のキーワードに引っかかったときにAndroidに通知させたり、メールを送信させたりすることも簡単だろう。やはり、スクリプトが使えるといろいろできて面白いな。

Android上でPython、Lua、JavaScriptなどを実行するスクリプティング環境が凄い

2010-02-25T01:45:00.011+09:00

ASE (Android Scripting Environment)を使って簡単にPython, Perl, JRuby, Lua, BeanShell, JavaScript (Rhino), それにシェル(将来的にはさらにたくさんのスクリプト言語)をAndroid上で実行できるのはご存じだろうか。ASEのインストールからスクリプトの作成、実行まで、すべてAndroid単体でできる。もちろん、PC上でコーディングしたい場合は、USBで繋げてPC上のスクリプトをAndroid端末上で実行することもできるし、PC上のコードをAndroid端末にコピーすることもコマンド一発だ。さらに、各種センサー、位置情報、SMS、テキストの読み上げなどもスクリプト上で操作できるというのだからこれを使わない手はない。

そこで、試しにPythonスクリプトを書いてみた。Android端末のGPS機能で緯度経度を取得して、逆ジオコーディングで現在の住所を表示するスクリプトだ。Google Maps APIのURLなどを含めた雛形だけPCからAndroid端末(HT-03A)にコピーして、通勤時の電車の中で書いたのが以下のコードだ。

# -*- coding: utf-8 -*- import android, time, json, urllib url = "http://maps.google.com/maps/geo?ll=%.16f,%.16f&sensor=false&output=json&hl=ja&oe=UTF8&key=Google_Maps_API_Key" droid = android.Android() droid.startLocating() for i in range(10): location = droid.readLocation() if location["result"]: break time.sleep(1) lat, lng = location["result"]["network"]["latitude"], location["result"]["network"]["longitude"] geo_data = json.loads(urllib.urlopen(url % (lat, lng)).read())["Placemark"] geo_data = sorted(geo_data, key=lambda x: -x["AddressDetails"]["Accuracy"]) address = geo_data[0]["address"] droid.makeToast(address)

シェル環境が使えるので、print文を使ったデバッグも簡単だった。苦労すると思われたソフトキーボードもQWERTY配列と予測変換が使えるので思ったよりも楽だったし、トラックボールでのカーソル移動、コピー、カット、ペーストもある。できればキーボード付き端末が欲しいところだが、これからAndroid端末はたくさん出てくると予想されるので、そちらに期待している。早いところ、DroidやXperia X10 mini proが日本で出て欲しいところだ。因みに、作成したスクリプトはASE上でも実行できるし、ホーム画面にショートカットアイコンを作って直接実行もできる。

本格的なAndroidアプリケーションを作成するにはAndroid SDKとJavaになるのだろうが、個人的に使う小さなスクリプトならASEの方が端末上でサクッと書けるし、比較的大きなコードでもPC上で作成し、PCに端末を接続してデバッグ、完成したら端末にコピーすればいい。それに、様々なスクリプト言語が使えるので、自分が使いたいスクリプトを選べるのも魅力だ。対話環境も利用できるのでスクリプト言語の勉強のために使うのもありだと思う。

以下に、ASEの導入方法と使い方を書いておく。

準備

ASEはGoogleの公式プロジェクトではあるが、ちゃんと認証を受けたソフトウェアではないので(将来的にはAndroid Marketで配布されるらしい)、Androidの設定で[アプリケーション]-[提供元不明のアプリ]のチェックをオンにしておく必要がある(インストール後にはオフに戻しておくこと)。次に、Android端末でandroid-scriptingのFeatured downloadsにある最新版をダウンロードして、そのままインストールする。

ASEを起動し、メニューを開くと[Interpreters]の項目があるので、それを選択する。初期状態ではShellだけが選択できるようになっているが、他のスクリプト言語を入れたい場合は、メニューを開いて[Add]を選択する。ダイアログが開き、複数のスクリプト言語が表示されるので、使いたい言語を選択する。選択すると自動的にダウンロードされインストールされる。

PCとAndroid端末を連動させたい場合は、PCにAndroid SDKをインストールする必要がある。以前に導入方法を書いたので、そちらを参考にして欲しい。

さて、これでASEを使用する準備が整った。

使い方

まず、端末上でのコーディング方法を説明する。ASEを起動してメニューを開き、[Add]を選択するとダイアログが開くので、作成したいスクリプト言語を選ぶ。ソースコードの雛形が出るので、それにコードを書いていく。書き上がったら適当なファイル名で保存する。実行するにはASEを起動した最初の画面で表示されるスクリプトファイルを選択してもいいし、スクリプトのショートカットを作っておいてホーム画面から起動してもいい。因みにショートカットを作成するには、ASE起動時に表示されるスクリプトファイルを長押しして[Add Shortcut]を選べばいい。

次に、PCとAndroid端末をUSBで接続してAndroid上で実行する方法を示す。これについては、Android ASE (Android Scripting Environment)入門を参考にさせてもらった。

最初にPCとAndroid端末をUSBで接続する。このとき端末側の設定で[アプリケーション]-[開発]-[USBデバッグ]をオンにしておく。

ASEのインタプリタ起動時に表示されるAP_PORTが55063で、PC上のポートを4321(任意の未使用ポートを選べる)とする場合は、Windowsでは以下のようにコマンドプロンプト(シェル)上で設定する。因みに%はプロンプトを示している。

% adb forward tcp:4321 tcp:55063 * daemon not running. starting it now * * daemon started successfully * % set AP_PORT=4321

最後にデーモンを停止してポートを閉じる場合は、以下のコマンドを使う。

% adb kill-server

また、PCにもAndroidで使用するスクリプト環境が入っている必要がある。例えばPythonを使う場合はあらかじめPCにもPyhton 2.6をインストールしておき、さらにandroid.pyを、PythonをインストールしたディレクトリのLib/site-packages/にコピーしておく。これでPC上で実行したスクリプトがAndroid端末で動作する。

最後に、PC上で作成したスクリプトをAndroid端末にコピーする方法だが以下のようにすればコピーできる。ただし、将来にわたってコピー先のディレクトリが不変である保証はない。

% adb push 作成したスクリプトファイル /sdcard/ase/scripts/

Android端末上のディレクトリを調べたい場合、

% adb shell

とすればリモートシェルが立ち上がるので、以下のように調べることができる。

$ cd /sdcard/ase/scripts cd /sdcard/ase/scripts $ ls ls saychat.py notify_weather.py speak.py weather.py saytime.py sayweather.py test.py $

注意事項

今回、HT-03Aで使用したのだが、入力方法がiWnn IMEやOpenWnnになっているとASEのインタプリタ上で文字を入力できなかった。入力するには入力方法をAndroidキーボードにする必要がある。ただし、スクリプトの作成・編集についてはどの入力方法でも問題はなかった。

追記(2010/4/5):

記事を書いた時点でのASEはase_r16.apkだったが、現在の最新版はase_r20.apkになっている。頻繁に更新されるのでダウンロードする際は最新版の確認をして欲しい。

追記(2010/6/27):

ASE r22からreadLocation()のデータ構造が変更されたようなので、それに合わせて上述のコードを修正した。

「ハッカーと画家」を読んで

2010-02-15T21:32:00.006+09:00

ポール・グレアムの「ハッカーと画家コンピュータ時代の創造者たち」を読んだ。もっと以前に読んでいてしかるべき本であったが、読みそびれていた。もっと技術的な話だと思っていたのだが、(プログラマであれば)気軽に読めるとても面白いエッセイ集だった。

個人的に興味深かったのは、第4章の「天邪鬼の価値」で、ジョブズとウォズニアックが錠開け装置をいじっている写真だ。リチャード・ファインマンがマンハッタン計画で重要書類の入っている金庫を破ることを楽しみにしていたり、グレアムが学生の頃のMITではピッキングが流行ったりしていたそうだが、それを読んで、自分が子供の頃のことを思い出した。古いダイアル式南京錠が家にあったのだが、それは錠が閉まっていて親に聞いても番号が分からないという。そこでどうやったら開けることが出来るかを考えるうちに面白くなり、次第に夢中になっていった。ダイアルは3桁の数字なので、10*10*10=1000通りを試したら必ず開けられる。しかし、そんな面倒なことはしたく無い。悪用されても困るので詳しくは書かないけど、しばらくいじっているうちにキーの動きに法則があることに気がついた。こうなれば簡単で、最大で10+10+10=30通りを試すだけでよくなる。これで開かない錠前を開けることができた。今で言えばセキュリティに欠陥があるということなのだろうが、困難だと思われることに挑戦し、それを克服することは、とても強い達成感となる。子供ながらにそう感じた。ファインマンもMITの学生もそう感じたのだろう。これがハックする理由の原点だろうか。

第13章の「オタク野郎の復讐」を読めば分かるけど、ポール・グレアムは熱心なLispハッカーで、Lispを非常に高く評価している。確かに他の言語の意義についても説いてはいるけど、「他のプログラミング言語はとうとう(Lispの生まれた)1958年に追いつこうとしている」と書いていることからもLispが最も良い言語だと考えているのが分かる。確かにLispは良い言語だと思うけど、個人的には万人にLispを勧めることはできないなぁ。

自分の場合は、普段はC++とPythonを利用していて(多くの場合はこれで事足りる)、最近は並列化のためにTBBやCUDA、それとErlangを使ったりしている。もちろんAndroidで開発するときはJavaだし、グラフィカルなことをしたいときはProcessingやActionScriptを使うし、他にも様々な言語をいじったりするけども、結局、言語の選択はその環境と目的に強く依存されると思う。それに、複数の言語から選択できる方が一つの言語に固執するより健全じゃないかなぁ(一つの言語を極めてみるというのには異存はないけど)。複数の言語を覚えるのは大変そうに思えるかもしれないけど、最初に2～3の言語を習得すれば、それ以降はあまり苦労せずに覚えることができると思う。

ところでLispの開発環境についてだけど、WindowsでCommon Lispを使いたいときはEmacs Lispの代わりにCommon Lispライクなマクロ言語を搭載したxyzzyが手軽だ。LinuxならCLISPやSBCLがよく使われている。

ポール・グレアムの最新のエッセイはPaul Graham - Essaysから読むことができる。日本語訳はnaoya_t:ポール・グレアムのエッセイと和訳一覧でまとめられているので、興味のある方は読んでみてはどうだろうか。あと、第13章「オタク野郎の復讐」で納得しかねたPythonユーザはPaul Prescodの「PythonとLispの関係について」(川合史朗訳)を読んでみることをお勧めしたい。

Erlang基礎文法最速マスター

2010-02-05T00:40:00.044+09:00

先日、Lua基礎文法最速マスターを書いてみたが、予想以上に自分自身への学習効果が高かった。そこで、普段使っているPythonと同じぐらいに使いこなしたいと思っていたErlang(アーラン)の基礎文法最速マスターを書いてみることにした。

Erlangが関数型プログラミング言語であることもあり、書き下すのは思ったよりも大変だったが、学習効果はかなりあったと思う。言語を習得したいときはこのようなまとめを書いてみるのが良さそうだ。

ただ、手続き型プログラミング言語に比べて異なる部分があまりにも大きいので、すべてを説明することは難しく、これを読んだだけですぐに使えたりはしないかもしれない。また、間違っていたり、足りない部分などがあったら、教えて頂けるとありがたい。

1. 基礎

対話環境

コマンドラインからerlを実行すると対話環境(シェル)になります。コマンドの最後にはピリオド(.)が必要です。help()で簡単な説明を読むことができます。

$ erl 1> A = 10. % Aに10を束縛. 10 2> B = A * 5. % BにA * 5 (50)を束縛. 50 3> hello. % helloはアトム(定数のようなもの/後述). hello 4> b(). % 現在の束縛変数を表示. A = 10 B = 50 ok 5> A = 20. % 変数は一度しか代入(束縛)できない. ** exception error: no match of right hand side value 20 6> f(). % 束縛変数をすべてクリアする. ok 7> A = 20. % 再度束縛できる. 20 8> q(). % Erlangシェルを終了させる. ok

画面出力

io:formatで書式指定の出力を行うことができます。

~p : 整形して出力. ~s : 文字列を出力. ~f : 浮動小数点数を出力. ~w : Erlangの標準構文として出力(アトムならそのまま、文字列ならリストとして出力など) ~n : 改行.

io:format("Hello world~n"). % "Hello world" %% "5 , 1.235, 30, erlang" io:format("~-5w, ~6.3f, ~p, ~s~n", [5, 1.23456, 30, "erlang"]).

%から行末までがコメントになります。ブロックコメントはありません。慣例として%%がよく使われます。

% コメント. %% コメント.

変数の代入

Erlangの変数の先頭は必ずアルファベットの大文字かアンダーバー(_)になります。また、一度代入すると後から変更できません。代入した変数のことを束縛変数と呼びます。まだ代入されていない変数のことを未束縛変数と呼びます。変数は動的型付けなので宣言は必要ありません。

A = 5. % ※1 B = "Hello world". C = atom. A = 10. % Aは束縛変数のためエラーになる. A = 5. % ※2 Aは束縛変数だが、パターン照合が一致するのでエラーにならない.

実のところ、=は代入演算子ではなく、パターン照合演算子になります。例えば、※1のA = 5のAは未束縛変数であり、どんな値にもパターンが一致するので5の照合が成功して、Aに5が束縛できるのです。※2のA = 5では、既にAは5に束縛されているので、数値の5か、5の値を持つ変数とだけ照合が成功します。

Erlangで重要な要素の一つにアトムがあります。アトムとは数値以外の不変値を表すのに使用します。C言語の列挙子などが近い存在です。アトムは通常アルファベットの小文字から始まります。変数に代入することができます。

atom. A = hello.

また、先頭文字を大文字にしたり、空白や特殊記号を使用したい場合はシングルクォーテーション(')で囲むことでアトムとなります。

'Atom'. 'This is an atom.'.

ある項目を一つにまとめたい場合はタプルを使います。タプルは中括弧({})で括ることにより作れます。

A = {pen, book, desk}. B = {b, {language, "erlang"}, 10}.

タプルから値を取り出す場合、パターン照合を使います。

C = A. % 未束縛変数Cに {pen, book, desk}が入る. {b, D, 10} = B. % Bのタプルと未束縛変数Dを含む{b, D, 10}はパターンが一致するのでDに{language, "erlang"}が入る. {b, E, 20} = B. % パターンが一致しないのでエラーになり、Eは未束縛変数のまま.

いくつかのパターン照合の例を以下に挙げておきます。

{X, 123} = {10, 123}. % 成功. Xに10が入る. {X, 12} = {10, 123}. % 失敗. 12と123が一致しない. {A, B, A} = {5, 10, 5}. % 成功. Aに5、Bに10が入る. {A, B, C} = {5, 20, 8}. % 失敗. Bには10が束縛されている. {A, _, _} = {5, 20, 8}. % 成功. アンダーバー(_)はどの値とも一致する. [H|T] = [1, 2, 3]. % 成功. Hに1、Tに[2, 3]が入る. [A, B|T] = [1, 2, 3, 4, 5]. % 成功. Aに1、Bに2、Tに[3, 4, 5]が入る.

スクリプトの実行

コンパイルして実行するには以下のようにコマンドを実行します。ただし、ソースコードをコンパイルするためには、先頭でモジュール名をアトムで指定する必要があり、モジュール名は基本的に拡張子を除いたファイル名が使われます。例えば、ソースコードのファイル名がtest.erlであれば、-module(test).と指定します。-exportについては後述の関数の説明を参照してください。

test.erl

-module(test). -export([hello/0]). hello() -> io:format("Hello world~n").

シェル上で実行:

1> c(test). % コンパイル. {ok,test} 2> test:hello(). Hello world ok

コマンドラインで実行:

$ erlc test.erl % コンパイル. $ erl -noshell -s test hello -s init stop Hello world

ここでは、-noshellにより対話型シェルを立ち上げず、-s test helloでtest:hello()を実行し、-s init stopで終了させています。

次に示すように、escriptで実行すればコンパイルは不要ですが、実行時に呼ばれる関数はmain/1となります。-moduleと-exportは必要ありません。

test.erl

#!/usr/bin/env escript main(_) -> io:format("Hello world~n").

実行:

$ ./test.erl Hello world

コマンドライン引数を取る場合は、以下のようにします。

test.erl

-module(test). -export([main/0, main/1]). main() -> % 引数なしの場合. io:format("No argument.~n"). main(A) -> % 引数ありの場合. [io:format("~s ", [X]) || X <- A], io:nl().

実行:

$ erlc test.erl % コンパイル. $ erl -noshell -s test main Hello world -s init stop Hello world $ erl -noshell -s test main -s init stop No argument.

2. 数値

数値の表現

Erlangは最後がピリオド(.)になるので、1.は整数の1であり、実数の1.0ではありません。実数の1.0にするには、1.0.と書く必要があります。

A = 1. % これは整数の1 B = 1.0. % これは実数の1.0

各種演算

5 + 2. % 7 5 - 2. % 3 5 * 2. % 10 5 / 2. % 2.5 5 div 2. % 2 (商) 5 rem 2. % 1 (剰余)

インクリメントとデクリメント

Erlangは関数型言語で代入は一度しかできないので当然インクリメントはできません。

3. リスト

Erlangでは角括弧によりリストを作ることができます。また、単一代入なので一度作成したリストを変更することはできません。変更したい場合は別のリストを作成します。

リストの作成

A = [1, 2, 3].

リストの要素への参照

Erlangではリストの先頭のインデックスは1となります。

%% 要素の参照. lists:nth(1, A). % リストAの先頭の要素. hd(A)と同じ. lists:nth(2, A). % リストAの2番目の要素.

リストの個数

N = length([1, 2, 3]). % 3

リストの操作

A = [1, 2, 3]. %% 先頭を取り出す. F = hd(A). % Fは 1 [H|T] = A. % Hは 1、Tは[2, 3] %% 先頭に追加. B = [5|T]. % Bは[5, 2, 3] %% 末尾を取り出す. C = lists:last(B) % Cは3 [L|R] = lists:reverse(B). % Lは3、Rは[2, 5] %% 末尾に追加. D = A ++ [9]. % Dは[1, 2, 3, 9]

4. 文字列

文字列表現

ダブルクォーテーション(")で括ると文字列になりますが、Erlangではそれを整数のリストとして扱っています。

"abc". % [97, 98, 99] と同じ意味. io:format("~p~n", [[97, 98, 99]]). % "abc"と表示される. A = "abc". % [97, 98, 99]

文字列操作

%% 結合. A = string:concat("aaa", "bbb"). % "aaabbb" A = lists:concat(["aaa", "bbb", "ccc"]). % "aaabbbccc" join([]) -> []; join([H|T]) -> string:concat(H, join(T)). % バイナリ文字列の場合は、Hをbitstring_to_list(H)に. A = join(["aaa", "bbb", "ccc"]). % "aaabbbccc" %% 分割. A = re:split("aaa, bbb, ccc", "\s*,\s*"). % [<<"aaa">>, <<"bbb">>, <<"ccc">>] バイナリ文字列. A = regexp:split("aaa, bbb, ccc", "\s*,\s*"). % ["aaa", "bbb", "ccc"] regexpは遅いのでre推奨. %% 長さ. L = length("abc"). % 3 %% 切り出し. S = string.substr("abcd", 1, 2). % "ab" 文字列の先頭は1、先頭から2文字を切り出し. %% 検索. R = string:rstr("abcd", "cd"). % 見つかった場合はその位置(この場合は3)、見つからなかった場合は0が返る.

比較演算子

整数と浮動小数点数の比較以外では==と/=の代わりに、=:=と=/=を使うようにしましょう。

N1 == N2 % N1はN2と等しい. N1 =:= N2 % N1はN2と同一. N1 /= N2 % N1はN2と等しくない. N1 =/= N2 % N1はN2と同一でない. N1 < N2 % N1はN2より小さい. N1 > N2 % N1はN2より大きい. N1 =< N2 % N1はN2以下. N1 >= N2 % N1はN2以上.

5. 関数

Erlangでは関数名は必ずアルファベットの小文字から始まり、以下のような構文になります。

関数名(引数) [when ガード] -> 式1, 式2, ... 式N.

式はカンマ(,)で区切り、関数の終端はピリオド(.)になります。また、モジュールの外部から関数を呼び出すためには-exportアノテーションで関数を指定しなければなりません。例えばmain([A])を呼び出したい場合、-export([main/1]).のように指定します。これは引数が1つあるmain関数をエクスポートするという意味です。Erlangでは引数の個数のことをアリティと呼びます。因みに、-exportで関数を指定しなくても、-compile(export_all).とすれば、モジュール内の関数すべてを外部から呼び出せます。

以下のsum関数は再帰を使ってリスト内のすべての要素を足し合わせます。ここでは引数のパターンが[]と[H|T]の2種類出てきていますが、上から順にパターンが照合され一致する関数が評価されます。それぞれの関数の区切りにはセミコロン(;)が使用されます。

sum([]) -> 0; sum([H|T]) -> H + sum(T).

関数名の右側にあるwhenとはガードと呼ばれるパターンを補助する仕掛けで、このガードの条件を満たさなければパターンが一致していても式は評価されません。以下のsum_odd関数はカードを使って奇数のみを足し合わせています。

sum_odd([]) -> 0; sum_odd([H|T]) when H rem 2 =:= 1 -> H + sum_odd(T); sum_odd([_|T]) -> sum_odd(T).

サンプルプログラムとして、ガードを使ってFizzBuzz問題を解いてみます。1から100までを表示する場合はfizzbuzz(100).と実行します。

fizzbuzz(N) when N rem 15 =:= 0 -> io:format("FizzBuzz~n"); fizzbuzz(N) when N rem 3 =:= 0 -> io:format("Fizz~n"); fizzbuzz(N) when N rem 5 =:= 0 -> io:format("Buzz~n"); fizzbuzz(N) -> io:format("~p~n", [N]).

パターン照合を使って以下のように書くこともできます。

fb(_, 0, 0) -> "FizzBuzz"; fb(_, 0, _) -> "Fizz"; fb(_, _, 0) -> "Buzz"; fb(N, _, _) -> N. fizzbuzz(0) -> ok; fizzbuzz(N) -> fizzbuzz(N-1), io:format("~p~n", [fb(N, N rem 3, N rem 5)]).

Erlangでは、funを使うことによって無名関数を使うことができます。

F = fun(X) -> X * 3 end. F(10). % 30

6. 制御文

case文

case 条件 of パターン1 [when ガード1] -> 式1; パターン2 [when ガード2] -> 式2; ... パターンN [when ガードN] ->式N end

パターンを1から順に条件と照合して一致するパターンの式を返します。case文でもガードを使うことができます。

以下に例を示します。

X = case {20, 30, 40} of {10, A, B} -> one; {20, A, B} when A > 50 -> two; {20, A, _} when A < 50 -> three; true -> others end.

タプル{20, 30, 40}とパターンを比べると、2番目のパターン{20, A, B}と一致してますが、ガードのA > 50の条件に一致しないので式は評価されません。次のパターン{20, A, _}も一致していて、さらにガードA < 50の条件とも一致するので式が評価され、アトムthreeがXに入ることになります。最後のパターンtrueはすべての条件と一致します。

上述のFizzBuzz問題をcase文とリスト内包表記(後述)を使って1行で書くこともできます。

[io:format("~p~n",[case{N,N rem 3,N rem 5}of{_,0,0}->fizzbuzz;{_,0,_}->fizz;{_,_,0}->buzz;{N,_,_}->N end])||N<-lists:seq(1,100)].

if 文

if ガード1 -> 式1; ガード2 -> 式2; ... ガードN -> 式N end

例を挙げます。

N = 10. %% Resultにはsameが入る. Result = if N < 10 -> low; N =:= 10 -> same; N > 10 -> high end.

for/while文

Erlangにはfor文もwhile文もありません。その代わりに関数を使って表現できます。

例えばC言語のfor文を使った以下のようなコードについて考えます。

for (i = 1; i <= 10; i++) { printf("%d\n", i * i); }

Erlangではこれを以下のように書くことができます。

for(M, M, F) -> [F(M)]; for(I, M, F) -> [F(I) | for(I+1, M, F)]. for(1, 10, fun(I) -> io:format("~p~n", [I*I]) end).

7. ファイル入出力

ファイル操作にはfileモジュールを利用します。

{ok, S} = file:open("input.txt", read). % 入力をinput.txtから読み込む. {ok, W} = file:open("output.txt", write). % 出力をoutput.txtに書き出す. %% input.txtから数値を読み込んで、その数値を倍にしてoutput.txtに書き込む. for_write(eof, _, _) -> ok; for_write(L, S, W) -> {N, _} = string:to_integer(L), io:format(W, "~p~n", [N*2]), for_write(io:get_line(S, ''), S, W). for_write(io:get_line(S, ''), S, W).

バイナリデータinput.datを読み込んで、それをoutput.datに2回書き込みます。

{ok, B} = file:read_file("input.dat"). file:write_file("output.dat", B). file:write_file("output.dat", B, [binary, append]).

8. 平行プログラミング

my_server.erlに以下のコードを作成します。

-module(my_server). -export([loop/0]). loop() -> receive hello -> io:format("Hello!~n"), loop(); bye -> io:format("See you!~n") end.

これをシェル上でspawn関数を使って、spawn(fun モジュール名:関数名/アリティ)のように呼び出します。因みにfun モジュール名:関数名/アリティは、関数の参照を行うための記法になります。

1> Pid = spawn(fun my_server:loop/0). 2> Pid ! hello. Hello! 3> Pid ! bye. See you!

spawn関数によりmy_server:loop関数をプロセス上に実行させて、プロセスIDのPidを取得し、送信演算子 ! でhelloメッセージを送ることによりプログラムから返事が返ってきます。上記のプログラムではbyeと送ることで終了します。

spawn関数は上記の方法のほかに、spawn(モジュール名, 関数名, [引数])のように使うこともできます。

1> Pid = spawn(my_server, loop, []).

平行プログラミングはErlangの存在を際立たせているのですが、ここで扱うには規模が大きすぎるので割愛します。詳しくは参考サイトなどを参照してください。

知っておいた方がよい文法

真偽値

真偽値の型はありませんが、アトムのtrueとfalseが真偽値のリテラルとして使われます。

not true. % falseアトムが返される.

論理演算子

true or false. % true true and false. % false not true. % false

ビット演算子

1 bor 2. % 3 5 band 3. % 1 5 bxor 3. % 6 bnot 3. % -4 1 bsl 2. % 4 - 左シフト 16 bsr 2. % 4 - 右シフト

map関数

%% [1, 4, 9, 16 ,25] - リストの要素をそれぞれ2乗にする. lists:map(fun(X) -> X * X end, [1, 2, 3, 4, 5]).

定義された関数を使う場合は以下のようになります。

square(X) -> X * X. % 2乗を返す関数. lists:map(fun square/1, [1, 2, 3, 4, 5]).

filter関数

%% [1, 3, 5] - 奇数のみのリストを作る. lists:filter(fun(X) -> X rem 2 =:= 1 end, [1, 2, 3, 4, 5]).

リスト内包表記

上述のmap関数はリスト内包表記を使って以下のように書くことができます。

[X * X || X <- [1, 2, 3, 4, 5]]. % [1, 4, 9, 16, 25]

上述のfilter関数は以下のように書くことができます。

[X || X <- [1, 2, 3, 4, 5], X rem 2 =:= 1]. % [1, 3, 5]

数値と文字列の変換

list_to_integer("12"). % 12 list_to_float("123.5"). % 123.5 integer_to_list(12). % "12" float_to_list(123.5). % "1.23500000000000000000e+002"

参考サイト

基礎文法最速マスターまとめサイト

Lua基礎文法最速マスター

2010-02-02T16:48:00.030+09:00

最近、基礎文法最速マスターというプログラミング言語の解説が流行ってるようなので、便乗してみた。個人的にはC++やPythonの方が慣れ親しんでいるのだが、自分でも勉強できるように普段使っていない言語を書いてみることにした。以前にここのブログで言及した言語、Processing、Erlang、Lua、PowerShellなどの中でもErlangとLuaに興味があったので、比較的書きやすいLuaを選んでみた。

何故Luaなのか? Wikipediaによると、Luaはブラジル・リオデジャネイロのカトリカ大学で生まれた手続き型言語だ。高速な動作、高い移植性、組み込みの容易さが特徴だ。また、ホストプログラムへの組み込みが容易であることもあって、コンピュータゲームなどで利用されている。有名どころでは、PlayStation HomeやWorld of Warcraftなどがある。また、小飼弾氏もなんてめんこい言語と述べているように評価が高い。

さて、早速Lua基礎文法最速マスターを書いてみる。上述のように自分にとっては勉強を兼ねて書いているので、間違いや記述漏れなどがあるかもしれない。コメントなどで指摘していただけるとありがたい。また、C言語の連携など、足りない部分については随時追加していく予定だ。

追記(2010/2/9): 「C言語とLuaの連携」を追加した。

1. 基礎

対話環境

Luaは対話環境として実行できます。

$ lua Lua 5.1.4 Copyright (C) 1994-2008 Lua.org, PUC-Rio > print("Hello world") Hello, world > print(1 + 2) 3 > print(type("Hello world")) string

print関数の代わりに = を利用することもできます。

> = "Hello world" Hello world > = 1 + 2 3 > = type("Hello world")) string

print関数

print("Hello world") print(1 + 2)

ハイフン2つ(--)から行末までがコメントになります。

-- コメント.

複数行コメントには--[[ ～ ]]を使います。また、最後の]]を--]]としておけば、先頭の--[[を---[[と変更することでコメントを外すことができます。

--[[ これは, コメントです. --]] ---[[ print("これは,") print("コメントではありません.") --]]

変数の宣言と代入

大域変数には宣言はありません。局所変数にはlocalを使います。

a = 1 a = "hello" local a = 3 local a = "world"

Luaでは多重代入することができます。

a, b, c = 1, 2, 3

多重代入を利用してスワップが可能です。

a, b = b, a -- aとbの値を入れ替える.

スクリプトの実行

コマンドラインから以下のように実行することができます。

lua test.lua

またコマンドライン引数はテーブルargに保持されます。

--[[ arg[-1]: "lua" arg[0]: "test.lua" arg[1]: "arg1" arg[2]: "arg2" --]] lua test.lua arg1 arg2

2. 数値

数値の表現

実数と整数の区別はありません。以下の変数b, c, dは同じ数値になります。

a = 1 b = 1.234 c = 0.1234e1 d = 12.34e-1

各種演算

num = 5 + 2 -- 7 num = 5 - 2 -- 3 num = 5 * 2 -- 10 num = 5 / 2 -- 2.5 num = 5 % 2 -- 1 (剰余) num = 5 ^ 2 -- 25 (累乗)

インクリメントとデクリメント

Luaには++演算子や+=演算子がないので以下のように記述します。

i = i + 1 i = i - 1

3. 文字列

文字列表現

文字列はシングルクォート(')かダブルクォート(")で囲みます。2重の角括弧([[～]])でも文字列となり、エスケープシーケンスなどもそのまま表示できます。

str = 'abc' str = "abc" str = [[abc]] str = 'ab"cd"ef' -- ab"cd"ef str = "ab'cd'ef" -- ab'cd'ef str = "abc\ndef" -- abcに改行が入り、次の行にdefが出力される str = [[abc\def]] -- abc\defが1行で出力される

string.format関数を利用してC言語のprintf関数のような書式設定ができます。

string.format("%d, %6.3f", 10, 12.34567) -- 10, 12.346 ("%d, %6.3f"):format(10, 12.34567)

"%q"は、安全に読み出せる文字列に書式化します。

--[[ "test\ \"test\"\ test" --]] string.format("%q", 'test\n"test"\ntest') ("%q"):format('test\n"test"\ntest')

文字列操作

分割については標準ライブラリにないので自前でsplit関数を用意します。

-- 結合. a = "aaa" .. "bbb" -- "aaabbb" a = table.concat({ "aaa", "bbb", "ccc" }, ",") -- "aaa,bbb,ccc" -- 分割. function split(str, del) p, nrep = str:gsub("%s*"..del.."%s*", "") return { str:match((("%s*(.-)%s*"..del.."%s*"):rep(nrep).."(.*)")) } end split("aaa, bbb, ccc", ",") -- { "aaa", "bbb", "ccc" } -- 長さ. length = #"abc" -- 3 -- 切り出し. substr = string.sub("abcd", 0, 2) -- ab substr = ("abcd"):sub(0, 2) -- 検索. result = string.find("abcd", "cd") -- 見つかった場合はその位置(この場合は3)、見つからなかった場合はnilが返る. result = ("abcd"):find("cd")

4. 配列

配列変数の宣言と代入

-- 配列の宣言 array = {} -- 配列への代入 array = { 1, 2, 3 }

配列の要素の参照と代入

Luaでは配列の添え字(インデックス)は通常1から始まります。

-- 要素の参照. array[1] -- 配列arrayの先頭. array[2] -- 要素の代入. array[1] = 1 array[2] = 2

配列の個数

array_num = #array array_num = table.getn(array)

配列の操作

array = { 1, 2, 3 } -- 先頭を取り出す. first = table.remove(array, 1) -- firstは 1, arrayは { 2, 3 } -- 先頭に追加. table.insert(array, 1, 5) -- arrayは { 5, 2, 3 } -- 末尾を取り出す. last = table.remove(array) -- lastは 3, arrayは { 5, 2 } -- 末尾に追加. table.insert(array, 9) -- arrayは { 5, 2, 9 }

5. テーブル

Luaのテーブルは連想配列になっていて、nilを除く数値や文字列を添え字とすることができます。上述の配列についても基本的にはテーブルとなります。また、テーブルを入れ子にしたり、関数を保持させることもできます。

テーブルの宣言と代入

t = { 1, 2, 3 } t = { name = "lua", length = 3, sense = "moon" } t = { "students", name = { "taro", "hanako", "kenta" }, num = 3 } t = { func1 = function() return "ok" end, func2 = function(a, b) local c = a * b return c end }

テーブルの要素の参照と代入

-- 要素の参照. t[1] t["name"] t.name -- 文字列を添え字にする場合はピリオド(.)を使用できる. t.func2(2, 3) -- テーブルに保持した関数を呼び出す. -- 要素の代入. t[1] = 5 t["name"] = "lua" t.name = "lua"

6. 制御文

if 文

if 条件 then -- 条件が真. end

if ～ else文

if 条件 then -- 条件が真. else -- 条件が偽. end

if ～ elseif 文

if 条件1 then -- 条件1が真. elseif 条件2 then -- 条件1が偽、条件2が真. end

while文

while 条件 do -- 条件が真の間、処理される. end

repeat ～ until文

repeat -- 条件が偽の間、処理される. until 条件

for文

for i = 1, 10 do print(i) -- 1, 2, 3, 4, 5, 6, 7, 8, 9, 10を出力. end for i = 1, 10, 2 do print(i) -- 1, 3, 5, 7, 9を出力. end

汎用forループとipairs/pairs関数を使って配列/テーブルを出力できます。

for i, value in ipairs({ 10, 20, 30 }) do --[[ 1 10 2 20 3 30 と表示される. --]] print(i, value) end data = { a = 5, b = 6, c = 7 } for key, value in pairs(data) do --[[ a 5 c 7 b 6 と表示される. --]] print(key, value) end

比較演算子

比較演算子では偽の時にfalse、真の時にtrueを返します。

num1 == num2 -- num1はnum2と等しい. num1 ~= num2 -- num1はnum2と等しくない. num1 < num2 -- num1はnum2より小さい. num1 > num2 -- num1はnum2より大きい. num1 <= num2 -- num1はnum2以下. num1 >= num2 -- num1はnum2以上.

7. 関数

Luaでは関数を作るにはfunction(...) ～ endを使います。また、関数内に関数を作ることができます。

function sum(num1, num2) local total = num1 + num2 return total end sum = function(num1, num2) local total = num1 + num2 return total end

8. ファイル入出力

Lua独自のファイル入出力として、io.input, io.output関数があります。初期状態で標準入力、標準出力に割り当てられています。

io.input("input.txt") -- 入力をinput.txtから読み込む. io.output("output.txt") -- 出力をoutput.txtに書き出す. while line = io.read() do print(line) -- io.write(line .."\n")と同じ. end io.input() -- 入力を標準入力にする. io.output() -- 出力を標準出力にする.

C言語のようなファイル入出力にはio.open関数を使います。

--[[ r: 読み込み, w:書き込み, a:追記, r+, w+, a+ fh: ファイルハンドル, msg: エラーメッセージ. --]] fh, msg = io.open("input.txt", "r") if fh then data = fh:read("*a") -- ファイル全体を読み込む. print(data) else print(msg) end

9. C言語とLuaの連携

LuaではC言語と連携を取るためのAPIが充実しているので、C言語からLuaを利用することも、LuaからC言語を利用することも簡単です。基本的な流れとして、スタックに積んだデータをやりとりすることになります。

以下にサンプルコードを示しておきます。LuaからC言語を利用する場合も、C言語からLuaを利用する場合も、C言語のソースコードをコンパイルしたファイルから実行されます。

ヘッダファイルやライブラリのパスを通した上で、Visual Studioでは、

cl func.c lua51.lib

gccでは、

gcc func.c -llua -lm

でコンパイルできます。

func.lua

print(func1(1.5)) -- C言語で作成した関数func1を呼び出す. data = { test = "lua" } print(func2(data)) -- C言語で作成した関数func2を呼び出す.

func.c

#include #include "lua.h" #include "lualib.h" #include "lauxlib.h" /* 引数で渡された数値を半分と倍にして返す */ int func1(lua_State *L) { /* 最初のスタックから数値を読み出す */ double d = lua_tonumber(L, 1); lua_pushnumber(L, d / 2.0); /* 半分にしてスタックに載せる */ lua_pushnumber(L, d * 2.0); /* 倍にしてスタックに載せる */ return 2; /* 戻り値のスタック数 */ } /* 引数で渡されたテーブル内のtestフィールドの文字列を返す */ int func2(lua_State *L) { /* スタックをクリアする */ lua_settop(L, 1); /* テーブル内のフィールド"test"をスタックの最初に置く */ lua_getfield(L, 1, "test"); /* スタックの2番目(つまりフィールド"test"のデータ)の */ /* 文字列を読み出してスタックに置く*/ lua_pushstring(L, lua_tostring(L, 2)); return 1; /* 戻り値のスタック数 */ } int main() { /* Luaを使えるようにする */ lua_State *L = luaL_newstate(); /* Luaの標準関数を利用可能にする */ luaL_openlibs(L); /* C言語で作成した関数をLua上で呼び出せるようにする */ lua_register(L, "func1", func1); lua_register(L, "func2", func2); /* Luaソースファイル"func.lua"を読み出して実行する */ /* func.lua内でfunc1, func2を利用している */ if (luaL_loadfile(L, "func.lua") || lua_pcall(L, 0, 0, 0)) { fprintf(stderr, "error\n"); return -1; } /* luaL_dostringを利用してC言語からLuaを使用する */ luaL_dostring(L, "print(3.5)"); /* スタックを利用してC言語からLuaを利用する */ lua_getglobal(L, "print"); /* print関数をスタックに置く */ lua_pushstring(L, "string"); /* 文字列"string"をスタックに置く*/ lua_pcall(L, 1, 0, 0); /* 引数1個、戻り値なし、エラー関数なしで実行 */ lua_close(L); return 0; }

出力結果:

0.75 3 lua 3.5 string

上記の方法だと、LuaからC言語の関数を呼び出す場合でもC言語からLuaのコードを呼ばなくてはならず、コンパイルが必要になります。そこで、以下にC言語による関数をWindowsのDLLファイルおよびUnixの共有ライブラリファイルのモジュールとして呼び出す方法を書いておきます。関数の内容は上記のコードと同じで、func1とfunc2を定義しています。

Visual Studioでのコンパイル方法は以下の通りです。

cl cmodule.c lua51.lib /LD

gccでのコンパイル方法は以下のようになります。

gcc cmodule.c -llua -shared -o cmodule.so

実行は、通常のLuaスクリプトと同じです。

lua func_mod.lua

func_mod.lua

require("cmodule") -- cmodule.dll/cmodule.soを読み込む. print(cmodule.func1(1.5)) -- C言語で作成した関数func1を呼び出す. data = { test = "lua" } print(cmodule.func2(data)) -- C言語で作成した関数func2を呼び出す.

cmodule.c

#include <stdio.h> #include "lua.h" #include "lauxlib.h" /* 引数で渡された数値を半分と倍にして返す */ static int func1(lua_State *L) { /* 最初のスタックから数値を読み出す */ double d = lua_tonumber(L, 1); lua_pushnumber(L, d / 2.0); /* 半分にしてスタックに載せる */ lua_pushnumber(L, d * 2.0); /* 倍にしてスタックに載せる */ return 2; /* 戻り値のスタック数 */ } /* 引数で渡されたテーブル内のtestフィールドの文字列を返す */ static int func2(lua_State *L) { /* スタックをクリアする */ lua_settop(L, 1); /* テーブル内のフィールド"test"をスタックの最初に置く */ lua_getfield(L, 1, "test"); /* スタックの2番目(つまりフィールド"test"のデータ)の */ /* 文字列を読み出してスタックに置く*/ lua_pushstring(L, lua_tostring(L, 2)); return 1; /* 戻り値のスタック数 */ } /* モジュールに登録するために関数のテーブルを定義 */ static luaL_Reg cmodule[] = { { "func1", func1 }, { "func2", func2 }, { NULL, NULL } /* 最後は NULL, NULL とする */ }; /* DLL/共有ライブラリにエクスポートする関数 luaopen_(モジュール名) */ /* Unixでは__declspec(dllexport)は不要 */ __declspec(dllexport) int luaopen_cmodule(lua_State *L) { luaL_register(L, "cmodule", cmodule); /* cmoduleモジュール */ return 1; }

出力結果:

0.75 3 lua

知っておいた方がよい文法

真偽値

falseとnil以外はすべて真になります。よって、0や""や空のテーブルなどもすべて真です。

論理演算子

a = 10 b = 30 c = a < 20 or b < 20 -- true d = a < 20 and b < 20 -- false a = 10 or 20 -- a = 10 a = 10 and 20 -- a = 20 a = nil or 10 -- a = 10 a = nil and 10 -- a = nil

初期化されていない変数はすべてnilが入っていることを利用して、orを使ってデフォルト値を設定することができます。

a = a or 10 -- aに何も代入されていなければ10が代入される.

外部Luaファイルの読み込み

外部Luaファイルの実行やテーブルなどのデータを読み込む目的で利用できます。

dofile("file.lua")

文字列をプログラムとして実行

Perlなどのeval機能として、loadstring関数があります。

f = loadstring("i = i + 1") i = 0 f() f() f() print(i) -- 3と表示される.

データの型を文字列で返す

type(1) -- "number" type("abc") -- "string" type({ 1, 2, 3 }) -- "table" type(true) -- "boolean" type(print) -- "function"

数値と文字列の変換

tonumber("123.5") -- 123.5 tostring(123.5) -- "123.5"

参考サイト

他の基礎文法最速マスター

C++0x: 構造体を格納したSTLコンテナに対してソート・探索・削除などのアルゴリズムを適用する

2010-01-22T02:54:00.002+09:00

先日、構造体を格納したコンテナに対してSTLのアルゴリズムを適用する方法について記したが、今回はそれをC++0xで書き直してみた。C++0xの規格はまだきちんと定まっていないが、草案ではかなりのところまでつめられてきており、また対応するC++コンパイラも出てきていることから今のうちにC++0xに慣れておいた方が良いと思う。今回のプログラムで行う内容については前回と全く同じだが、C++0xを使うことによりかなりすっきり書くことができた。因みに現時点の最新の規格(草案)はN3000 (PDF)になる。日本語での資料はC++0xの言語拡張まとめ (Faith and Brave - C++で遊ぼう)や本の虫が詳しい。余談だが、2010年になっても0xから1xに変わることはないようだ。C++の生みの親であるBjarne Stroustrupによれば、0xのxは16進数と考えて欲しいとのこと。

C++0xでは多くの便利な機能が追加されているが、今回はラムダ式、auto型指定子、初期化子リストを使用した。使用したコンパイラはVisual Studio 2010 beta2 (VS2010)、GCC 4.5 (snapshot 20100114)、Intel Compiler 11.1だが、残念ながらVS2010とIntel Compiler 11.1では初期化子リストの機能が実装されていないので、それらを使用する場合、今回示したコードのうち素数を格納する静的メンバコンテナの初期化部分は変更しなくてはならない。また、GCCについては最新リリース版である4.4.2でラムダ式が使えないので、ここでは開発版の4.5を使用している。その他のコンパイラも含めてC++0xへの対応はC++0xCompilerSupportで確認できる。

初期化子リストを使用しない:

static int init_primes[] = { 2, 3, 5, 7 }; vector<int> IsPrime::primes(init_primes, init_primes + 4);

初期化子リストを使用する:

vector<int> IsPrime::primes = { 2, 3, 5, 7 };

今回のコードでは関数オブジェクトを多用していたのでラムダ式が非常に有効だった。ラムダ式を使えば関数オブジェクトを用意しなくてもその場ですぐに記述できるからだ。

以下のコードは関数オブジェクトを用意してsort関数を使用した例だ。

class LessAn { public: bool operator()(const A& a, const A& b) { return a.n < b.n; } }; sort(A_list.begin(), A_list.end(), LessAn());

これに対しラムダ式を使えば、以下のように一行で済ませることができる。

sort(A_list.begin(), A_list.end(), [](const A& a, const A& b) { return a.n < b.n; });

このように、C++0xは機能の一部を使うだけでもとても便利だ。規格が新しくなるたびに新たに覚えなくてはならないことが増えるので、それを面倒と見る向きもあるかもしれないが、そのコストに見合うだけの価値がC++0xにはあると思う。

最後にC++0xで書き換えたソースコードを示す。クラスによる関数オブジェクトがごっそり無くなっていることに気付くだろう。前回からの変更部分は赤で示している。変更前のコードや実行時の出力結果については前回の記事を参考にして欲しい。

#include <iostream> #include <iomanip> #include <vector> #include <algorithm> #include <numeric> #include <cstdlib> using namespace std; const int num_A = 10; // A_listコンテナ内の構造体Aの数. const int max_n = 30; // 構造体A内の配列の最大数. // 構造体A : 要素数n, 要素の配列pを持つ. struct A { int n; int *p; A(int n_, int *p_) : n(n_), p(p_) { for (int i = 0; i < n; i++) p[i] = rand() % max_n; } }; // 構造体Aの表示. void print(const A& a) { cout << setw(3) << a.n << " :"; for (int i = 0; i < a.n; i++) cout << " " << a.p[i]; cout << endl; } // A_listコンテナの表示. void print(const vector<A>& a_list) { cout << " n : p[]" << endl; for (auto p = a_list.begin(); p != a_list.end(); ++p) print(*p); cout << endl; } // 任意の数値を素数判定する関数オブジェクト. class IsPrime { private: static vector<int> primes; int i, j; public: bool operator()(int n) { if (n < 2) return false; if (binary_search(primes.begin(), primes.end(), n)) return true; for (auto p = primes.begin(); p != primes.end(); ++p) { if (n < (*p) * (*p)) return true; if (n % *p == 0) return false; } for (i = *(primes.end() - 1) + 2; i * i <= n; i += 2) { for (j = 0; i > primes[j] * primes[j] && i % primes[j] != 0; j++); if (i < primes[j] * primes[j]) { primes.push_back(i); if (n % i == 0) return false; } } return true; } }; // 素数を格納する静的メンバコンテナ. vector<int> IsPrime::primes = { 2, 3, 5, 7 }; int main() { vector<A> A_list; // 構造体Aのvectorコンテナ A_list. // A_listを乱数で初期化. for (int i = 0; i < num_A; i++) { int n = rand() % max_n + 1; A_list.push_back(A(n, new int[n])); } cout << "初期化した構造体Aのコンテナ(A_list):" << endl; print(A_list); cout << "構造体Aの配列(A.p)をソートして重複データを削除:" << endl; for_each(A_list.begin(), A_list.end(), [](A& a) { sort(a.p, a.p + a.n); a.n = unique(a.p, a.p + a.n) - a.p; }); print(A_list); cout << "構造体Aの配列(A.p)の要素数(A.n)でA_listをソート:" << endl; sort(A_list.begin(), A_list.end(), [](const A& a, const A& b) { return a.n < b.n; }); print(A_list); cout << "構造体Aの配列(A.p)を素数のみにする:" << endl; for_each(A_list.begin(), A_list.end(), [](A& a) { a.n = stable_partition(a.p, a.p + a.n, IsPrime()) - a.p; }); print(A_list); cout << "構造体Aの配列要素の和が偶数ならA_listから削除:" << endl; A_list.erase(remove_if(A_list.begin(), A_list.end(), [](const A& a) { return accumulate(a.p, a.p + a.n, 0) % 2 == 0; }), A_list.end()); print(A_list); cout << "再び構造体Aの配列(A.p)の要素数(A.n)でA_listをソート:" << endl; sort(A_list.begin(), A_list.end(), [](const A& a, const A& b) { return a.n < b.n; }); print(A_list); cout << "構造体Aの配列(A.p)内で指定した数値と一致する要素を持つ構造体Aを探す:" << endl; for (int i = 0; i < 10; i++) { auto p = find_if(A_list.begin(), A_list.end(), [i](const A& a) { return find(a.p, a.p + a.n, i) != a.p + a.n; }); cout << setw(3) << i << " : "; if (p != A_list.end()) print(*p); else cout << "指定の数値を要素として持つ構造体Aは見つかりませんでした." << endl; } return 0; }

整数の分割

2010-01-19T00:47:00.008+09:00

整数の分割(integer partitions)を列挙するプログラムを書いてみた。ここでは再帰を用いた比較的単純な実装を示すが、より効率的なアルゴリズムを考えるとなると奥が深い。

整数の分割とは、ある整数を自然数の和で表したものだ。例えば分割する整数を5とすると求める自然数は以下のようになる。

5 4 1 3 2 3 1 1 2 2 1 2 1 1 1 1 1 1 1 1

今回のC++で書いたコードは単純で理解しやすいと思うが、高速化などは考えていない。もしよりよいアルゴリズムに興味があるのならAntoine Zoghbiu and Ivan Stojmenovic. Fast Algorithms for Generating Integer Partitions. Intern. J. Computer Math., 70, 319-332 (1998) (PDF)あたりが参考になるかも。

使い方は以下の通り。

partitions 分割したい整数 [分割した要素の最大値]

分割したい整数が5であれば、

partitions 5

とする。出力は次のようになる。

5 (max 5): 7 5 4 1 3 2 3 1 1 2 2 1 2 1 1 1 1 1 1 1 1

また、分割したい整数が5で、分割した要素の最大値を3とする場合は、

partitions 5 3

で、以下のような出力を得る。

5 (max 3): 5 3 2 3 1 1 2 2 1 2 1 1 1 1 1 1 1 1

partitions.cpp

#include <iostream> #include <vector> #include <algorithm> #include <cstdlib> using namespace std; void partitions(int n, int max_n, vector<int>& v, vector<vector<int> >& vv) { if (n == 0) { vv.push_back(v); return; } for (int i = min(n, max_n); i > 0; i--) { v.push_back(i); partitions(n - i, i, v, vv); v.pop_back(); } } int main(int argc, char* argv[]) { if (argc < 2) { cerr << "Usage: " << argv[0] << " number [max_number_in_partitions]" << endl; exit(1); } int n = atoi(argv[1]); int max_n = argc > 2 ? atoi(argv[2]) : n; vector<vector<int> > vv; partitions(n, max_n, vector<int>(), vv); cout << n << " (max " << max_n << "): " << vv.size() << endl; for (vector<vector<int> >::const_iterator p = vv.begin(); p != vv.end(); ++p) { for (vector<int>::const_iterator q = p->begin(); q != p->end(); ++q) cout << " " << *q; cout << endl; } return 0; }

余談だが、ActiveState CodeでPythonのジェネレータを使った以下のようなコードを見つけた。さらに同じ作者がその2年後に書いた記事から、別アルゴリズムのソースコード(tarball)を読むことができる。

def partitions(n): # base case of recursion: zero is the sum of the empty list if n == 0: yield [] return # modify partitions of n-1 to form partitions of n for p in partitions(n-1): yield [1] + p if p and (len(p) < 2 or p[1] > p[0]): yield [p[0] + 1] + p[1:]

C++: 騎士の巡歴と周遊

2010-01-12T09:11:00.009+09:00

「騎士の巡歴(Knight's Tour)」を解くプログラムをC++で書いてみた。騎士の巡歴とはチェスボード上の駒「ナイト」を移動させてすべてのマスを一回ずつ通過させる問題だ。特に最初の駒の位置に戻ってくる解を「騎士の周遊(Closed Knight's Tour)」と呼ぶ。

一応、C++らしいコードを心掛けてみたけど、思ったより長くなってしまった。騎士の巡歴ではWarnsdorffのアルゴリズム、騎士の周遊においてはそれに加えてSchwenkの定理を用いている。また、Puzzle DE Programmingで書かれている方法も参考にさせてもらった。

まず、ボード上のマスをNode構造体のポインタで表現し、*nodeとする。そのnodeからナイトが動けるマスをvector<Node*> next;として保持する。また、一度通ったnodeはnode->visitedにそれを記録しておく。nextを順に巡っていくが、Warndorffのアルゴリズムにより、移動先となるnext内のnodeのうち、動けるマスの最も少ないnodeを移動先とする。すべてのマスを通れば探索終了だ。

また、騎士の周遊については、最初にSchwenkの定理から解があるかどうかを判断する。解があれば、騎士の巡歴と同様の手順でまず解を見つける。ここで、見つけた解の最初のマスからナイトが動けるマスをA、最後のマスからナイトが動けるマスをBとし、BからAの順となるマスがあるかどうか調べる。もしあれば、そのAのマスから最後のマスまでの順路を逆にすればそれが騎士の周遊の解となる。もし、BからAの順となるマスがなければ、動けるマスが見つかるまでバックトラックにより探索する。この手順については上記のPuzzle DE Programmingが詳しい。

プログラムの使い方は以下の通り。

knight 行数列数 [駒のスタート行=0 駒のスタート列=0 巡歴か周遊か?]

スタート位置はデフォルトで(0, 0)で、何も指定がなければ騎士の巡歴を求める。騎士の周遊の場合は、コマンドラインの最後に c を付ける。

例えば、16x16マス上で騎士の周遊を解く場合は以下のようにする。

knight 16 16 c

出力結果:

1 254 31 232 205 196 29 194 203 106 27 104 187 108 25 102 32 229 256 253 30 235 204 197 28 193 202 107 26 103 180 109 255 2 231 206 233 252 195 238 201 198 105 186 181 188 101 24 230 33 228 219 236 213 234 251 192 247 190 199 112 179 110 177 3 224 209 214 207 220 237 246 239 200 185 182 189 176 23 100 34 227 218 223 210 241 212 167 250 191 248 113 184 111 178 67 225 4 215 208 217 166 221 240 245 160 183 172 175 68 99 22 128 35 226 165 222 211 242 161 168 249 170 149 114 173 66 69 5 164 129 216 143 162 157 244 159 148 115 174 171 98 21 64 36 127 136 163 156 243 144 141 152 169 150 93 116 65 70 55 133 6 155 130 137 142 153 158 147 92 117 80 97 56 63 20 126 37 132 135 154 145 140 87 118 151 94 73 62 71 54 57 7 134 125 138 131 86 119 146 91 74 81 96 79 58 19 50 38 123 40 85 120 139 88 45 82 95 76 61 72 51 16 53 41 8 121 124 43 10 83 90 75 12 47 78 59 14 49 18 122 39 42 9 84 89 44 11 46 77 60 13 48 17 52 15

24x12マスで(10, 5)の位置から騎士の巡歴を解く場合は以下のようにする。

knight 24 12 10 5

出力結果:

24 27 106 225 272 29 108 231 250 31 110 113 105 226 25 28 107 230 267 30 109 112 249 32 26 23 224 271 268 273 232 251 266 247 114 111 211 104 227 288 229 270 259 276 233 252 33 248 22 223 210 269 280 285 274 265 258 263 246 115 103 212 281 228 287 260 277 262 275 234 253 34 214 21 222 209 284 279 286 257 264 245 116 235 193 102 213 282 219 256 261 278 241 254 35 244 20 215 194 221 208 283 240 255 204 243 236 117 101 192 153 218 239 220 207 242 237 200 205 36 152 19 216 195 190 1 238 203 206 175 118 201 159 100 191 154 217 196 189 178 199 202 37 124 18 151 158 187 172 179 2 197 174 125 176 119 99 160 155 184 157 188 173 168 177 198 123 38 150 17 148 161 186 171 180 3 126 169 120 129 95 98 185 156 183 146 167 170 165 128 39 122 16 149 96 147 162 181 164 127 4 121 130 69 97 94 137 182 135 142 145 166 131 70 5 40 138 15 92 141 144 163 134 73 66 57 68 59 93 88 139 136 83 74 143 132 71 60 41 6 14 81 84 91 140 133 72 65 56 67 58 49 87 78 89 82 75 64 55 46 61 50 7 42 80 13 76 85 90 11 62 53 44 9 48 51 77 86 79 12 63 54 45 10 47 52 43 8

示した画像は出力した解をPython+PILで画像に変換したものだ。以下のように使用する。

show_knight.py 解のデータファイル出力画像ファイル [幅=400 高さ=400]

上記の例では以下のようにする。

show_knight.py knight_16x16.txt knight_16x16.png
show_knight.py knight_24x12.txt knight_24x12.png 300 600

また、今回のプログラムでは200x200マスの騎士の周遊でもほぼ瞬時に解くことができた。先頭の画像はその解だ。多くの場合は問題なく解を見つけることができるが、場合によっては困難なこともある。そのようなときはスタート位置を変更することで解けることがある。

以下にプログラムのソースコードを示す。

knight.cpp

// Solver of Knight's Tour using Warnsdorff's algorithm and Schwenk's theorem #include <iostream> #include <iomanip> #include <vector> #include <algorithm> #include <utility> #include <cmath> #include <cstdlib> using namespace std; struct Node { int row, col; bool visited; vector<Node*> next; Node(int r, int c) : row(r), col(c), visited(false) { } }; class IsUnvisited { public: bool operator()(const Node* a) { return !a->visited; } }; class IsVisited { public: bool operator()(const Node* a) { return a->visited; } }; class NotEqualUnvisited { private: const int cnt; public: NotEqualUnvisited(const Node* a) : cnt(count_if(a->next.begin(), a->next.end(), IsUnvisited())) { } bool operator()(const Node* a) { return count_if(a->next.begin(), a->next.end(), IsUnvisited()) != cnt; } }; class LessMovable { public: bool operator()(const Node* a, const Node* b) { int cnt_a = count_if(a->next.begin(), a->next.end(), IsUnvisited()); int cnt_b = count_if(b->next.begin(), b->next.end(), IsUnvisited()); return cnt_a < cnt_b; } }; class KnightTour { private: int nrow, ncol; vector<pair<int, int> > moves; vector<Node*> nodes, tour, best_tour; bool is_closed; public: KnightTour(int r, int c, bool closed) : nrow(r), ncol(c), is_closed(closed) { // Knight can move two horizontally and one vertically, // or one horizontally and two vertically. moves.push_back(make_pair( 2, 1)); moves.push_back(make_pair( 1, 2)); moves.push_back(make_pair( 2, -1)); moves.push_back(make_pair( 1, -2)); moves.push_back(make_pair(-2, 1)); moves.push_back(make_pair(-1, 2)); moves.push_back(make_pair(-2, -1)); moves.push_back(make_pair(-1, -2)); } void search(Node* node); void run(int start_pos); void print(); }; void KnightTour::search(Node* node) { if (node->visited) return; if (best_tour.size() == nrow * ncol) { // for Closed Knight's Tour if (is_closed) { if (find(best_tour.back()->next.begin(), best_tour.back()->next.end(), best_tour.front()) != best_tour.back()->next.end()) return; for (vector<Node*>::iterator p = best_tour.back()->next.begin(); p != best_tour.back()->next.end(); ++p) { vector<Node*>::iterator q = find(best_tour.begin(), best_tour.end(), *p) + 1; vector<Node*>::iterator r = find(best_tour.front()->next.begin(), best_tour.front()->next.end(), *q); if (r != best_tour.front()->next.end()) { reverse(q, best_tour.end()); return; } } best_tour.clear(); } return; } node->visited = true; tour.push_back(node); if (best_tour.size() < tour.size()) best_tour = tour; // Warnsdorff's algorithm sort(node->next.begin(), node->next.end(), LessMovable()); vector<Node*> next(node->next); next.erase(remove_if(next.begin(), next.end(), IsVisited()), next.end()); if (!next.empty()) next.erase(remove_if(next.begin(), next.end(), NotEqualUnvisited(next.front())), next.end()); for (vector<Node*>::iterator p = next.begin(); p != next.end(); ++p) search(*p); node->visited = false; tour.pop_back(); } void KnightTour::run(int start_pos) { // initialization for nodes for (int i = 0; i < nrow; i++) for (int j = 0; j < ncol; j++) nodes.push_back(new Node(i, j)); for (vector<Node*>::iterator p = nodes.begin(); p != nodes.end(); ++p) { for (vector<pair<int, int> >::iterator q = moves.begin(); q != moves.end(); ++q) { int r = (*p)->row + q->first; int c = (*p)->col + q->second; if (r >= 0 && r < nrow && c >= 0 && c < ncol) (*p)->next.push_back(nodes[r*ncol+c]); } } // Schwenk's theorem if (is_closed && (nrow * ncol % 2 == 1 || (min(nrow, ncol) == 2 || min(nrow, ncol) == 4) || (min(nrow, ncol) == 3 && (max(nrow, ncol) == 4 || max(nrow, ncol) == 6 || max(nrow, ncol) == 8)))) return; if (!is_closed && nrow * ncol % 2 == 1 && start_pos % 2 == 1) return; search(nodes[start_pos]); } void KnightTour::print() { if (best_tour.size() < nrow * ncol) { cout << "No solution." << endl; return; } vector<vector<int> > board(nrow, vector<int>(ncol)); int cnt = 1; for (vector<Node*>::iterator p = best_tour.begin(); p != best_tour.end(); ++p) board[(*p)->row][(*p)->col] = cnt++; int width = static_cast<int>(log10(static_cast<double>(nrow * ncol)) + 2); for (int i = 0; i < nrow; i++) { for (int j = 0; j < ncol; j++) cout << setw(width) << board[i][j]; cout << endl; } } int main(int argc, char* argv[]) { if (argc <= 2) { cerr << "Usage: " << argv[0] << " nrow ncol [start_row=0 start_col=0] [closed]" << endl; exit(1); } int nrow = atoi(argv[1]); int ncol = atoi(argv[2]); int r = 0, c = 0; if (argc > 4) { r = atoi(argv[3]); c = atoi(argv[4]); } bool is_closed = false; if (argv[argc-1][0] == 'c') is_closed = true; KnightTour kt(nrow, ncol, is_closed); kt.run(r * ncol + c); kt.print(); return 0; }

show_knight.py

#!/usr/bin/env python import sys, os, Image, ImageDraw def draw_board(board, nrow, ncol, size, offset_x, offset_y, out_image): im = Image.new("RGB", size) im.paste((255, 255, 255)) draw = ImageDraw.Draw(im) for i in range(0, size[0], offset_x): draw.line((i, 0, i, size[1]), fill=0) for i in range(0, size[1], offset_y): draw.line((0, i, size[0], i), fill=0) for i in range(0, size[0], offset_x): for j in range(0, size[1], offset_y): if (i // offset_x + j // offset_y) % 2 == 1: im.paste((190, 190, 190), (i + 1, j + 1, i + offset_x, j + offset_y)) for i in range(nrow * ncol - 1): draw.line((board[i] % ncol * offset_x + offset_x // 2, board[i] // ncol * offset_y + offset_y // 2, board[i+1] % ncol * offset_x + offset_x // 2, board[i+1] // ncol * offset_y + offset_y // 2), fill=(255, 0, 0)) if sorted([abs(board[nrow*ncol-1] % ncol - board[0] % ncol), abs(board[nrow*ncol-1] // ncol - board[0] // ncol)]) == [1, 2]: draw.line((board[nrow*ncol-1] % ncol * offset_x + offset_x // 2, board[nrow*ncol-1] // ncol * offset_y + offset_y // 2, board[0] % ncol * offset_x + offset_x // 2, board[0] // ncol * offset_y + offset_y // 2), fill=(255, 0, 0)) im.save(out_image) def main(args): if len(args) < 3: print >>sys.stderr, "Usage: %s in_datafile out_imagefile [size_x=400 size_y=400]" % os.path.basename(args[0]) sys.exit(1) in_file, out_image = args[1:3] if len(args) < 5: size = (400, 400) else: size = map(int, args[3:5]) data = [map(int, l.strip().split()) for l in file(in_file)] nrow, ncol = len(data), len(data[0]) board = range(nrow * ncol) cnt = 0 for r in data: for c in r: board[c-1] = cnt cnt += 1 offset_x, offset_y = size[0] // ncol, size[1] // nrow size = (offset_x * ncol + 1, offset_y * nrow + 1) draw_board(board, nrow, ncol, size, offset_x, offset_y, out_image) if __name__ == "__main__": main(sys.argv)

2010年を迎えて

2010-01-01T17:49:00.004+09:00

明けましておめでとうございます。

今年でこのブログも4年目になるなぁ。早いものだ。自分が初めてインターネットに触れたのが1994年で、それ以前はNIFTY-ServeやPC-VAN、草の根BBSなど利用していた。インターネットを利用し始めたころはメールアドレスを持っていても周りが誰も使っていなかったので全くの無用の長物だった。その頃、みんなが電子メールを持つようになれば素晴らしい世界になるのにと考えたものだが、それから数年でその「素晴らしい世界」になったわけだ。

自分のウェブサイトを作ったのが1996年から、ブログを書き始めたのは2000年2月14日からだけど、最初の頃はHTMLを直接編集していた。その後、Movable Typeに移行してしばらく使っていた。それからいくつかのサイトやブログなどに手を出し、科学情報ばかりを扱った「科学随想録」や以前ハマったMMOのEverQuestのギルド用フォーラムを作成したりしつつ、今の「良いもの。悪いもの。」に落ち着いた。

このブログはプログラミング関連情報をメインとして扱っているけど、昨年は、Google Wave、Android、Twitter、mixiアプリなどが興味深かったな。今年はどんな技術が出てくるんだろう。今からワクワクする。ブログ記事は自分が楽しめるものを書く、書きたい時が書き時というスタンスだけど、他の人にも楽しんでもらえるとしたら嬉しい。因みに自分のプログラミングスタイルの変遷は「プログラミングができるということは、人生を楽にできるということ」に書いてある。

これからもどうぞよろしくお願いします。

良いもの。悪いもの。

恭賀新年

円周率を1万桁まで求める

好きな・嫌いなコンピュータ言語のアンケート

コンピュータにラストワンを解かせてみた

オフィスビル内の最短経路

GoogleのURL短縮サービスgoo.glのAPIをPythonで利用する

暇潰しで書いたプログラム

Scalaのアクターモデルでマンデルブロ集合を並列計算

CUDA 4.0でマルチGPU化が限りなく簡単になっているという話

C++: Base64エンコード・デコードとURLエンコード

タンパク質分子において水素原子の位置が異なるアミノ酸構造の同型判定

東北地方太平洋沖地震 可視化地図

開発エンジニアの世界へ

複数のGPUでマンデルブロ集合を並列計算

2010年から2011年へ

ある重さを量るのに使う錘の組み合わせは何通り?

Android端末による自動通訳を一行のPythonコードで実装する

SL4AのPythonを使ってAndroid端末に日本語を喋らせてみた

Android端末上に電子掲示板システムを構築する方法

Pythonを使ってAndroid端末を5分でリモートカメラにする方法

Android端末で青空プログラミング! SL4Aの導入からアプリケーションの作成・公開まで

アルゴリズムの素晴らしさに気付かせてくれたのはエラトステネスの篩だった

Pythonワンライナーで数独を解いてみた

日本全国ハンバーガーショップ分布地図

2次元セルオートマトンとエントロピー

小学3年生の授業参観でアルゴリズムに出会った

スーパーコンピュータとプログラミング言語

OAuthを使ってAndroidからPythonでTwitterに投稿する

C++0xでYコンビネータ

一行でテキストに含まれるURLをすべて短縮URLに変換するPythonスクリプト

コマンドラインで動作するOAuth対応TwitterクライアントをPythonで作ってみた

Google App EngineとSafe Browsing APIを利用して短縮URLチェッカーを作ってみた

一つのGoogle App Engineアプリケーションで複数のWaveボットを作成する

Android Scripting Environment (ASE) Python API簡易リファレンス

Google Waveを使わないと人生損する

Scratchでプログラミングする子供たち

Google Wave Robots API v2でボットを書き直してみた

AndroidからPythonでTwitterに投稿する

Android上でPython、Lua、JavaScriptなどを実行するスクリプティング環境が凄い

「ハッカーと画家」を読んで

Erlang基礎文法最速マスター

1. 基礎

対話環境

画面出力

コメント

変数の代入

スクリプトの実行

2. 数値

数値の表現

各種演算

インクリメントとデクリメント

3. リスト

リストの作成

リストの要素への参照

リストの個数

リストの操作

4. 文字列

文字列表現

文字列操作

比較演算子

5. 関数

6. 制御文

case文

if 文

for/while文

7. ファイル入出力

8. 平行プログラミング

知っておいた方がよい文法

真偽値

論理演算子

ビット演算子

map関数

filter関数

リスト内包表記

数値と文字列の変換

参考サイト

基礎文法最速マスターまとめサイト

Lua基礎文法最速マスター

1. 基礎

東北地方太平洋沖地震可視化地図