Erlangとlists:zf/2
普段はEmacs + Distelで開発しているのですが、ErlIDEって最近どうなんだろうと思って久しぶりに触ってみました。
初回はかなり待たされましたが、その後は快適です。補完も効くし、F3(Open Declaration)もきちんと効いて快適です。UTF-8での保存もサポートするようになったようです。以前はだめだったんですが風向きが変わったのでしょうか。
補完が効くので面白がっていろいろ眺めていたら、lists:zf/2というのを発見しました。説明がまったくありません。F3で飛んでみると「The name zf is a joke!」なるコメントが。実装を見る限りだと、mapとfilterを合わせたようなものみたいですね。以下とても作為的な例ですが、FizzBuzzしつつ7の倍数を省くという処理を書いてみました。
続きを読むErlangとボウリングの点数とリストのパターンマッチ
Re: 配列の隣接する2項にそれぞれ演算を施した配列で、overlappingPairsCollect: というSmalltalkのメソッドが紹介されていました。面白そうなのでErlangで実装してみました。
-module(pairs). -compile(export_all). overlapping_pairs_collect(F, L) -> overlapping_pairs_collect(F, L, []). overlapping_pairs_collect(_F, [], Res) -> lists:reverse(Res); overlapping_pairs_collect(_F, [_], Res) -> lists:reverse(Res); overlapping_pairs_collect(F, [X, Y | L], Res) -> overlapping_pairs_collect(F, [Y|L], [F(X, Y) | Res]).
実際に試してみます...
75> pairs:overlapping_pairs_collect(fun(X,Y) -> X + Y end, lists:seq(1,5)). [3,5,7,9] 76>
よいようです。実はこれを試すまで、Erlangでリストの先頭2項目以上のマッチングや連結ができるということを完全に失念しておりました。
というよりできないものだと勝手に思いこんでいて、でも文字列だと複数文字のマッチングできるしなあ...と若干納得のいかないところがあり、今回できることがきちんと確認できてよかったです。
できることが分かったので、同じくsumimさんのTDDBC 札幌 2.3 で遊びで書いてみたボウリングスコア集計もできそうだなと思いました。Haskell Bowling | xProgramming.comが元の問題のようです。Haskellのコードを素直に真似て書いたのが下記のコードです。
score([]) -> 0; score([X]) -> X; score([X,Y]) -> X + Y; score([X,Y,Z]) -> X + Y + Z; score([X,Y,Z|L]) -> if X =:= 10 -> X + Y + Z + score([Y,Z|L]); X + Y =:= 10 -> X + Y + Z + score([Z|L]); true -> X + Y + score([Z|L]) end.
しかしこれがどうも思わしくありません。具体的には下記のようなリストで期待した結果が来ません。
76> pairs:score([10, 10, 10, 10, 10, 10, 10, 10, 10, 3, 3]). 249 77>
本当は255点を期待しています(手で計算してもやはり255点でした)。そしてオリジナルのHaskellバージョンでも同じく249という誤ったスコアになってしまいます。
インタプリタになったつもりでトレースしてみたのですが、 前から順番に処理して、[10, 3, 3] にさしかかったとき、最初の10というのは第9フレームで倒したピンの数ですので、第9フレームとしての得点は10 + 3 + 3 = 16となり、第10フレームはストライク・スペアにかかわらず単に倒したピンの数を足せばいいので(ストライク・スペアが出たときは3投できますので3回で倒したピンの数を足す) 3 + 3 = 6 となります。したがって第9〜10フレームの合計スコアは16 + 6 = 22 です。第8フレームまでの合計スコアは233点なので、あわせて255点がゲーム終了時の点数になります。
上記コードでは、[10, 3, 3]にさしかかったとき、 score([X,Y,Z]) にマッチしてそれを全部足すという処理を行っています。これは第10フレームで10本、3本、3本と倒した場合は正しいのですが、今回はそうではありませんので、最後のパターンにマッチして、第9フレームとして10 + 3 + 3 を加算した後、第10フレームとして 3 + 3 を加算しなければいけません。でも、どっちのパターンにマッチするべきなのかは現在のフレームによって決まりますので、あれこれ考えてみたのですが、結局、フレーム数を保持しなければどうしようもないのでは?という結論に至りました。書きなおしたコードとテスト用コードは下記の通りです。
score2(L) -> score2(L,1). score2(L, 10) -> lists:sum(L); score2([X,Y,Z|L], Frame) -> if X =:= 10 -> X + Y + Z + score2([Y,Z|L], Frame + 1); X + Y =:= 10 -> X + Y + Z + score2([Z|L], Frame + 1); true -> X + Y + score2([Z|L], Frame + 1) end. test() -> 0 = score2([0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]), 300 = score2(lists:duplicate(12,10)), 30 = score2(lists:flatten([10, 5, 5, lists:duplicate(17, 0)])), 255 = score2([10, 10, 10, 10, 10, 10, 10, 10, 10, 3, 3]), 161 = score2([0, 0, 10, 8, 2, 10, 10, 10, 5, 3, 8, 2, 10, 2, 3]), 126 = score2([5, 3, 7, 2, 8, 2, 10, 7, 1, 9, 0, 6, 2, 10, 6, 4, 8, 0]), ok.
テストは無事に通り、そしてプログラムも若干単純になったように思います。第10フレームで何投したのか気にせず足すだけなど手抜きをしていますが... 一方、不完全なリスト(10フレームまで行っていないもの)ではエラーとなります。
今回久しぶりにボウリングのスコアの計算を試みたのですが、当時(10歳前後?)の理解がいろいろ間違っていたこともあり追跡に苦労しました。具体的には10フレーム目だけストライク・スペア出しても次に倒したピンの数が2倍のスコアにならないということを知りませんでした(そのかわりに3投できるというボーナスがつくのですね)。過去に自力で計算したスコアは多めに計算していたのかもしれません。もっとも中学時代はほとんどボウリングしなかったし、高校時代になればもうスコア計算は勝手にやってくれていたように思いますので、小学生時代の短い期間だけですね。そしてそのときはストライク・スペアなんてろくに出なかったのでまず問題ないでしょう... (どうでもいい)
Erlangと配列 (つづき)
前回のつづきです。Erlangには配列がないものだと思い込んでいたのでこのようなエントリを書いたのですが、ふとReference Manualを見るとarrayという単語が...
以前書いたCRC32のルーチンに追加して再度計測してみました。
- Erlang R14B03 (erts-5.8.4) [source] [smp:2:2] [rq:2] [async-threads:0] [hipe] [kernel-poll:false]
- Mac OS X Server 10.6.8
- Processor 2.53GHz Intel Core 2 Duo
- Memory 4GB 1067MHz DDR3
loop | array | tuple | binary2 | dict | process_dictionary | ets |
1 | 9759 | 6035 | 7784 | 14556 | 5618 | 12727 |
2 | 10187 | 6050 | 8105 | 14794 | 5578 | 12338 |
3 | 9478 | 5823 | 7805 | 14912 | 5831 | 12796 |
4 | 9880 | 5985 | 8079 | 14972 | 5799 | 12796 |
5 | 10064 | 6001 | 7851 | 14754 | 5586 | 12465 |
あれ?あんまり早くないですね... 続いてWindows環境:
- Windows 7
- Processor 2.13GHz Intel Core 2 Duo
- Memory 2GB
loop | array | tuple | binary2 | dict | process_dictionary | ets |
1 | 16988 | 7720 | 10621 | 23196 | 8485 | 18048 |
2 | 17424 | 7689 | 10888 | 23227 | 8002 | 17783 |
3 | 17581 | 7768 | 11371 | 23010 | 8001 | 18127 |
4 | 17362 | 7877 | 10966 | 23134 | 8065 | 18502 |
5 | 17237 | 7551 | 10919 | 23291 | 8127 | 18298 |
やっぱり早くないです。というよりtupleの倍以上かかってますね。この結果だけを見るとtupleの方がいいなあと思えてきます。
コードは以下の通りです。一部コードを追加しただけなので構造に変化はありません。また、arrayに与えるフラグ(fixed)の有無は性能にはほとんど影響しないようでした。
続きを読むErlangとCRC32 (つづき)
先日のErlangと配列の続きです。
あらすじ: zlib:crc32と、自前で実装したCRC32の性能を比較しました。自前で実装したCRC32は内部のテーブルの持ちかたをいろいろ変えて性能の違いを計ってみました。当たり前ですがzlibのものが一番早かったです。
今回はそんなに関係ないあらすじ: 一口にCRC32といってもいろんなバリエーションがあるので、IEEE 802.3 のものでなかったらzlib:crc32は使えないから嫌だなあと思い、もし自分で実装するとなるとErlangで配列に相当するデータ構造が必要だよね、でもいくつか思いつく手段のうちどれをとればいいのだろう?と疑問に思いました。(あらすじに続く)
Voluntasさんから、erlang:crc32/1 を使えばというコメントをいただきました。ありがとうございます。
(また、Voluntasさんには、Efficiency Guideの日本語版も紹介いただきました。ありがとうございます。OTP Design Principles と System Principles もあって感激です。)
さて、CRC32がBIFにあったなんて...盲点でした。盲点がでかすぎる気がしますね。恥ずかしいです。
あらためて計測しなおしてみました。まずMac:
- Erlang R14B03 (erts-5.8.4) [source] [smp:2:2] [rq:2] [async-threads:0] [hipe] [kernel-poll:false]
- Mac OS X Server 10.6.8
- Processor 2.53GHz Intel Core 2 Duo
- Memory 4GB 1067MHz DDR3
loop | tuple | binary2 | dict | process_dictionary | ets | zlib | erlang_crc |
1 | 5734 | 7671 | 13954 | 5658 | 12408 | 430 | 429 |
2 | 5763 | 7673 | 14028 | 5624 | 12488 | 457 | 453 |
3 | 5726 | 7616 | 13994 | 5612 | 12368 | 428 | 429 |
4 | 5762 | 7682 | 14031 | 5673 | 12432 | 427 | 428 |
5 | 5755 | 7594 | 14014 | 5691 | 12567 | 430 | 429 |
次にWindows:
- Windows 7
- Processor 2.13GHz Intel Core 2 Duo
- Memory 2GB
loop | tuple | binary2 | dict | process_dictionary | ets | zlib | erlang_crc |
1 | 7691 | 10685 | 22681 | 7969 | 16769 | 483 | 46 |
2 | 7471 | 10514 | 22744 | 8034 | 19671 | 529 | 46 |
3 | 8439 | 13368 | 23447 | 8316 | 17050 | 483 | 61 |
4 | 7643 | 10561 | 22697 | 8033 | 16988 | 483 | 61 |
5 | 7783 | 10576 | 22963 | 8220 | 16898 | 483 | 46 |
最後のerlang_crcというのがerlang:crc32を使ったときの結果です。前回と同様、10万回ずつ試しています。前回との違いは、
- 試行を5回(つまり10万回を5回)に減らしました(前回は10回でした)
- 前回没にしたbinary2を採用しています(くわしくは前回の記事を御覧下さい)
といったところです。Windows版のerlang_crcが目の覚めるようなスピードで動いていますね... ertsのソースを軽く見た限りではMacとWindowsでそんなに劇的に変わる気配は感じられなかったので、もう少し読んでみる必要がありそうです。
ソースを再度載せます。erlang_crc を追加したのと、あとははてなダイヤリーに載せやすいように整形する関数(pp/1)を用意したくらいしか違いはありません。
続きを読むErlangとiolist()
io:format/2みたいな書式指定の出力を、printfに対するsprintfのように、文字列を作るために使いたい! というときには io_lib:format/2が使えます。
16> io_lib:format("~s", ["ABCDE"]). ["ABCDE"] 17> io_lib:format("~10s", ["ABCDE"]). [[[32," ",32,32],65,66,67,68,69]] 18>
2個目は何が起きているの?何か悪いことした? と思うかもしれませんが(私もついさっきまではそう思っていました)、flattenするときちんと期待通りのものが出ていることが分かります。
18> lists:flatten(io_lib:format("~10s", ["ABCDE"])). " ABCDE" 19>
How to format a flat string with integers in it in erlang? - Stack Overflowによると、気にせずそのまま文字列として使っていいよ、と読めます。ただこの状態だと、string:len/1やlength/1で文字数を得ることができないよねえ...と思ったら、これもFAQに相当するもののようで、Erlang io:format to stringによると、iolist_size/1 が使えるようです。
19> L = io_lib:format("~10s", ["ABCDE"]). [[[32," ",32,32],65,66,67,68,69]] 20> length(L). 1 21> string:len(L). 1 22> iolist_size(L). 10 23>
めでたしめでたし...なのでしょうか? なんとなく取った先からlists:flatten/1したいという欲求に抗えない気持です。
なお、iolist_size/1 にただの文字列(string())を与えても問題ないようです。
23> iolist_size("ABCDE"). 5 24>
まだまだ分からないことがたくさんですね。という感想は、そんなことも知らなかったのか、という指摘への予防線としては何の威力もありませんね。