qemu VNC on WebSocket

はじめに

qemu 1.4 では Websocket プロトコル上で VNC を実現する機能が実装されました。
Qemu/Changelog/1.4
従来、ブラウザ(Websocket)でVNCを利用する場合、Websockify などを用いて、Websocket 通信を通常のソケット通信に変換しなければなりませんでした。今回 qemu VNC がWebsocket 対応したことにより、従来のような面倒な変換なしにブラウザ経由で VNC を利用できます。HTML5対応のブラウザであれば、Java プラグインなど無しに気軽に VNC を利用できるようになるのでとても便利です。

関連コミット：
http://git.qemu.org/?p=qemu.git;a=commit;h=7536ee4bc3da7e9b7fdadba5ba6ade63eaace430

使い方

qemu の configure 段階で vnc-ws を有効にします。

$ ./configure --enable-vnc-ws

以下のようなエラーがでるかもしれません。

ERROR
ERROR: User requested feature vnc-ws
ERROR: configure was not able to find it
ERROR

その時は、gnutls-devel パッケージをインストールします。

# yum install gnutls-devel

無事にインストールが済んだら、libvirt XML ファイルを編集しましょう。
コンパイルした qemu を使用するため、emulator タグで qemu の path を変更します。
また、qemu に "-vnc :1,websocket" オプションを渡すためのタグを追加します。ここで、"1:" はディスプレイポート番号です。"0:" だと既存のディスプレイと重なるかもしれないので、ずらしてあります。

<domain type='kvm' xmlns:qemu='http://libvirt.org/schemas/domain/qemu/1.0'>
...
  <devices>
    <emulator>/usr/local/bin/qemu-system-x86_64</emulator>
    ...
  </devices>
  <qemu:commandline>
    <qemu:arg value='-vnc'/>
    <qemu:arg value=':1,websocket'/>
  </qemu:commandline>
</domain>

仮想マシンを起動し、novnc.com にアクセスします。
noVNC.com は HTML5(Canvasなど) と Websocket で実装された、Web ベースの VNC クライアントです。 ブラウザは必ず HTML5 対応の新し目のブラウザを使いましょう。
右上の "Connect" ボタンをクリックし、
Host : 127.0.0.1
Port : 5701
を入力します。ポート番号は、上記で設定したディスプレイ番号に 5700 を足したものになります。今の場合だと、ディスプレイ番号 "1" + 5700 = 5701 です。
接続できると、こんな感じで、画面が表示されます。Chrome の中で Firefox を動かして見ました。

せっかくなので、iphone と Nexus 7 でも試して見ました。
Nexus 7

iphone

自宅の WiMAX環境では、iphone は重くて使い物になりませんでした。Nexus 7 もキーボードがいまいち使いにくかったです。

ともあれ、VNC on Websocket ではブラウザさえあれば、どこからでも VNC で画面転送できるのは便利です。家の仮想マシンを VPN 接続で iphone から操作する、なんてもこともできます。

余談

SPICE の HTML5 クライアントはないのかな？と思ったらありました。
HTML5 - SPICE
qemu が Spice on Websocket に対応していないので、 Websockify が必要です。

qemu cache mode まとめ

はじめに

qemu の cache mode には "none", "direcsync", "writeback", "writethrough", "unsafe" の5つがあります。名前からでは、cache mode のそれぞれの仕組みがよくわかりません。そのために、どのようなケースでどの cache mode を使えばいいのか、判断に困ってしまいます。
ここでは、raw ディスクイメージについて、それぞれの cache mode の違いをまとめます。(qcow2 など他のディスクイメージフォーマットでは仕組みが若干ことなります)

Cache Mode 性質比較
それぞれの cache mode ではHost page cache や仮想的な Disk write cache を用いるかどうかで性質が変わってきます。表でまとめると以下のようになります。

cache mode	Host page cache	Disk Write cache	NO Flush
directsync
writethrough	✓
none		✓
writeback	✓	✓
unsafe	✓	✓	✓

✓ : on

Host page cache とは、qemu が 仮想マシンイメージファイルを open するときに O_DIRECT フラグをつけるか否かです。"none" と"directsync" では O_DIRECT フラグを"つける" ので、Host page cache を使いません。

