2011年10月アーカイブ

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 系を使ってる？ もう古いので早急に乗り換えを検討されるとよろしい。

問題

以下のC#のコードに含まれる誤りを指摘しなさい:

Send()
{
    var xs = (
        GatherItems()
        .SelectMany(i => i.SubItems)
        .Select(i => i.MakeLocation())
    );

    SendLocations(xs);
}

SendLocations(IEnumerable<Location> ls)
{
    var now = DateTime.Now;

    foreach (var l in ls)
        l.UpdatedAt = now;

    foreach (var l in ls)
        l.Send();
}

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 をインストールして実際に試してみて欲しい。

あらすじ

あなたはとある業務用アプリケーションの開発・保守を任されています。 このアプリケーションはASP.NET / C#で作成されており、 多数の一般社員が作成したデータが積み上げられ、 溜まったデータを集計・出力したものを上層部が眺める、 といったことが日夜行われています。 様々な角度からデータを確認する必要があるため、 データ出力機能はアプリケーション内に山ほどあります。 出力形式は様々ですが、とりわけCSVで出力されているデータが多くなっています。

さて、その数ある出力機能の中でも、 特定の条件を満たす社員の一覧をCSVで出力する機能があるのですが、 クライアントからの要望で出力されるCSVのカラムの並びの変更や追加を行うことになりました。 出力機能の改修は今回が初めてなのですが、 既にあるものに少し手を加えるだけなので、 大した仕事にはならないはずです。 ちゃっちゃと片付けてしまいましょう。

5分後 ──