良いもの。悪いもの。

電子メールクライアントのMozilla Thunderbird 78でやっとOpenPGPの機能が標準搭載された。 とはいっても、78.0.1ではまだ不完全で、78.1.0でほぼ完成したようだが、デフォルトではOpenPGPは使えない。今後リリース予定の78.2からデフォルトで動作するようになるらしい。 78.1.0で使うためには、「オプション」の「一般」の一番下の「設定エディター...」を開き、 mail.openpgp.enable を true にする必要がある。 ただし、設定をいじると動作保証対象外になるので、自己責任で対応すること。 今回の動作検証ではWindows 10上で実行させた 64ビット版Thunderbird 78.1.0 を使っている。 設定を済ませたら、「エンドツーエンド暗号化」のOpenPGPの「Add Key...」で秘密鍵をインポートもしくは作成する。 GnuPG などですでに鍵を作っているのであれば、それをエクスポートして読み込ませるだけだ。 公開鍵をインポートする場合、「OpenPGP Key Manager」の「Import Public Key From File」で対応可能だ。 早速、メールを作成し、「セキュリティ」から「暗号化が必要」と「このメッセージにデジタル署名」を選択して送信する。 メッセージは自分自身に送っているのであまり意味はないが、それぞれの機能がきちんと動作していることを確認することはできる。 この通り、暗号化とデジタル署名ができていることを確認できた。 PGPは昔からあるが、自分の周りでは使われているのをほとんど見たことがない。 Thunderbirdに標準搭載されたのを機に、広まってくれないだろうか。

現代では簡単に写真や動画を撮ることができる。それは、個人情報の流出と直結する。 特に動画に映った人物について、匿名化することはなかなかに大変だ。 目線やモザイク、塗りつぶしなどで顔を隠すケースをよく見かけるが、個人的にはちょっと微妙。犯罪臭がするし、淫靡な印象を与えてしまう。 ほかにもアイコンやシンボルで顔を隠したりすることができるツールなどもあるが、ちょっと自分好みではないし、何よりオリジナリティに欠ける。 そこで、古典的でもあり、未来的でもある、そして新しい、そんな顔映像匿名化を考えてみた。 匿名化するにあたって、まずは顔、特に目と鼻を検出できなくてはならない。 幸いなことに、 Keypoint R-CNN モデルを使えばそれが可能になる。 利用するだけならば、PyTorchのチュートリアルレベルの知識を持っていれば十分。 そして、コードはできるだけシンプルで分かりやすく、その場ですぐに書けてしまえることが重要だ。 これは大事なことで、たとえ面白そうな技術でも、それを体験できるまでに時間がかかれば多くの人は興味を失ってしまう。 体験して理解さえすれば、達成感と面白さを実感できるし、次を目指す動機づけになる。 閑話休題。さて、今回作るのは、動画の顔画像の匿名化だ。そして、古典的で未来的、何のことだと思われるかもしれないが、使っている技術は新しく、できたものは懐かしいということ。 具体的には、顔画像に細工をして「へのへのもへじ」にしてしまうのだ。とはいっても、目と鼻を置き換えるだけなので「のもの」を使う。 江戸時代中期にはよく知られていたという「へのへのもへじ」は、まさに古典的で懐かしいと言えるだろう。 作成したコードは foota / nomono-anonymizer にある。使い方は次の通り。 $ python nomono-anonymizer.py [入力動画ファイル名] [出力動画ファイル名] 動画はフレームごとに画像データとして処理され、それを事前学習した Keypoint R-CNN のモデルに推論をさせる。 モデルは画像データに対し人物領域を検出し、それに対して目、鼻、耳、肩、肘など、17のキーポイントを推定する。 今回は、右目・左目・鼻の3つのキーポイントを利用し、取得した座標に対して、画像データ上に「のもの」の文字...