Disk Write Cache とは、virtio-blk デバイスの持つ揮発性 cache です。現在では通常のHDDなどは32MB や 64MB のcache を持っていますが、Disk write cache は virtio-blk が持つ仮想的な cache です。qemu の中では Disk Write Cache を使うか否かで flush(fdatasync) のタイミングが異なります。使う場合はOSから flush 要求があった時に flush(fdatasync) しますが、使わない場合は disk write の度に flush(fdatasync)します。qemu が fdatasync を発行することで、Host の Disk にデータが書きだされますが、頻繁に fdatasync すると性能が劣化してしまします。

NO Flush とはqemuが保持している cache を disk へ flush するのを無効化します。無効化することで性能は上がりますが、Host クラッシュ時にゲストでファイル不整合が起こる可能性が増します。

以上を踏まえると、cache mode は以下のように分類できます。
こちらのほうがわかりやすいと思います。

	Host page cache あり	Host page cache なし
Write 毎 にFlush	writethrough	directsync
Flush 要求時に Flush	writeback	none
Flush 無効	unsafe

性能比較
それぞれのcache mode のライト性能を、dd で測定しました。
環境は以下となっています。

• HostOS: Fedora 18 (3.7.9-201.fc18.x86_64)
• GuestOS : 同上
• Host FS : ext4 (ordered)
• Guest FS : 同上
• Host memory : 4GB
• Guest memory : 1GB
• qemu : 1.4
• qemu aio : threads
• qemu disk type : raw

測定コマンドは

$ dd if=/dev/zero of=./zero bs=64K count=8K 

もしくは

$ dd if=/dev/zero of=./zero bs=64K count=8K oflag=direct

です。
Cache Mode の性質を比較するために、direct flag をつけた場合でも測定しています。

比較表

	通常 write(MB/s)	oflag=direct(MB/s)
HOST	96.5	82.3
directsync	65.8	4.8
writethrough	62.8	4.6
none	88.3	54.2
writeback	80 ~ 400	80 ~ 400
unsafe	80 ~ 400	80 ~ 400

"writeback" と "unsafe" ではブレが非常に大きくなっています。これは Host の Page cache の影響です。 "directsync" と "writethrough" では、oflag=direct 時に著しく性能が落ちています。これは qemu が write 毎に fdatasync を発行するためです。

Cache mode の選定
さて、cache mode には色々あり、性質も大きく異なりますが、結局どの mode を選べば良いのでしょうか。指標としては、"メモリ消費量"、"性能"、"安全性" が挙げられます。

"メモリ消費量" で mode に大小をつけると以下のようになります。
directsync = none < writethrough = write back = unsafe
"directsync" と "none" では Host page cache を使用しないため少なくなります。他の mode では Host page cache が効くため、Guest と Host で二重にキャッシュが効いていることになります。つまり、同じデータがメモリ上に重複して存在してしまします。KSM(Kernel Samepage Merging)の仕組みがあるとは言え、キャッシュ重複はメモリを消費するため、好ましいものではありません。

"性能" での優劣は以下となります。
directsync < writethrough < none < writeback < unsafe
"writeback" と "unsafe" は広大な Host page cache を効かせる分、性能は良くなります。write 毎に fdatasync を発行する "directsync" や "writethrough" は性能は劣ります。

"安全性" での優劣は以下となります。ここで、安全性とは、ファイル整合性がとれるまでの時間が短いものを優とします。
unsafe < writeback < none < writethrough = directsync
fdatasync を頻繁に発行する "writethrough" と "directsync" はファイル整合性を取りやすいです。cache を効かせ、Flush 頻度が少ないものほど、安全性は劣ります。

以上を踏まえて、cache mode を選定します。
要件により、選定する cache mode は異なります。

1. とにかく安全第一。物理環境と同程度の安全性が欲しい。
⇛ directsync
cache mode で一番安全なのは O_DIRECT で fdatasync を頻発する directsync です。そのかわり、性能はいまいちです。

2. メモリ消費量は程程に、性能もある程度欲しい。
⇛ none
"none" は Host page cache を使わないため、メモリ消費もそれほど大きくありません。性能も Host には劣りますが、まずまずです。

3. メモリをどれだけ消費しようが、性能が欲しい。
⇛ writeback
"writeback" は広大な Host page cache を使うため、性能が出ます。反面、メモリ消費量は大きいです。

普通に VM をいじる分には "writeback" で。メモリ が多くない環境では "none" にするのがいいと思います。
ちなみに、自分はいつも "none" にしています。

参考文献
An Updated Overview of the QEMU Storage Stack
QEMU Emulator User Documentation
[Qemu-devel] Is cache=writeback safe yet

qemu virtio-blk data plane の使い方

