1024によるエントリー一覧

Android 指リスト編については、既に Haskell編、 Python編、 Python編(その2) が存在しているが、今度は C++ 編である。

が、 C++ では Haskell や Python のように、 interactive shell でお遊びをするあたりはさすがに再現できないので、 代わりに実行速度にこだわってみたい。

実行速度にこだわるというからには、 Python やら Haskell やらがどの程度の実行速度なのかをあらかじめ知っておく必要がある。 以前の記事では interactive shell で遊ぶために全てのパターンを列挙していたが、 今回については単純化のためパターン数の計算のみについて考えることとし、 最初から単純にパターン数を数え上げる方式にプログラムを若干変更の上計測する。

実行時間計測：Python

ベースのプログラムはPython編(その2)を用い、 nextList 関数を数え上げのみに限定しておく。

def nextList(i, rem):
    return sum(
        (nextList(s, rem - set([s])) for s in candidate(i, rem)),
        1 if len(rem) <= 5 else 0)

print(nextList(0, frozenset(range(1, 10))))

time コマンドで実行にかかった時間を計測する。

% time python3 flistnum.py
389112
python3 flistnum.py  2.65s user 0.02s system 99% cpu 2.667 total
% time python3 flistnum.py
389112
python3 flistnum.py  2.66s user 0.00s system 99% cpu 2.659 total
% time python3 flistnum.py
389112
python3 flistnum.py  2.65s user 0.01s system 99% cpu 2.657 total

2.6秒強程度といったところ。

実行時間計測：Haskell

ベースのプログラムはもちろんHaskell編のものを使用する。 Python のときと同じように nextList 関数を数え上げのみに限定し、

nextList :: Int -> [Int] -> Int
nextList n rem =
    foldr (+) (if length rem <= 5 then 1 else 0)
    [nextList s (rem \\ [s]) | s <- candidate n rem]

main = print $ nextList 0 [1..9]

実行速度最適化オプション -O2 もつけてコンパイル後、計測する。

% time ./flistnum
389112
./flistnum  0.10s user 0.00s system 101% cpu 0.102 total
% time ./flistnum
389112
./flistnum  0.09s user 0.01s system 99% cpu 0.102 total
% time ./flistnum
389112
./flistnum  0.10s user 0.00s system 101% cpu 0.101 total

ちょっ...、わずか 0.1 秒...。

やるな、Haskell。 だが今回使うのは何しろ C++ である。コレに勝ってみせねばなるまい。

C++ の本当の実力を見せてやる！

えっ。Python での実装はもうあるじゃん...。まったくもって今更何を言いだすのか。 "There's Only One Way To Do It" を掲げる Python にもかかわらず「その2」などとは。

とはいうものの、いかに Python といえども、やはりやり方をひとつに絞ることはできはしない。 比較的 Python らしい、ジェネレータを使用したやりかたは既に示されている。 そこで本記事では、もうひとつのやり方として元々の Haskell版 のクローンを Python で実装してみようと思う。

なお本記事では Python 3.2 を使用する。

何？ まだ Python 2 系を使ってる？ もう古いので早急に乗り換えを検討されるとよろしい。

Android 機にはロック機構として暗証番号やパスワードの他に、指リストというヤツがある。 テンキー状に9個のボタンが配置され、そのボタンを一筆書きでなぞって繋いでいく。 最低 4 個のボタンを繋ぎ(最大はもちろん 9 個)、そのパターンによって認証するシステムだ。

パターンというのは人間にとってそれなりに覚えやすくもあり、 Android 機を使っている人は端末ロックを指リストにしている人も多いだろう。 指紋跡でパターンがバレる、なんて話もあるにはあるが...、 それはさておき、純粋にパターン数として、どのくらいあるのだろうか？

9 個のボタンの単純な組み合わせであれば、Σ(i=4 to 9) P(9,i) = 985,824 通りで、約 19.9 bit。 しかし指リストは選択順によって選択できないパターンが存在する。 例えば、指リストのボタン位置をテンキーに見立てたとして、 4 -> 6 -> 5 の順では選択できない。 なぜなら、4 -> 6 で一筆書きでなぞろうとしたら、 5 の位置を通らざるを得ないからだ。 従って、上記パターンは数えすぎであり、もっと少ないはずである。 別の方法で数え上げた方が良さそうだ。 選択したボタンから、次に移ることができるボタン数を調べていくのがいいだろうか。

さすがにこれだけの数を人間が数え上げるのは無茶があるので、計算機にやらせよう。

まあこんなものは Perl でも Python でも Ruby でも Javascript でも、 いっそのこと C でも C++ でもいいのだが、こんなことをするのにうってつけの言語がある。

Haskell だ。

本記事では GHC を使う。実行結果も載せておくことにはするが、 ぜひ手元に GHC をインストールして実際に試してみて欲しい。

本件はMercurialでアレを元に戻す108の方法に含まれるような内容ではあるのだが、非常に長くなるので独立した記事にしてみたい。QA形式に倣うのならこんな感じだろうか。

問題：誤ってブランチをマージしてしまった。しかしマージは公開され、それぞれのブランチには新しい修正も加えられている。それでもマージをなかったことにしたい。