今の世の中、そこら中に人工知能(AI)と呼ばれるシステムがあふれている。特にディープラーニングによるニューラルネットワークモデルを使ったシステムは高度な処理が可能であると広く考えられているようだ。では、それを使ったAIはどのようにこの世界を見ているのだろうか。 ディープラーニングで得られる特徴を含んだ値(特徴マップ)がAIの視覚と呼べるだろう。AIについて扱った教材では、ディープラーニングにより学習されたニューラルネットワークモデルの特徴マップを例示していることがあるが、特定の画像に対する特定の特徴の一部を載せているだけなので、AIがどのように世界を見ているのか、それだけで判断するのは難しい。 そこで、任意の動画に対してニューラルネットワークモデルを使って特徴マップを映像化することにした。今回、対象とするネットワークアーキテクチャは、 AlexNet と VGG19 だ。それぞれ2012年と2014に公表されており、どちらのアーキテクチャも ImageNet の分類できわめて高い性能を誇っている。 特徴マップの映像化を行うにあたって、まずは動画処理のために ffmpeg-python を利用することにした。これは、名前からもわかるようにPythonのFFmpegラッパーで、動画を扱うのにはかなり便利なライブラリとなっている。次に、AlexNetとVGG19を利用するために PyTorch とそのパッケージである torchvision を利用した。torchvisionにはAlexNetとVGG19の学習済みネットワークモデルも用意されている。使い方は簡単で、例えばAlexNetなら、以下のコードでネットワークモデルをすぐに使うことができる。 model = torchvision.models.alexnet(pretrained=True) 今回は学習をせず用意されているモデルを使うだけなので、推論モードにして勾配計算をしないように model.eval() と torch.set_grad_enabled(False) を記述しておく。 処理の流れは次の通り。入力データとして適当な動画ファイルを用意する。動画ファイルが読み込まれると、ffmpegによりフレーム画像を一枚ずつ読み出し、それをnumpyで配列に変換。変換され...

最近ずっとリモートワークだったので、これを機に書斎の整理整頓を行った。段ボールに無造作に放り込まれたPC関連機器や電子ガジェットを漁っていると、2004年10月に発売されたソニーの非接触型ICカードリーダPaSoRi RC-S320が出てきた。2008年3月に購入したので実に12年以上前のモノだ。 このまま捨て置くのは勿体ないし、ちょっと興味をそそられたので、 以前のブログ記事 に上げた コード がちゃんと使えるか、最近新調したWindows 10搭載PCで確認してみた。 当然、ドライバが入っていないのでそのままでは動かない。早速最新のドライバを入れようと思ったが、実はRC-S320はとっくに販売終了していて、新しいPaSoRiとはドライバが違う。まあ、そりゃそうか。調べたところ古いドライバ( NFCポートソフトウェア Version 5.4.8.6 )を落としてくれば動くことが分かった。動作確認環境はWindows 8.1までみたいだけど、まあ、大丈夫でしょ。 ドライバを入れたところ、デバイスマネージャーでちゃんと認識された。よし、これで準備OKだ。動かしてみよう! …いやまてよ? 今時Python2は許されない。ということでPython3のコードにちょこちょこっと修正して、これで良し。PaSoRiの上にモバイルSuica機能を搭載したAndroid端末を置いて、さっそく実行 python read_felica.py (ｶﾀｶﾀｶﾀｯﾀｰﾝ!) OSError: [WinError 193] %1 は有効な Win32 アプリケーションではありません。 あ、これよく見るやつだ。実行パス名にスペースとか入ってちゃんと認識しないやつだ。と思ったけど調べてみるとパス名は問題ないみたい。あとは、そうそう、64ビット環境で32ビットのライブラリ使ったとか。それだ! 実行環境はPython3の64ビット版なので読み込むDLLも64ビットじゃないと。でも、利用させてもらった felicalib は32ビット版しかないみたい。 0.4.3から64ビット版にも対応する みたいだけど、最新版の0.4.2が2008年6月リリースでそれ以降出ていないということはもう出ない可能性が高い。ちなみにソニーのドライバは当時64ビット版が存在しなかったみたいだけど、今...