はじめに
qemu virtio-blk data planeとは、virtio-blk デバイスごとに、専用のIO threadを作り、QBL(qemu big lock)の外部で動作させることでlock contentionによる性能劣化を抑える試みです。専用のthreadを作り性能を向上させる試みは、ネットワークではすでにvhost-netを用いて行われていました。

関連コミット:
http://git.qemu.org/?p=qemu.git;a=commit;h=392808b49b6aee066d0c1d200e72fc3dc11c9d0f

簡単に仕組みを説明すると、virtio-blk デバイスごとに作られたIO threadはLinux Native AIOシステムコールを使い、非同期にIOを発行します。ゲストからの通知(ioeventfd)、およびゲストへの割り込み通知(irqfd)もこのIO threadが担当します。従来はqemuが行なっていた作業をglobal mutex外へと分離し、専用のthreadに任せることでScalabilityと性能を向上させることができるわけです。

virtio-blk data planeを用いることで、IOPSが14万から60万に上がったという報告もあります。
http://comments.gmane.org/gmane.comp.emulators.qemu/184821

しかし、現状ではvirtio-blk data plane には以下のような制限があります。

• raw format のみのサポート
• live migration 非サポート
• hot unplug 非サポート
• qemu での IO throttling が効かない
• Host は linux のみサポート(Linux Native AIO syscallを使うため)

使い方
virtio-blk x-data-plane を使うには、まず条件として以下が必要です。

• raw image formatでなければならない
• wce(write cache enable: Guestのwrite cache設定を起動中に on/off 変更する機能) off
• scsi off

「raw image なんてないよ、qcow2(or 3) しかないよ！」という方は以下のコマンドでraw image を作ってVMを新規作成しまししょう。

# qemu-img convert -O raw qcow.img raw.img

qemu を直接起動しても良いのですが、ここでは利便性のためにlibvirtを経由してqemuを扱うことにします。
上記の条件に合うように、libvirt XML file を作りましょう。
例えば、以下のようにします。

<domain type='kvm' xmlns:qemu='http://libvirt.org/schemas/domain/qemu/1.0'>
...
  <devices>
    <emulator>/usr/local/bin/qemu-system-x86_64</emulator>
    <disk type='file' device='disk'>
      <driver name='qemu' type='raw' cache='none' io='native'/>
      <source file='/home/eiichi/vmimg/fraw.img'/>
      <target dev='vda' bus='virtio'/>
      <address type='pci' domain='0x0000' bus='0x00' slot='0x06' function='0x0'/>
    </disk>
    ...
  </devices>
  <qemu:commandline>
    <qemu:arg value='-set'/>
    <qemu:arg value='device.virtio-disk0.config-wce=off'/>
    <qemu:arg value='-set'/>
    <qemu:arg value='device.virtio-disk0.scsi=off'/>
    <qemu:arg value='-set'/>
    <qemu:arg value='device.virtio-disk0.x-data-plane=on'/>
  </qemu:commandline>
</domain>

diskタイプをraw、AIOはLinux Nativeを指定します。
また、qemuの-setオプションを使うことで、x-data-plane=on オプションを有効にします。

評価
以下の環境で、bonnie++による書き込み性能評価を行いました。

• Host OS: Fedora 18
• Host Memory : 4G
• Host FileSystem : btrfs
• Guest OS: Fedora 18
• Gues VCPU: 2
• Guest Memory : 1G
• Guest FileSystem : btrfs
• Qemu : qemu v1.3.0-rc2
• 測定コマンド : bonnie++

Guest data plane off:

Version  1.96       ------Sequential Output------ --Sequential Input- --Random-
Concurrency   1     -Per Chr- --Block-- -Rewrite- -Per Chr- --Block-- --Seeks--
Machine        Size K/sec %CP K/sec %CP K/sec %CP K/sec %CP K/sec %CP  /sec %CP
fraw             2G   875  84 74157  13 21666   6  3128  78 50335   6 263.5  15
Latency             31893us     632ms    6507ms   83291us     299ms     728ms
Version  1.96       ------Sequential Create------ --------Random Create--------
fraw                -Create-- --Read--- -Delete-- -Create-- --Read--- -Delete--
              files  /sec %CP  /sec %CP  /sec %CP  /sec %CP  /sec %CP  /sec %CP
                 16 21634  57 +++++ +++ +++++ +++ 22124  60 +++++ +++ +++++ +++
Latency               241us     593us     443us     108us      30us     138us

Guest data plane on:

Version  1.96       ------Sequential Output------ --Sequential Input- --Random-
Concurrency   1     -Per Chr- --Block-- -Rewrite- -Per Chr- --Block-- --Seeks--
Machine        Size K/sec %CP K/sec %CP K/sec %CP K/sec %CP K/sec %CP  /sec %CP
fraw             2G   900  87 61252  12 24206   7  3296  82 91454  12 242.6  15
Latency             54769us    1189ms    5273ms   36272us     275ms     546ms
Version  1.96       ------Sequential Create------ --------Random Create--------
fraw                -Create-- --Read--- -Delete-- -Create-- --Read--- -Delete--
              files  /sec %CP  /sec %CP  /sec %CP  /sec %CP  /sec %CP  /sec %CP
                 16  6949  18 +++++ +++ +++++ +++ 19625  52 +++++ +++ 32179  21
Latency              1069us    1450us     448us     112us     449us     173us

残念ながら、自分の環境だと性能に大きな違いは見受けられないようです。。
高性能なストレージを使ったり、qemu_global_mutex contention が大量に発生する環境で測定すると、また違った結果がでてくると思われます。

参考文献

An Updated Overview of the QEMU Storage Stack
Optimizing the QEMU Storage Stack
[Qemu-devel] [PATCH v2 0/8] virtio: virtio-blk data plane
Features/WriteCacheEnable

手軽にqemuのトレースを採る

qemu内部のロジックを追ったり、性能解析をするにはトレース採取が有効です。qemuのトレースを手軽に採る方法についての投稿です。

qemuのトレースを採る方法については、いくつかありますが、標準エラー出力にトレースを書き出す "stderr" trace-backend がもっとも簡単な方法です。
"stderr" backend の仕組みは qemu 内部のトレースイベントを標準エラー出力にデバッグprintfをするという非常に単純なものです。
qemu-kvm 0.15よりサポートされています。

関連コミット：
http://git.qemu.org/?p=qemu.git;a=commit;h=320fba2a1f384e17db150d74540a2cf005eb47b5


使い方
qemuのトレースは採取しない設定でもオーバヘッドがあるため、デフォルトではオフになっています。トレースを有効にするには、コンパイル時にトレースを有効にする必要があります。
コンパイルオプションは以下のようになります。

./configure --prefix=/usr/local/ --enable-trace-backend=stderr

トレースイベント一覧は以下のファイルにかかれています。

qemu/trace-events

イベント一覧から、取得したいイベントを選びファイルに書き出します。 例えば、以下のような内容のファイルを作ります。ワイルドカード指定が可能です。

g_malloc
g_free
qemu*
virtio*

qemu を起動する際に、このイベントファイルを-traceオプションに指定します。

sudo ./qemu-system-x86_64 -enable-kvm -hda ~/vmimg/f1.img -m 512 -trace events=/path/to/events-file

得られる出力は以下のようになります。

g_malloc size 16 ptr 0x7f3f40004270
qemu_co_mutex_lock_entry mutex 0x7f3f54a80898 self 0x7f3f54a7faa0
qemu_co_mutex_lock_return mutex 0x7f3f54a80898 self 0x7f3f54a7faa0
qemu_co_mutex_unlock_entry mutex 0x7f3f54a80898 self 0x7f3f54a7faa0
qemu_co_mutex_unlock_return mutex 0x7f3f54a80898 self 0x7f3f54a7faa0
qemu_coroutine_yield from 0x7f3f54a7faa0 to 0x7f3f400009d8
qemu_coroutine_enter from 0x7f3f54a7fbb8 to 0x7f3f54a7faa0 opaque (nil)
qemu_co_mutex_lock_entry mutex 0x7f3f54a80898 self 0x7f3f54a7faa0
qemu_co_mutex_lock_return mutex 0x7f3f54a80898 self 0x7f3f54a7faa0
qemu_co_mutex_unlock_entry mutex 0x7f3f54a80898 self 0x7f3f54a7faa0
qemu_co_mutex_unlock_return mutex 0x7f3f54a80898 self 0x7f3f54a7faa0
g_free ptr 0x7f3f40004270

libvirtとの連携
qemuを利用する際は、通常libvirt経由で利用することが多いと思います。ここではlibvirtから"stderr" trace-backend を利用する際のtipsを記載します。

・libvirtのログに出力
virsh start domain コマンドでドメインを起動した場合、stderrの出力先は、以下になります。

/var/log/libvirt/qemu/domain.log

・動的なイベントのオン・オフ
qemu monitor command を利用することで、稼働中のドメインで採取するイベントを動的にon/offできます。

