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とハフマン符号

他の言語で書いたことがあるコードをErlangで書くとどうなるかいろいろ試してみたくなりました。第1弾はハフマン符号です。

ハフマン符号化の大まかな流れは、(1) 頻度表を作る、(2) 頻度表を元にハフマン木を作る、(3) ハフマン木を元に入力記号→ビット列の対応表を作る、(4) 3で作った対応表を元に符号化する、となります。

ではさっそく作ってみましょう。まずは「(1) 頻度表を作る」です。

続きを読む

Erlangとボウリングの点数 (2)

前回の続きです。前回、倒したピンの数をリストにして渡すとスコアが返ってくる関数を作りました。今回は以下のような点をいじってみたいと思います。

  • 途中経過が見えないのは寂しいので、各フレーム時点の合計得点が見たい
  • 10フレームすべての情報を与えないとエラーになってしまうのをなんとかしたい
  • せっかくなので見た目もスコアシートっぽく表示できるようにしたい

まず1つ目についてやってみます。各フレームの情報を、{倒したピンの数, 合計得点} というタプルのリストで返すような関数になるようscore2を改造します。

続きを読む

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のルーチンに追加して再度計測してみました。

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環境:

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:

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:

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のソースを軽く見た限りではMacWindowsでそんなに劇的に変わる気配は感じられなかったので、もう少し読んでみる必要がありそうです。


ソースを再度載せます。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> 

まだまだ分からないことがたくさんですね。という感想は、そんなことも知らなかったのか、という指摘への予防線としては何の威力もありませんね。