職場でSlackを利用している。なかなか使いやすいし便利だ。しかし、技術者としては与えられた機能を利用するだけではやはり満足できない。自分好みの道具を作りたい。 というわけで、単なるチャットツールとして使うSlackでは物足りなくなったので、Slackのボット(bot)をPythonで作ってみることにした。Hubotのようなボット用フレームワークも利用可能だが、SlackのAPIをガシガシ制御する感じにしたかったので、 Slack Real Time Messaging API をPythonから制御してSlackと連携した。今回は、書き込んだ数字を素因数分解するボットを作ってみた。 まずは、Slack用のボットを利用する準備をする。 Slack API にアクセスして、 Bot users をクリックし、Custom bot usersにある creating a new bot user のリンクからBotsのページを開く。 名前(ここでは @prime_decomposition)を入力したらAdd bot integrationボタンをクリックする。 Integration Settingsの画面ではAPI Tokenが表示されており、ボットのスクリプトでこれを利用する。あとは好みに応じてアイコンの変更やボットの説明を記述しておく。今回のボットでは、デフォルトのフェイスマークに用意してあるロボットのアイコンを使い、説明文は「素因数分解をするよ!」とした。あとは、Save Integrationのボタンをクリックして設定を保存する。 ボットの準備ができたら、それをSlackへメンバーとして加える。ボットを参加させたいチャンネル(ここの画像では #general だが #random に参加させたい場合は #random を選択すること)のChannel Settings(歯車のアイコン)から、Invite team members to join...を選択する。先ほど設定したボットがメンバーとして表示されているのでそれを選ぶ。これで下準備は完了だ。 次にPythonを使ってボット用スクリプトを作成する。目的は、Slack上で誰かが数字を書き込んだ際に、それを取得して素因数分解をすること。そのためには、Slackに書き...

しばらく前に、PythonのWebフレームワークである Pyramid を利用した。これがなかなか良くできており、Android端末上でも動かしてみたくなったので載せてみた。 ところで、自分が利用しているキャリアはドコモなんだけど、 spモード だとグローバルIPが割り振られないので外部から端末にアクセスできない。なので、spモードを契約せずに、 mopera U を利用している。mopera UであればグローバルIPが割り振られるのでアクセスすることができるからだ。このためだけに、spモードにせず、mopera Uにしていると言っても過言ではない。 閑話休題。まず、Pyramidを動作させるにはAndroid端末用のPython環境である SL4A を入れる必要がある。次にPyramidを入れるのだが、必要なモジュールなどが複数あるのでそれも一緒に入れる。一応、Hello Worldプログラムを動かすのに必要なものはすべて挙げたが、もし足りない場合は実行時に何が足りないかエラー表示が出るので、それを参考に入れて欲しい。また、 Android SDK が導入されていることを前提にしている。 まず、Android端末にシェルで入ってプログラムを展開するディレクトリを準備する。環境に合わせてディレクトリは読み替えて欲しい。 > adb shell * daemon not running. starting it now on port 5037 * * daemon started successfully * $ cd /sdcard/sl4a/scripts $ mkdir pyramid $ exit 適当なディレクトリで以下のプログラム・モジュールをPC側で展開する。 pyramid-master.zip translationstring-1.3.tar.gz venusian-1.0.tar.gz WebOb-1.4.tar.gz zope.deprecation-4.1.2.tar.gz zope.interface-4.1.2.tar.gz repoze.lru-0.6.tar.gz PC側からAndroid端末にプログラム・モジュールをコピーする。 > adb push pyramid /...

久々のブログ更新。書きたいときに書くというスタンスです。最近、会社でも技術ブログを立ち上げたので、そちらで書いても良いかも。 今回はIRCボットの作成について書いてみる。しばらく前から社内IRCで技術関連の雑談用チャンネルを利用している。技術系のメーリングリストもあるのだけど、わざわざメールで話題にするようなことでもない、軽い内容を気軽に議論できる場が欲しかったので有志で立ち上げた。IT企業にとって技術的な雑談をできる場はとても大事だと思う。 素のIRCの場合、発言内容がサーバに保存されず、途中から参加しても話題についていけないという問題が出たので、適当なボットで対応することにしたが、やはりエンジニアがメインの会社なのだからボットも自作が基本でしょ、ということでPythonで作ってみた。まあ、作ったといっても「 Python でシンプルな IRC クライアントを作成する 」のサイトを参考にさせてもらったのでスクラッチから作成したわけではない。 コマンド techlog: を入れると、その日の発言がボットからのtalkで返される。ただ、最初は1日分の発言しか取れない仕様だったので、日を跨ぐとその前の発言が取得できないし、一時的にチャットを抜けた分のログが欲しいだけでも強制的に1日分の発言を取得してしまう。 そこで、SQLite3を使ってユーザ毎にログイン・ログアウト時刻を管理して、ログアウトしてからログインするまでの発言を取得できるように変更することにした。新規に参加したメンバーでも自動的にデータベースに登録される。せっかくユーザの時刻情報があるのだから、 techtime: , techtimeall: というコマンドを作って、それぞれ自分の滞在時間、ユーザ全員分の滞在時間も取得できるようにしてみた。 IRCサーバ上で以下のコマンドを実行すると、IRCにボットが常駐する。 $ ./irc_bot.py > irc_bot.log & ソースコードは以下の通り。 そこそこ社内IRCも使えるようになったのだが、最近、別プロジェクトで利用を始めた Slack がかなり便利だったので、そこに技術系チャンネルを作ったところ、ほとんどのメンバーがSlackに流れてしまった…。次は Slackでボット作成 かなぁ。

スピログラフに初めて触れたのは小学校に上がる前だった。当時はそれがスピログラフという名称であることを知らず、輪っかをぐるぐる回して綺麗な模様を描ける道具としてお気に入りの玩具になっていた。自分はマンデルブロ集合やジュリア集合のような数学的に表現できる図形や模様にともて魅力を感じるのだが、幼少のころのスピログラフがその切っ掛けだったのかもしれない。 長方形の定規に大きさの異なる3枚の歯車が付属しており、そして2つの円がくり抜かれている。さらに、矢印、五角形、半円などの型が子供心をくすぐったものだ。因みに、歯車と円に付いている歯数は刻印されており、3つの歯車はそれぞれ36、52、63、円の方は96、105の歯を持っている。 幼少のころ以来、スピログラフを見かけることはなかったのだが、最近になって100円ショップでも売られているという噂を聞き、少し探ってみた。近くの100円ショップでは扱っていなかったが、「デザイン定規」という名称でネットで78円で売っていたので思わず購入してしまった(当然だが送料のほうが高くついた…)。 スピログラフは一般的には内トロコイド(hypotrochoid; 内余擺線)といい、以下の式で表現できる(Wikipediaより)。 定円の半径 r c 、動円の半径 r m 、描画点の半径 r d とし、下図では、それぞれ、青、緑、赤の線で示している。そして、回転角を θとした軌跡がスピログラフの模様となる。 スピログラフでは半径よりも、円周の歯の数で示した方が分かりやすいだろう。円周と半径の比は変わらないのだから、歯の数の比がそのまま半径の比となる。例えば定円の歯が30で動円の歯が10ならば、 r c : r m =3:1ということだ。 さて、幼少のころはこんなに綺麗な模様が数式で表現できるなどと夢にも思わなかったわけだが、今はそれを理解し、コンピュータを使って自由に描くことができる。コンピュータであれば、動円が定円の外側に来る外トコロイド(epitrochoid; 外余擺線)も描くことができるし、描画点を動円の外に出すことも思いのままだ。 せっかくコンピュータを使って簡単に表示できるようになったというのに、プログラムを組むことが難しくては意味がない。しかし、Python+matplotlibであれば簡単に...

2013年を終え、2014年を迎えた。さて、昨年と今年の違いは何か? 昨年のブログで2013を素因数分解すると「3×11×61」になることを示したが、2014は「2×19×53」となる。そして差を取ると、「2-3, 19-11, 53-61」、つまり、「-1, 8, -8」となり、1月、8月が昨年と今年の差であることがわかる。そして、負を示した1月は運気が下がり、正と負を持つ8月は運気の上下があるに違いない! 因みに2013+2014=4027が素数にあることから、昨年から今年にかけて行っていることは、これまでとは違ったユニークな内容となる! …などと、MMRばりなことを書けるぐらいの余裕を持ちつつ、今年一年を頑張りたいと思いますので、本年もどうぞよろしくお願いいたします。 以下にPython+ NZMATH を使った素因数分解を示す。 >>> import nzmath.factor.methods as methods >>> methods.factor(2013) [(3, 1), (11, 1), (61, 1)] >>> methods.factor(2014) [(2, 1), (19, 1), (53, 1)] >>> methods.factor(2013+2014) [(4027, 1)]

先週ぐらいから クッキークリッカー(Cookie Clicker) というJavaScriptを使ったブラウザゲームが流行っている。クリックするだけのゲームと聞いて、最初はあまり興味を持てなかったのだが、自分の周りであまりにもやっている人が多いので少し遊んでみることにした。 クッキークリッカーを簡単に説明すると、まずはクリックすることでクッキーを作り、作ったクッキーを使ってクッキーの生産性を高めるためのアップグレードやアイテムを購入し、たまに出現するゴールデンクッキー(Golden Cookie)をクリックすることでさらに多量のクッキーが得られるので、それらを駆使してできるだけたくさんのクッキーを作るというゲームだ。 このようにとてもシンプルなゲームなのだが、最初はちまちまとしか作れなかったクッキーが徐々に増えていき、様々なアイテムやイベントを通すことで、終盤では毎秒数千億クッキーを作れるというところに人々を惹きつける魅力があるらしい。しかし、自分は「人間の代わりにプログラムを働かせることでどこまで効率が良くなるか」という目的のために自動化プログラムを作成したくなった。コンピュータは人間を楽にさせるために存在するべきだ。 このゲームはJavaScriptで作られており、そのコードや変数を修正すれば簡単にチートを行うことができる。しかし、自分はそれについては全く興味がない。元のシステムには全く手を入れずに人間が操作する部分のみをプログラムで最適化したいのだ。 まず、最初に考えついたのは自動クリックだ。これは様々なツールが世に溢れているのでそれを使っても良いのだが、プログラマだったら、このぐらいは自分で作りたい。そこで、Pythonと pymouse を使って自動クリックプログラムを作成した。これで、毎秒100～200クリックすることができるようになった。これ以上の速度にするとブラウザがついて行けずプチフリーズを頻繁に起こし逆に生産性が落ちてしまう。因みに画面上のエフェクトなどは設定で消しておくほうが良いだろう。 次に、ゴールデンクッキーへの対処だ。ゴールデンクッキーはランダムな間隔でブラウザ上のどこかに出現する。そのクッキーをクリックすると溜まっているクッキーの1割分の枚数が貰えたり、一定時間現在の7倍の効率でクッキーを焼けるようになったりする。...

世の中のことをもっと知るにはどうしたら良いだろうと思うときがある。世の中の多くの事柄はログやデータに落とされる。Googleなどの検索サイトは良い例だろう。さて、そのログやデータをどうすれば良いのか? 多くの場合、視覚化が有効な手段となる。 まずは身の回りの日常的なデータやログを何とかしたい。ただ、日常のデータを視覚化するのに数十行以上のコードは書きたくない。まるで息をするかのごとく自然に視覚化を行いたいのだ。そのためには1～2行、長くて数行で済ませることが必要だ。そこでPythonとmatplotlibを使う。加えて、IPythonがあればなお良い。IPythonの導入については以前のブログ記事である IPythonの埋め込みプロットが素晴らしい を参考にして欲しい。 まずは事前にnumpyとmatplotlibをインポートしておく。できればscipyも。 >>> from numpy import * >>> from pylab import * 短いコードで視覚化を行うためには、Pythonの内包表記は必須だ。例えば、5, 2, 1, 5, 8をデータとするグラフを書きたいのならIPythonを使って以下の1行で実現できる。 >>> plot([5, 2, 1, 5, 8]) 数値が行ごとにinput.txtというファイルに書かれていた場合は以下の通り。 >>> plot([int(x) for x in file("input.txt")]) map関数を使えばもっとスマートに書ける。ファイル内の数値を文字列として配列で読み込み、それらの文字列をmap関数によりintで整数に変換する。 >>> plot(map(int, file("input.txt"))) さて、ログが2次元で書かれていた場合はどうするのか。例えば以下のデータがinput.txtに書かれていたとする。 2, 2.5 5, 6.2 6, 3.6 7, 6.3 10, 1.9 この場合、以下のようにすればプロットできる。ファイルから行ごとの文字列を読み出して、それを","を区切りとしてリス...

Pythonでは timeitモジュール を使って簡単に実行時間を計測できる。以下に示すコードはPythonでは一般的なコードだと思う。 たらい回し関数(竹内関数) と階乗を求める関数だ。これを実行した時の時間計測、さらにコードに含まれている関数の実行時間を簡単に測るにはどうすればよいか。 ここでtimeitモジュールが利用できる。まず、Pythonシェル環境では以下の通り。 main関数の測定は次のように行う。stmtで時間計測したい関数を指定して、setupで最初の1回だけ実行する文を指定する。numberは実行する回数となっている。正確を期するなら複数回を指定するべきだろう。 >>> import timeit >>> timeit.timeit(stmt='test_timeit.main()', setup='import test_timeit', number=1) 12 3628800 2.663659573618423 たらい回し関数(tarai)のみの測定。 >>> timeit.timeit(stmt='test_timeit.tarai(12, 6, 0)', setup='import test_timeit', number=1) 2.6390463109480637 階乗関数(factorial)のみの測定。100万回実行。 >>> timeit.timeit(stmt='test_timeit.factorial(10)', setup='import test_timeit', number=1000000) 2.3606330638673825 さらに、コマンドラインでの計測も可能だ。 main関数の測定。コマンドオプションの-sは最初に1回だけ実行する文、-nは実行する文の回数、-rはタイマのリピート数になっている。 $ python -m timeit -n 1 -r 1 -s "import test_timeit" "test_timeit.main()" 12 362880...

あけましておめでとうございます。 新年を迎えて、ふと、今年の西暦である2013を素因数分解したらどんな数に分解されるのか気になったので考えてみた。桁をすべて足し合わせると 2+0+1+3=6 と3の倍数になり、3で割り切れることは明白だ。3で割ると671となる。671に対し桁を一つ飛ばしにして足し合わせた数の差が (6+1)-7=0 で11の倍数(0を含む)なので11で割り切れることも簡単にわかる。671を11で割ると61の素数となる。つまり、2013の素因数分解は 3×11×61 となる。 大きな素数同士による合成数の素因数分解は非常に困難であることが知られている。この性質を利用して多くの暗号アルゴリズムで大きな素数による合成数が利用されている。現在のところ、素因数分解アルゴリズムとしては、楕円曲線法(ECM; Elliptic Curve Method)や複数多項式二次ふるい法(MPQS; Multiple Polynomial Quadratic Sieve)がよく使われているらしい。で、手軽にこれらを利用できるライブラリがないかと軽く調べたところ NZMATH(ニジマス) という数論のためのPythonモジュールがあることを知ったので、早速インストールして使ってみた。 ところで、大きな素数といえばメルセンヌ素数が有名だが、 マラン・メルセンヌ は、2 n -1 に対してnが257以下のとき、n = 2, 3, 5, 7, 13, 17, 19, 31, 67, 127, 257のときにのみ素数となると主張した。しかし、一部に間違いがあり、n = 61, 89, 107のときも素数であり、また、n = 67, 257は素数ではなく合成数であった。 そこで、誤って素数としていたn = 67のときの 147573952589676412927 について楕円曲線法(ECM)で解かせると、すぐに 193707721×761838257287 と結果が出力された。 >>> import nzmath.factor.methods as methods >>> methods.factor(147573952589676412927, method="ecm") [(193707721L, 1),...

先日、「 『フカシギの数え方』 おねえさんといっしょ！ みんなで数えてみよう！ 」という動画を見た。格子状のマスの左上から右下までの経路が何通りあるのかを調べて、格子が多くなればなるほど組み合わせの数が爆発的に増えることを教えてくれる動画だ。これは 自己回避歩行(Self-avoiding walk) と呼ばれている問題らしい。 これだけ聞いてもそれほどインパクトはないのだが、動画に出てくるおねえさんの経路を調べあげる執念がもの凄く、ネット上でも結構な話題になっている。執念と言うよりも狂気に近い。しかし、話題になった割には動画内で言及されている高速なアルゴリズムを実装したという話を聞かなかったので、自分で確かめることにした。 動画のおねえさんは深さ優先探索によるプログラムを使っていると思われるが、それだとスパコンを使っても10×10マスの格子を解くのに25万年も掛かってしまう。そこで、高速化のためにゼロサプレス型二分決定グラフ(ZDD; Zero-Suppressed Binary Decision Diagram)と呼ばれるアルゴリズムを利用することにした。このアルゴリズムを開発したのは北大の 湊先生 で、ZDDによりすべての経路を見つけ出すアルゴリズムとして クヌース先生 のSIMPATHを使った。ZDDについてはクヌース先生も強い関心を持っていて、 The Art of Computer Programming Volume 4, Fascicle 1 (TAOCP 4-1)ではBDD/ZDDの詳細な解説を読むことができる。演習問題の解説だけで書籍の半分を使っていることからしても気合の入れようがわかるだろう。 実際に自分のノートPCでZDDアルゴリズムを使ったコードを走らせたら、ほんの10秒程度で10×10マスの問題を解いてしまった。おねえさんがスパコンで25万年かかった問題をノートPCでたった10秒である。約8千億倍の高速化だ。これだけ劇的に変わるとやっぱり楽しい。そして、アルゴリズムの重要性を再認識させられた。 さて、以下におねえさんが利用したであろう自作の深さ優先探索(DFS)プログラムと高速な解法であるZDDアルゴリズムの両方を載せておく。ZDDについては4つのプログラムを1つのPythonスクリプトで統合している。これは、クヌー...

5年ほど前、このブログで 虚数のテトレーション という記事を書いたことがある。 テトレーション(tetration) とは、自らのべき乗を指定された回数反復する演算のことで、 n a と表現する。 3 5 の場合、5 5 5 = 1.911×10 2185 となる。Pythonの関数で表現すれば以下のようになる。 以前の記事では、 ∞ i が 0.43828+0.36059 i に収束することを見つけたのだが、今回はそれに関連したフラクタルについて紹介したい。 テトレーション n a の a には複素数を指定することができる。このとき、 a = x + yi として、それを複素平面に置く。ここで正の整数 n を大きくしていき、発散と判定された n に対応した色で平面を色分けする。発散しない場合、予め決めておいた n の上限値を使う。これで得られる図を テトレーション・フラクタル(tetration fractal) と呼ぶ。 n (x + yi) = a + bi としたとき、 n +1 (x + yi) = a' + b'i は以下のように計算できる。 Pythonでの実装は ActiveSate Code に Tetration Fractal として載っている。今回はこれを少し修正したコード、C++で書いたコード、更にTBBで並列化したコードを用意して、それらの実行速度のベンチマークを取ってみた。 Python C++ C++ with TBB 258.732秒 16.999秒 0.976秒 ここで、複素平面の領域は(-1.5, 0)-(-0.75, 0.75)であり、最大繰り返し数は256としている。画像の大きさは1,024×1,024とした。実行環境はIntel Xeon X5650の2CPUで、12コア・24スレッドとなっている。 以下に、ソースコードを示す。詳細についてはコードを読んでいただきたい。 Pythonによる実装: % ./tetration.py tetration.png -1.5 0.0 0.75 0.75 1024 1024 C++による実装: % ...

先日、 Tokyo.SciPy #3 に参加して、SciPyの生みの親である Travis Olipant氏のセッション を聞いた。その時に最近の IPython では埋め込みプロットができることを知ったので早速入れてみたところ、これがとてもクールでカッコよかったのでここで紹介したい。 埋め込みプロットはIPythonのバージョン0.11からできるようになっている。ただ、自分が使っているLinux環境では普通に持ってくるとバージョン0.10が入ってしまうので使えない。そこで、IPythonの公式サイトから最新版のバージョン0.12を持ってきて入れてみた。 ただ、埋め込みプロットができるのはターミナル版ではなくQt版のシェルなので、それに関連するライブラリなども一緒に入れなくてはならない。IPythonの起動時に何々のライブラリが足りないとかいろいろと文句を言われるが、足りないものをyumなりapt-getなりソースコードをコンパイルなりして順次入れていけば使えるようになると思う。 あと、IPythonの設定ファイルの構成が0.10から大きく変わった。以前は .ipython/ 内の pythonrc を利用していたのだが、それがなくなって、代わりに .ipython/profile_default/ 内の ipython_config.py と ipython_qtconsole_config.py が使われるようになった。デフォルトの設定ファイルは以下のコマンドで作ることができる。 $ ipython profile create そして、埋め込みプロットを使うためのQt版IPythonの起動コマンドは以下の通り。 $ ipython qtconsole --pylab=inline これでQt版シェルが立ち上がって埋め込みプロットを表示できるようになる。 せっかくなので実際に埋め込みプロットを使ってみる。ここでは自分のお気に入りのマンデルブロ集合をプロットしてみた。因みに、シェル上での複数行のソースコードの編集も改良されたので入力がかなり楽になった。冒頭にスクリーンショットを貼っておく。 rangex = arange(-2.0, 1.0, 0.01) rangey = arange(-1.0, 1.0, 0.01) (X, ...

最近、HTML5に触れる機会があり、その良さが何となく伝わってきたので、何かしら簡単なコードを書いてみたくなった。そこで、ちっちゃいけどリッチ、というギャップを楽しむためにAndroid端末を使うことにした。具体的には、Android端末を SL4A で ウェブサーバにして 、HTML5をインターフェイスにしたお絵かきBBSをPythonで書いてみた。 BBSでは絵とテキストを扱うことができて、それらはAndroid端末上でSQLiteのデータベースで管理される。利用者の利便を考えて、名前などはクッキーで保存する。3G回線や無線LANなどで接続することを考慮して、IPアドレスも取得できるようにした。また、書き込み時にサーバのAndroid端末が振動して書き込みがあったことを知らせてくれる。因みに、NTTドコモの3G回線で使うためには、グローバルIPが振られるmopera Uなどのサービスが必要で、spモードでは利用できない。 実際に作ってみたプログラムのスクリーンショットを冒頭に入れてみた。必要最低限の機能しかないが、それでも文章と画像を保存できるちゃんとした掲示板だ。草の根BBSのころを考えると隔世の感がある。 以下に今回作成したソースコードを載せておく。こんな短いコードでもちゃんと機能するのが不思議な感じだ。 image_bbs.py # -*- coding: utf-8 -*- import sys,os,cgi,sqlite3,datetime import socket,fcntl from wsgiref.simple_server import make_server import android droid=android.Android() LIMIT=10 # 最大表示記事数. DB_FILE='/sdcard/image_bbs.sqlite' P=8080 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, ima...

今年は2012年です。 bool leap_year(int y) { return !(y%4)^!(y%100)^!(y%400); } そして、 leap_year(2012) が真となるので閏年です。平年と比べて一日増えるわけですが、その一日たりとも無駄にしない充実した一年にしたいと思います。 本年もどうぞ宜しくお願い申し上げます。

マチンの公式 で円周率を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)->...

社内で好きなコンピュータ言語と嫌いなコンピュータ言語のアンケートを取ってみた。ことの発端は 自分のツイート なのだが、思いがけず賛同を得ることができたので、実際にアンケートを社内で行うことにしたのだ。各自で社内Wikiを編集してもらってもよかったのだけど、プログラムを作る会社でもあるし、投票システムに興味もあったので、Google App Engine (GAE)で作ってみることにした。以前にGAEで掲示板などを作成していたので、それらを流用して時間をかけずにすぐに仕上げることができた。以下のリンクから実際に投票できる。 好きな・嫌いなコンピュータ言語のアンケート 表示されているコンピュータ言語一覧から、最も好きな言語と最も嫌いな言語をそれぞれ一つずつ、それ以外にも好きな言語や嫌いな言語があれば、それらも選択(複数可)する。投票したい言語が一覧にない場合は「言語の追加」で自由に追加できるようになっている。言語を選択して投票ボタンを押すと、投票数とそのグラフが更新される。表示されるグラフには、「最も好きな・最も嫌いな言語」と「好きな・嫌いな言語」の2つがあり、青のグラフが「好きな言語」、赤のグラフが「嫌いな言語」を表している。「好きな・嫌いな言語」のグラフについては、「最も好きな・最も嫌いな言語」と「好きな・嫌いな言語」を足し合わせた票数となっている。 また、コメントも投稿できるようになっていて、自分の好きな言語を啓蒙するのも良し、嫌いな言語について文句を言うのもアリだ。自由に書き込める。 現時点での社内での票は以下のグラフに示す通りで、幅広く票が入っているように思う。傾向としては、C, C++, C#, ASM, Python, Rubyあたりが人気で、Visual Basic, Java, Perlが不人気みたいだ。 今回作成したコードの簡単な説明を書いておく。上述の「好きな・嫌いなコンピュータ言語」だけでなく、初期変数を設定することで、「好きな・嫌いな動物」「好きな・嫌いな食べ物」などのように、簡単に任意のアンケートを作成できるようになっている。グラフについては Google Chart API を利用しているが、1,000ピクセルを超えることができないので、表示数を1,000ピクセル以内に抑える処理を入れている。また、頻繁にデータベ...