利用可能なトレースイベント一覧の取得

# virsh qemu-monitor-command --hmp domain info trace-events

イベントのon・off

# virsh qemu-monitor-command --hmp domain trace-event qemu_vmalloc on
# virsh qemu-monitor-command --hmp domain trace-event qemu_vmalloc off

参考情報

Observability using QEMU tracing
qemuのtrace機能
docs/tracing

mbed + FeliCa リーダライタでドアの鍵開閉システム

mbed + FeliCa リーダライタを使って、ドアの鍵を開閉するシステムをつくってみました。
まずは、こちらをごらんください。



このシステムは、

• 特定の Suica(FeliCa) カードをリーダライタにかざすと鍵を開閉する
• 他の FeliCa カードだと開閉しない

ようになっています。
動画では、はじめに Suica で鍵開閉を行い、次に他の Felica カードをかざしても鍵開閉が行われないことを示しています。
特定の Suica カードの認証は、単にカードの IDm を読み取って比較しているだけです。

以下、材料と参考にさせていただいた情報などです。

材料

1. mbed
2. rb303 サーボモータ
3. FeliCa リーダー・ライター RC-S620S
4. FeliCa RC-S620S ピッチ変換基板(フラットケーブル付き)
5. 磁石とか金具とか端材

を用いています。
1,3,4 については スイッチサイエンスさんより購入可能です。
2 のサーボモータに関しては、たぶん秋葉原の千石電商さんで購入しました。
5 の磁石とか金具とか端材はホームセンターで購入したり、拾ったりしました。

参考情報

• スイッチサイエンス : mbedでFeliCa リーダー・ライター RC-S620Sをつかう
• Felica Developer's Blog : Arduino向けRC-S620/S制御ライブラリの提供 [RFワールド No.12連動 -機器構成②-]

失敗談

実は、FeliCa ピッチ変換基盤と mbed のつなぎ方を間違えてしまい、RC-S 620S リーダ・ライタを1台壊してしまいました。

上の写真は 材料3 のピッチ変換基盤です。

僕は一番上が VCC だと勘違いして mbed に接続し、リーダライタを壊してしまいました。

正しい接続の仕方は、上から

1. なし
2. なし
3. GND
4. Serial RX
5. Serial TX
6. VOUT(3.3V)

です。くれぐれもご注意を。

ですが、なんと嬉しいことに、twitter 上で僕の失敗を知った @wnaitou さんが、新しいFelica リーダライタを贈って下さいました！そのおかげで、この鍵開閉システムができました。

@wnaitou さん、どうもありがとうございました！! m(_ _)m

おまけ

iphone から操作できるようにもしました。



こちらは、
iphone -> the Internet -> 自宅サーバ -> mbed -> servo
という経路になっています。

SystemTapで関数の呼び出し元を取得する

SystemTapはスクリプトで気軽にLinux Kernelの動作を調査できる素敵なツールです．
この記事は，SystemTapで関数の呼び出し元を取得する方法についてのメモです．
Tapset Referenceを参考にし，Context Functionsのfunction:callerを使用します．
最も簡単なものだと，このような形になります．

probe kernel.function("schedule").return {
  printf("caller : %s", caller())
}

出力はこんな感じ．Kernel内のschedule()関数を呼び出した関数名と，アドレスが出力されます．

[eiichi@fedora]~/work/stap% sudo stap schedule.stp
caller : cpu_idle 0xffffffffc04023d0
caller : cpu_idle 0xffffffffc04023d0
caller : run_ksoftirqd 0xffffffffc04558ed
caller : cpu_idle 0xffffffffc04023d0

さて，簡単な応用として，linux/kernel/sched.cで定義されているschedule()関数を呼び出している関数Top20を表示させてみましょう．
systemtap scriptは以下のようになります．

global callers

function print_top() {
  cnt=0
  printf("%-50s\tCount\n", "Caller")
  printf("---------------------------------\n")
  foreach( [name] in callers-) {
    printf("%-50s\t%5d\n", name, callers[name])
    if (cnt++ == 20)
      break
  }
  printf("---------------------------------\n")
}

probe kernel.function("schedule").return {
  callers[caller()]++
}

probe end {
  print_top()
  delete callers
}