ちょっと長くなる。サンプルのリポジトリを用意しつつ実際に実行できるようにしておいたので、読むだけでなくぜひ手元で実行してみてほしい。そうそう、途中 log -G と strip コマンドを使用しているので、graphlog と mq の extension は ON にしておいてほしい。具体的には hgrc に次の行を書いておく。

[extensions]
graphlog =
mq =

あと、各コマンドの結果は煩雑なので、blog に記載するにあたっていろいろとそぎ落としてある(特に log -G)。実際の実行結果は自分で確かめて欲しい。

問. PHPで、配列の先頭要素、もしくは末尾要素を参照するにはどのようにすればよいか。

Mercurialリポジトリのバックアップだって？

分散型なんでしょ。要らないじゃん。

OK、もちろんそういう観点はある。Mercurialは分散型なので、該当プロジェクトが熱いうちは、かなり障害に強い。中央リポジトリと言ったところで、それは単にプロジェクト内でそのリポジトリを中央と「見做して」いるだけで、基本的には他のリポジトリと変わらないからだ。せいぜい、コミットメールの設定等が行われているくらいだろう。だから、中央リポジトリサーバーがダウンしても気にせず作業を続けられるし、プロジェクトの誰かのリポジトリを改めて「中央と見做せ」ば良い。復旧も簡単だ。

だから、Subversionほどにはバックアップを気にする必要はない。

それでも、Mercurialで管理している情報の重要さを鑑みれば、バックアップはあるに越したことはない。ことバックアップが重要になってくるのは、前述「該当プロジェクトが熱いうちは」という前提が崩れたときにある。開発を終え、少人数の保守要員が残り、保守案件も下火になり、メンバーもローカルPCを更新したりして、「まあサーバーにあるからいいでしょ。しばらく使わないし、必要になったらcloneしよ」といって皆のローカルディスクからはcloneされたリポジトリが消えていく。唯一残るリポジトリはサーバーのものだけ...。そういうときに限って、サーバーとは壊れるものなのだ。

だから、Mercurialのリポジトリを預かるサーバーは、やはりバックアップについて少なからず気にする必要がある。

え、SSH通るんならscp使えばいいじゃん。

YES、その通り。

しかし、「大容量ファイルを転送中に接続が切れてしまった」なんてときに、コピーが完了した後から残りを引き継ぎたい、みたいな要求にはscpコマンドは答えてくれない。もちろん、sftp使えばレジューム機能もあるんだしそうすればいいじゃんというのは正論だが、sftpの方はsshが通るからといって必ずしも使えるとは限らない。

そんなときは、多少強引だとしても、一歩戻って解決を試みるのもひとつの手だ。

大容量で、POPやIMAPも使える、Googleが提供するWebメールシステム、Gmail。 外出先からでも、別段特別なメールアプリケーションが無くても、 ブラウザ一本、スマートフォン一本あればメールを確認できるのは確かに便利だ。

しかし、そのGmailを使っていてひとつ気になるのが、 自分が参加しているメーリングリストに投稿しても、どうやらそのメールが届かないように見えることだ。

一体これはどういうことなのか？ 色々調べる中で分かったことをまとめてみよう。

ここ最近文字コードはUTF-8で統一することが多くなったので、 いわゆる「文字化け」を目にすることは随分少なくなったが、 それでもまだ「化けて出る」のが日本語という奴ではある。

で、まあ文字コード関連のノウハウは色々あるようだけども、 今回はそういう話題ではない。

この幽霊たち、いくつかは特徴のある姿をしているので、 分かりやすい幽霊についてちょっと紹介してみようと思う。

RAID1とかRAID5とか、冗長性確保という意味では確かに便利だけども、 ハードウェアのサポートが必要だったりとか、書き込みホール問題だとか色々あるワケで、 まあ色々面倒なところはある。 で、その辺の問題を解決したぜ！　と主張するのがSolaris由来のZFSでサポートされるRAID-Z。

http://blogs.sun.com/bonwick/entry/raid_z5

ほほう、なかなか良さそうじゃあないですか。 でもって普段使ってるFreeBSDにもZFSがportされてきたらしいじゃないですか。 こりゃあ試さないといかんでしょう。

さて、今回こちらに生まれも育ちも異なるが、 容量は大体全部250GBくらいのHDDが4玉ございます。 1玉だけ300GB近くあるけど気にせずに、ちょっくらRAID-Z2を組んでみようではございませんか。

なお今回特に冗長性が必要な運用を想定しているわけでは全くないので、 おおむねRAID-Z2とかはオーバースペックではある。 が、どのみち今回使用予定のHDDはどれもこれも少なくとも3年、 長いものは6年以上使っていていつ寿命がきてもおかしくないドライブなので、 そういう意味では冗長化も全く無駄ではなかろう。 ...いや要するに、「ZFSのRAIDを使ってみたい！」が半ば目的なわけだが。

まあ巷の噂ではCPUリソースを食うとかメモリもバカ食いするとか色々あるみたいだけど、 今回の構成はCPUはCore2Duo、メモリは4GBだ。 ZFSを使うのに十分かどうかはともかく、問題はないだろう。多分。

で、インストール手順は下記Wiki記事にある。

http://wiki.freebsd.org/RootOnZFS/GPTZFSBoot/RAIDZ2

以上。

うん。以上。これで終わらせても問題ないくらいにはなにもなくインストールが完了してしまった。

しかしまあこれだけというのもさみしいのでちょっと補足。