eiichi@fedora]~/work/stap% sudo stap schedule_caller_top.stp -c "sleep 1"
Caller                                             Count
---------------------------------
cpu_idle 0xffffffffc04023d0                          332
worker_thread 0xffffffffc0468418                     166
schedule_hrtimeout_range_clock 0xffffffffc09202e7    116
futex_wait_queue_me 0xffffffffc047ec83                52
do_nanosleep 0xffffffffc0920158                       18
work_resched 0xffffffffc0921302                       17
schedule_timeout 0xffffffffc091fa05                   12
run_ksoftirqd 0xffffffffc04558ed                       8

---------------------------------

sleep ではcpu_idleが多くなります．
ちなみに，hackbenchを動かすと，このような感じです．

[eiichi@fedora]~/work/stap% sudo stap schedule_caller_top.stp -c "hackbench 10"
Running in process mode with 10 groups using 40 file descriptors each (== 400 tasks)
Each sender will pass 100 messages of 100 bytes
Time: 0.374
Caller                                             Count
---------------------------------
schedule_timeout 0xffffffffc091fa05                 1590
work_resched 0xffffffffc0921302                      735
cpu_idle 0xffffffffc04023d0                          349
worker_thread 0xffffffffc0468418                      83
rwsem_down_failed_common 0xffffffffc0920d25           22
schedule_hrtimeout_range_clock 0xffffffffc0920375     17
do_wait 0xffffffffc0452025                            10
schedule_hrtimeout_range_clock 0xffffffffc09202e7      5
run_ksoftirqd 0xffffffffc04558ed                       5
do_nanosleep 0xffffffffc0920158                        2
futex_wait_queue_me 0xffffffffc047ec83                 1
---------------------------------

ここで，schedule()関数ではなく，他の関数でも，呼び出し元Top20を表示させる場合を考えてみましょう．いちいちstap scriptを書き換えるのも面倒です．

付け焼刃的ですが，shell scriptと組み合わせると，簡単にできます．

#!/bin/sh
func=$1
cmd=$2
stap -e 'global callers
function print_top() {
  cnt=0
  printf("%-50s\tCount\n", "Caller")
  printf("---------------------------------\n")
  foreach( [name] in callers-) {
    printf("%-50s\t%5d\n", name, callers[name])
    if (cnt++ == 20)
      break
  }
  printf("---------------------------------\n")
}
probe kernel.function("'$func'").return {
  callers[caller()]++
}
probe end {
  print_top()
  delete callers
}' -c "$cmd"

使い方はこんな感じ．

linux/kernel/sched_fair.c のupdate_curr()関数で試してみました．

[eiichi@fedora]~/work/stap% sudo sh caller_top.sh update_curr "hackbench 10"
Running in process mode with 10 groups using 40 file descriptors each (== 400 tasks)
Each sender will pass 100 messages of 100 bytes
Time: 0.469
Caller                                             Count
---------------------------------
update_cfs_shares 0xffffffffc043c777               21460
put_prev_task_fair 0xffffffffc043d062              18516
dequeue_entity 0xffffffffc043cb79                  12369
enqueue_entity 0xffffffffc043d0e1                  12363
check_preempt_wakeup 0xffffffffc043c51f             9622
task_tick_fair 0xffffffffc043c90d                   1968
task_fork_fair 0xffffffffc043c308                    400
---------------------------------

ちなみにhackbench 10 は400個のtaskを生成するので，task_fork_fairからのupdate_curr呼び出し回数がちょうど400になってますね．

参考
RedHat Tapset Reference Manual

SystemTap Tapset Reference Manual

Haskellでlist monadを使って完全順列を生成してみました

完全順列（撹乱順列とも）とは順列を置換と見た場合、不動点をもたない置換のことをいいます。順列の要素数を無限大にした極限をとったとき、完全順列の個数(モンモール数)とすべての順列の個数(n!)の比が1:e(eは自然対数の底)になり、世の中の物好きを惹きつけています。
前回のN-Queens問題につづいてlist monadを利用して関数型言語のHaskellで完全順列を生成するコードを書いてみましょう。

*Main> derangement ['c','o','n','s']
>>["ocsn","onsc","oscn","ncso","nsco","nsoc","scon","snco","snoc"]

こんな感じになって欲しいのです。順列を生成した後にfilterを掛けるのは非効率的なのでやめておきます。
書いてみると以下のようになりました。

import Data.List

derangement xs = drg xs xs

drg [] ys = return []
drg xs (y:ys) =
  delete y xs >>=
  \x -> map (x:) (drg (delete x xs) ys)

Monadを利用することを考えると、こんなに簡単に書けるんですね。
素晴らしきかな、Haskell、Monad！