刺身の上にたんぽぽ乗せる日記

プログラミングしたり、自販機の下に落ちてる小銭を集めたりしてます

feedparser置き換え

programming 2chnavi

2chnaviのサービスを運用するにあたって、リソースのボトルネックは何かというと、実はCPUが一番きつい。HDDと違って足りなかったら遅くなるだけでよかったんだけど、流石に全てのフィードをとってパースするのに1時間以上かかるのは、1万以上のRSSがあるとはいえ遅すぎる。

http://d.hatena.ne.jp/kudzu/20120403/1333449336

にも書いたけど、原因はfeedparserの実装が糞遅いから。涙がでるほど遅い。

で、ちょっと調べてたらspeedparserというfeedparserとある程度互換があるfeedparserの実装があったので、試してみた。

https://github.com/jmoiron/speedparser

pypiでパッケージがあったので、pip install speedparserで入れた。

てきとうに2chnaviに登録してあるrssを100ほどdlしてみて、２つのパーサが生成するオブジェクトのフィールドを比べてみたところ、更新日時の解釈が若干違うけど、url、コンテンツ、タイトルなどは割と互換に見える(追記：コンテンツはfeedparserのほうがタグの正規化などを行ってしまうため、完全マッチはできなかった。SANITIZE_HTML=0でも同様)。100くらいしかまだ試してないから、もしかしたらエンコーディングとか色々と細かいところで気が利かないのかもしれんけど。

参考までに速度を一部載せておくと、

5.380 vs 172.251 index.html?xml.15
4.532 vs 1421.450 rss.1
2.985 vs 122.598 index.rdf.21
11.675 vs 910.587 index.html?xml.5
1.524 vs 131.796 index.rdf.6
3.764 vs 487.475 index.rdf.12
5.577 vs 593.087 index.rdf.36
3.477 vs 276.774 index.rdf.43
14.047 vs 7256.265 index.rdf.23
3.561 vs 90.582 index.html.1
4.213 vs 806.865 index.rdf.5
3.599 vs 542.688 index.rdf.34
1.437 vs 432.654 index.html
6.362 vs 1437.406 index.rdf.42
3.384 vs 272.167 index.html?xml.8
5.521 vs 1194.197 index.rdf.47
3.104 vs 143.062 index.rdf.28
3.376 vs 152.067 index.html?xml.12
4.367 vs 872.829 index.rdf.2
14.783 vs 9165.716 talk?feed=rss2
6.751 vs 980.692 index.rdf.19
1.984 vs 205.695 index.html?xml.18
3.122 vs 225.296 index.rdf.18
36.107 vs 19888.307 index.html.4
3.402 vs 316.764 index.rdf.54
2.829 vs 226.778 index.rdf.32
4.423 vs 1081.482 index.rdf.3
5.801 vs 1916.120 index.html.2
25.172 vs 6872.890 gamble?feed=rss2
4.735 vs 846.101 index.rdf.15
11.688 vs 6284.851 pc?feed=rss2
3.572 vs 374.356 index.rdf.7
3.788 vs 377.102 index.rdf.53
4.442 vs 795.737 index.rdf.4
27.751 vs 18444.048 manga?feed=rss2
3.590 vs 524.870 index.rdf.14
2.967 vs 221.017 index.rdf.48
3.441 vs 568.598 index.rdf.20
2.940 vs 303.711 index.rdf.13
8.368 vs 3125.123 index.html?feed=rss2
4.147 vs 139.066 index.html?xml.2
8.120 vs 1324.849 index.rdf.40
3.152 vs 133.390 index.rdf.52
3.258 vs 290.415 index.rdf.44
7.013 vs 96.820 rss
2.808 vs 181.106 index.rdf.22
2.967 vs 233.972 index.rdf.50
3.104 vs 421.921 index.rdf.39
6.247 vs 1839.871 index.rdf.29
2.168 vs 89.000 index.html?xml.19
2.829 vs 178.847 index.rdf.16
2.832 vs 161.458 index.rdf.51
2.636 vs 186.148 index.rdf.24
15.118 vs 7562.889 feed.3
3.090 vs 253.103 index.rdf.10
2.158 vs 205.923 index.html?xml.9
2.976 vs 229.955 index.rdf.1
3.398 vs 446.549 index.rdf.31
3.053 vs 276.134 index.rdf
1.991 vs 169.961 index.html?xml.3
11.469 vs 1167.462 index.html?xml.1
3.876 vs 626.648 index.rdf.30
5.847 vs 1982.844 index.html.3
2.025 vs 167.217 index.html?xml.17
3.242 vs 147.577 index.html?feed=rss2.2
16.571 vs 10932.801 sports?feed=rss2
2.047 vs 70.548 index.html?xml
3.254 vs 276.725 index.rdf.41
1.998 vs 158.414 index.html?xml.11
1.994 vs 210.396 index.html?xml.14
3.120 vs 258.864 index.html?feed=rss2.1
15.106 vs 8625.756 index.html?xml.7
4.855 vs 1182.983 feed.1
1.979 vs 160.850 index.html?xml.16
3.355 vs 428.056 index.rdf.35
11.931 vs 1417.789 feed.4
3.353 vs 307.679 index.rdf.45
3.776 vs 474.214 index.rdf.8
1.795 vs 50.013 index.html?xml.4
10.671 vs 6183.113 music?feed=rss2
3.641 vs 310.649 index.rdf.38

speedparserはclean_html=False、feedparserはfeedparser.PARSE_MICROFORMATS = 0を設定。
単位はmsecで、左がspeedparser、右がfeedparser。正確な数字をとるために何度も回したりとかはしてないけど、別にそんなことしなくても余裕でわかるくらい差が出てる。
ざっくりspeedparserが数十-数百倍くらい速い。feedparserがいかに遅いかよくわかると思う。

もう少しtestcase追加してunittest全部通したらdeployしてみようかと思う。

追記：

一時間以上かかってたクロールが3分もかからなくなった。
しかもその3分の大部分がいくつか返事が返ってこないフィードの待ち時間で、過半数はあっという間に終わってた。

右端のところが新しいparserを使ったところで、見ての通り、ピークが100%にいかなくなってる。互換性の問題で移植できなかった部分はfeedparserのままにしておいたせいで多分まだ高めになってる。その処理自体はioのほうがボトルネックになるから、気にしなくていいかな、と思って放置してる。

追記２：

べ、別に都合のいい部分だけ切り抜いたわけじゃないんだからね、ということでピークがすぎる部分も載せてみる。ピークが小さくなった上に、圧倒的に短くなってるのがよくわかると思う。

pulse audio raop設定 / alsa設定

linux

http://raspberrypi.stackexchange.com/questions/5508/redirect-audio-to-another-airplay-device
にしたがってできたはずなんだけど、rebootしたら動かなくなってた...。
まずはpulse audioからraopで音を飛ばすところを確認する。

$ pulseaudio --log-level=debug -vvvv
(snip)
D: [raop-sink] module-raop-sink.c: Thread starting up
D: [pulseaudio] protocol-dbus.c: Interface org.PulseAudio.Core1.Device added for object /org/pulseaudio/core1/source1
D: [pulseaudio] protocol-dbus.c: Interface org.PulseAudio.Core1.Source added for object /org/pulseaudio/core1/source1
D: [pulseaudio] module-device-restore.c: Could not set format on sink raop.ipanema.local
D: [pulseaudio] module-suspend-on-idle.c: Sink raop.ipanema.local becomes idle, timeout in 5 seconds.
D: [pulseaudio] protocol-dbus.c: Interface org.PulseAudio.Core1.Device added for object /org/pulseaudio/core1/sink1
D: [pulseaudio] protocol-dbus.c: Interface org.PulseAudio.Core1.Sink added for object /org/pulseaudio/core1/sink1
I: [pulseaudio] module.c: Loaded "module-raop-sink" (index: #21; argument: "server=[169.254.171.141]:5000 sink_name=raop.ipanema.local sink_properties='device.description="ipanema"'").
D: [pulseaudio] protocol-dbus.c: Interface org.PulseAudio.Core1.Module added for object /org/pulseaudio/core1/module21
I: [pulseaudio] module-suspend-on-idle.c: Sink alsa_output.platform-bcm2835_AUD0.0.analog-stereo idle for too long, suspending ...
D: [pulseaudio] sink.c: Suspend cause of sink alsa_output.platform-bcm2835_AUD0.0.analog-stereo is 0x0004, suspending
I: [alsa-sink] alsa-sink.c: Device suspended...
D: [pulseaudio] core.c: Hmm, no streams around, trying to vacuum.
D: [pulseaudio] module-udev-detect.c: /dev/snd/controlC0 is accessible: yes
E: [pulseaudio] rtsp_client.c: Connection failed: Connection timed out
I: [pulseaudio] module-suspend-on-idle.c: Sink raop.ipanema.local idle for too long, suspending ...
D: [pulseaudio] sink.c: Suspend cause of sink raop.ipanema.local is 0x0004, suspending

もしやと思い

$ telnet 169.254.171.141 5000
Trying 169.254.171.141...

つながらず、macのほうでは

$ telnet 169.254.171.141 5000
Trying 169.254.171.141...
Connected to ipanema.local.
Escape character is '^]'.

試しにmacからping

$ ping ipanema.local
PING ipanema.local (192.168.0.38): 56 data bytes
64 bytes from 192.168.0.38: icmp_seq=0 ttl=255 time=5.395 ms

raspberry piからairmac expressにtelnet

$ telnet 192.168.0.38 5000
Trying 192.168.0.38...
Connected to 192.168.0.38.
Escape character is '^]'.

avahiが胡散臭い。

pi@rpi ~ $ ping ipanema.local
PING ipanema.local (192.168.0.38) 56(84) bytes of data.
64 bytes from ipanema.local (192.168.0.38): icmp_req=1 ttl=255 time=0.761 ms
64 bytes from ipanema.local (192.168.0.38): icmp_req=2 ttl=255 time=0.801 ms
^C

      • ipanema.local ping statistics ---

2 packets transmitted, 2 received, 0% packet loss, time 1001ms
rtt min/avg/max/mdev = 0.761/0.781/0.801/0.020 ms
pi@rpi ~ $ ping ipanema.local
PING ipanema.local (169.254.171.141) 56(84) bytes of data.
^C

      • ipanema.local ping statistics ---

7 packets transmitted, 0 received, 100% packet loss, time 6008ms

  • 立て続けでやると、二回目以降が何故かlink localのもので解決されるというのが問題らしい。
  • しょうがないからlink localのアドレスも割り振る。
    • force-bindはつけないと、普通のdefault routeあるせいか有効にならない。

pi@rpi ~ $ sudo avahi-autoipd eth0 --force-bind
Found user 'avahi-autoipd' (UID 111) and group 'avahi-autoipd' (GID 115).
Successfully called chroot().
Successfully dropped root privileges.
Starting with address 169.254.7.39
Callout BIND, address 169.254.7.39 on interface eth0
Received conflicting normal ARP packet.
Callout CONFLICT, address 169.254.7.39 on interface eth0
Trying address 169.254.204.240
Callout BIND, address 169.254.204.240 on interface eth0
Received conflicting normal ARP packet.
Callout CONFLICT, address 169.254.204.240 on interface eth0
Trying address 169.254.127.95
Callout BIND, address 169.254.127.95 on interface eth0
Received conflicting normal ARP packet.
Callout CONFLICT, address 169.254.127.95 on interface eth0
Trying address 169.254.99.123
Callout BIND, address 169.254.99.123 on interface eth0
Successfully claimed IP address 169.254.99.123

んで、ping

pi@rpi ~ $ ping ipanema.local
PING ipanema.local (192.168.0.38) 56(84) bytes of data.
64 bytes from ipanema.local (192.168.0.38): icmp_req=1 ttl=255 time=0.748 ms
64 bytes from ipanema.local (192.168.0.38): icmp_req=2 ttl=255 time=0.735 ms
^C

      • ipanema.local ping statistics ---

2 packets transmitted, 2 received, 0% packet loss, time 1000ms
rtt min/avg/max/mdev = 0.735/0.741/0.748/0.028 ms
pi@rpi ~ $ ping ipanema.local
PING ipanema.local (169.254.171.141) 56(84) bytes of data.
64 bytes from ipanema.local (169.254.171.141): icmp_req=1 ttl=255 time=1.47 ms
64 bytes from ipanema.local (169.254.171.141): icmp_req=2 ttl=255 time=0.703 ms

これやったけど、結局音出ない。
そもそもalsaで音出すのがまともに上手く行っていない。
http://raspberrypi.stackexchange.com/questions/639/how-to-get-pulseaudio-running

$ echo "play-file /usr/share/sounds/alsa/Front_Center.wav 0"|pacmd
Welcome to PulseAudio! Use "help" for usage information.

一応たまに音が出る。なんだこの糞は。

Raspberry PIにLCDをつなげる

linux

http://d.hatena.ne.jp/kudzu/20140426/1398523133の続き

root@rpi:~# i2cdetect 0
WARNING! This program can confuse your I2C bus, cause data loss and worse!
I will probe file /dev/i2c-0.
I will probe address range 0x03-0x77.
Continue? [Y/n] y
0 1 2 3 4 5 6 7 8 9 a b c d e f
00: -- -- -- -- -- -- -- -- -- -- -- -- --
10: -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- --
20: -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- --
30: -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- --
40: -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- --
50: -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- --
60: -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- --
70: -- -- -- -- -- -- -- --
root@rpi:~# i2cdetect 1
WARNING! This program can confuse your I2C bus, cause data loss and worse!
I will probe file /dev/i2c-1.
I will probe address range 0x03-0x77.
Continue? [Y/n] y
0 1 2 3 4 5 6 7 8 9 a b c d e f
00: -- -- -- -- -- -- -- -- -- -- -- -- --
10: -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- --
20: -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- --
30: -- -- -- -- -- -- -- -- -- -- -- -- -- -- 3e --
40: -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- --
50: -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- --
60: -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- --
70: -- -- -- -- -- -- -- --

  • まさかの一発OKで、自分でも驚き
  • サンプルのハローワールドのshell script動かしてみた。

root@rpi:~# ./lcdhelloworld.sh
Error: Write failed
Error: Write failed
Error: Write failed
Error: Write failed
Error: Write failed
Error: Write failed
Error: Write failed

  • 原因はアドレスがi2cdetectで3eになっているので、これに合わせる必要がある。
    • コピペしたい人用に下に貼り付けとく。

#!/bin/sh

# LCD の初期化
i2cset -y 1 0x3e 0 0x38 0x39 0x14 0x78 0x5f 0x6a i
sleep 0.3
i2cset -y 1 0x3e 0 0x0c 0x01 i
sleep 0.3
i2cset -y 1 0x3e 0 0x06 i
sleep 0.3

# a. 1行目の文字を出力 "ハロー"
i2cset -y 1 0x3e 0 0x80 b
i2cset -y 1 0x3e 0x40 0xCA 0xDB 0xB0 i

# b. 2行目の文字を出力 "ワールド"
i2cset -y 1 0x3e 0 0xc0 b
i2cset -y 1 0x3e 0x40 0xDC 0xB0 0xD9 0xC4 0xDE i

やたら文字が薄いのはそういうハードウェアなのか、なんか自分が失敗しているのかどちらか不明。

Raspberry PIセットアップメモ

linux

目指すはインターネットラジオ専用デバイス。

Raspberry Pi Type B 512MB ケースセット (clear)

Raspberry Pi Type B 512MB ケースセット (clear)

このケース付き買ったのはいいけど、

Raspberry Pi用 microSDカードアダプタ

Raspberry Pi用 microSDカードアダプタ

これ挿すと、microsdがでっぱって、ケースにぶつかる。ちょっとケース削れば入るかもしれない。

  • SDカードフォーマットして、NOOBのファイルコピーするだけで、初回起動時にインストールするdistroを選べる
  • ユーザpiのパスワードだけ変えておく。
  • piはsudo使える
  • 無線はhttp://wtakuo.tumblr.com/post/48835029766/raspberry-pi-usb-lanにしたがって設定を行った。
  • apはairmac expressでwpa/wpa2でパスワード設定してる
  • ハードウェアは下のUSBのものを使用

BUFFALO 無線LAN子機 コンパクトモデル 11n技術・11g/b対応 WLI-UC-GNM

BUFFALO 無線LAN子機 コンパクトモデル 11n技術・11g/b対応 WLI-UC-GNM

  • うまくいかず。

# ifdown wlan0;ifup wlan0
wpa_supplicant: /sbin/wpa_supplicant daemon failed to start
run-parts: /etc/network/if-pre-up.d/wpasupplicant exited with return code 1
Failed to connect to wpa_supplicant - wpa_ctrl_open: No such file or directory
wpa_supplicant: /sbin/wpa_cli daemon failed to start
run-parts: /etc/network/if-up.d/wpasupplicant exited with return code 1

  • ネットで調べると、単純に設定ファイルのパースエラーなどでも出るエラーらしい。

root@raspberrypi:~# wpa_supplicant -Dwext -iwlan0 -c /etc/wpa_supplicant/wpa_supplicant.conf
ioctl[SIOCSIWENCODEEXT]: Invalid argument
ioctl[SIOCSIWENCODEEXT]: Invalid argument
}'twork=group=CCMP TKIPKIP"
}'.work=group=CCMP TKIPKIP"l interface 'DIR=/var/run/wpa_supplicant GROUP=netdev
You may have another wpa_supplicant process already running or the file was
left by an unclean termination of wpa_supplicant in which case you will need
to manually remove this file before starting wpa_supplicant again.

  • メッセージが無茶苦茶になってるのは、どうやら改行コードがおかしいらしい。
  • perl -pi -e 's/\r/\n/g' wpa_supplicant.confで置き換えできる。間違えて\bと打っちゃったけど、nanoで上書きできた。
  • まだwifiつながらなくて、諦めたので、有線でつないでapt-get update/upgrade
  • rebootしてifdown/ifupしたらつながった
  • apt-get install mpc mpd
  • KCBSのurlを追加

$ curl http://provisioning.streamtheworld.com/pls/KCBSAM.pls
(list of stream url)
$ mpc add http://7279.live.streamtheworld.com:443/KCBSAM_SC
$ mpc play

$ ping rpi.local
PING rpi.local (192.168.0.44): 56 data bytes
64 bytes from 192.168.0.44: icmp_seq=0 ttl=64 time=387.840 ms
64 bytes from 192.168.0.44: icmp_seq=1 ttl=64 time=24.991 ms
64 bytes from 192.168.0.44: icmp_seq=2 ttl=64 time=151.270 ms

pi@rpi ~ $ pactl load-module module-raop-discover
Failure: Module initialization failed
$apt-get install pulseaudio-module-raop
(snip)
pi@rpi ~ $ pactl load-module module-raop-discover
20

  • ごちゃごちゃしてるうちになんか動いた。
  • mpdからraopで音でない
  • paplay /usr/share/sounds/alsa/Front_Center.wavは音が出るけど、超途切れる。全く出ないことも
  • mpdを何回か再起動してるうちに結局動いた。play叩いてから音が出るまでディレイがあったので、短いwavでテストすると再生される前にプロセス終了して音が出ていないかも

後はハードウェア。
http://sea-mountain.hatenablog.jp/entry/2013/09/21/231242
がわかりやすそう？

モンスターハンタースキルシミュレータのアルゴリズム

mh programming

この記事はモンハン Advent Calendar 2013 23日目のエントリーです。

こんにちわ！kudzuです。よろしくっく！
MH4用のスキルシミュレータのMH4スキルシミュ（泣）*1や、お守りスナイプ用のウェブページ*2とかを作ってます。


現在HR289で、好きな武器はライトボウガンです。たまに近接で大剣や片手を使うことはありますが、大体ライトボウガンかヘビィボウガンを使うことが多いです。

MH3Gでは水冷と麻痺が速射できるイケメンのガノシュトロームが愛銃でしたが、今作は属性速射と麻痺速射が使える銃が大きく減った上に、高レベルギルクエの状態異常耐性の上昇率の高さのせいで、麻痺速射が大幅に弱体化してしまい、大変がっかりしてしまいます。
MH4では、普段は烈日やブリザードタビュラを担いでいます。後はラージャン狩りにアイルーヘルドール。あまり使いませんが、ダークデメントや鬼ヶ島も大好きです。
あまり使う人を見ないですが、ライトボウガンは速射、リミカ、サポと、プレイスタイルが幅広い上に、納刀(納銃？)も素早いので、戦闘中に罠や閃光玉なども織り交ぜやすく、機動力が高く、立ち回りがしやすく、ヘビィほどではありませんが、火力も十分高く、とても面白い武器です。
貫通しゃがみヘビィをお使いの方は、増弾リミカタビュラを是非お試しください。フルリロードからの立ち貫通弾20連発は大変爽快です。

スキルシミュレータのアルゴリズム

前置きはこのくらいにして、MH4スキルシミュ（泣）の中のアルゴリズムを少し紹介したいと思います。

MH4の防具は、各部位に300+の装備があり、それに加えて、お守りという、コンピュータで網羅するにも禿げ上がるような組み合わせの数があります*3。それにくわえて、今回開発したシミュレータは、携帯上のJavascriptで動かさなくてはいけないため、デスクトップアプリの十倍くらいのハンデがあります*4。

そんなわけで、一層高速に探索ができるアルゴリズムが必要なわけですが、速度を上げるために、false-negativeが出てしまうと、「このシミュレータはこの装備の組み合わせが出ないぞ！」という話になってしまい、信用がなくなってしまうので、ヒューリスティックを元にアグレッシブな最適化を行うことはできません。

そこで、組み合わせの数を最小限に抑え、枝刈りを保守的に最大限に行い、条件がきついものは枝刈りで素早く結果を出し、条件が緩いものは、最大結果件数で切り上げることで、ある程度実用性がある感じの時間で結果を出すようにしています。

装備の組み合わせを見つける処理はざっくり５つのステップで行われています。

  • フィルタリング
  • グルーピング
  • 装備のスコアリング
  • 装備の選択
  • 装飾品の選択

フィルタリング

まず要求された条件に関係ない防具を除外します。
例えば女性であればアーク一式は装備できなく、逆に男性はフィリアが装備できないので、除外します。他にも剣士・ガンナーの装備の除外、進行度による除外、固定装備・除外装備などの設定を元に、探索対象となる装備を選びます。

グルーピング

残った防具の中から、要求されたスキルポイントの値とスロットが同じものは、組み合わせを減らすために、一つの防具としてまとめます。
例えば切れ味+1で検索した場合、クロオビメイルとアカムトウルンテは両方共匠+2、スロット1なので、同じ防具として扱っても大丈夫なわけです。
同様に、胴系統倍加の防具や空きスロット1-3の防具もまとめられています。

装備のスコアリング

ここからが重要です。
探索を枝刈りするためには、枝刈りするための指標が必要となります。
自分がとったアプローチは、装備にスコアをつけ、スコアの高いものから防具を試し、足りないスキルと、残っている防具のスコアを元に、枝刈りを行うというアプローチです。枝刈りの仕組みについては後で説明します。

スコアの付け方ですが、検索対象となるスキルが装飾品でスロット数いくつ相当か、ということになります。
先ほどの例の切れ味+1とクロオビメイルでは、クロオビメイルは匠+2で、匠+2は匠珠(3)相当なので、3スロット分の価値があり、かつ空きスロットが1あるため、合計4ポイントとなります。

匠珠(2)と匠珠(3)のように、いくつかスキルポイントの設定が異なる装飾品がある場合、スキルポイントごとのスロット数が低いものを採用します。なので、匠+1の防具は、本当は匠珠(2)相当の2スロットですが、ポイントは3 / 2の1.5となります。

装飾品がない潔癖などのスキルポイントは1ポイントあたり100という扱いにすることで、真っ先にそのスキルを持つ防具を試すように作ってあります。何故か剣士の検索してるのに、頭がガンナーばっかりという時は、大抵ガンナー頭のほうがスキルポイントが多めにあるため、優先的に試された結果、検索結果の最大件数全てガンナー頭になってしまった、ということです。

装備の選択

スコアにもとづき、一番スコアの高いものから順番に総当りで試していきます。
まずトリッキーなのは、胴系統倍加。これは胴の防具が選ばれたら順番に空いてる部位に胴系統倍加防具を試しはじめるという仕組みになっています。

そしてこのアルゴリズムで最も重要な枝刈りですが、

足りないスキルポイントのスロット数換算 > 空いている装備のスロット数 + (今選んだ防具のポイント * あと装備できる箇所の数)

となります。わかりにくいので、もう少し例を出しながら説明すると、回避性能+3のスキルをつけるべく、回避性能のスキルポイントを20集めようとした時、防具はスコアが高いものから順番に試されます。
お守りも含めて4つの防具を装備して、スキルポイント10と2スロットがあるとすると、残り２つと空きスロットでで10ポイント相当をカバーしなくてはいけません。2スロットは回避性能+3ポイント相当なので、残り2つの防具で回避性能+7を加えなくてはいけません。試している順番はポイントが高い順なため、次に選ぶ防具が回避性能+3スロット0だった場合、これより後に回避性能+3スロット0より高性能な防具がないことがわかっているため、足りない回避性能4ポイントは絶対に埋めることができない、ということがわかります。ここで枝刈りを行います。
先ほどの数式をこの例で書くと、

2 / 3 * 10 > 2 + (n * 2)
20 / 3 > 2 + (n * 2)
14 / 3 > (n * 2)
7 / 3 > n

と、次の防具が最低2と1/3ポイントの防具でないと無理だということがわかります。回避性能+3は2ポイント相当なので、無理だということがわかります。

そして、逆に

足りないスキルポイントのスロット数換算 <= 装備のスロット数

を満たした場合、装飾品を埋めることで要求スキルを満たすことができるかもしれないので、装飾品を試し始めます。

装飾品の選択

装飾品を試すのは、比較的簡単で、

  • 胴系統倍加がある場合、胴をまず埋める
  • スキル系統ごとにスロット数が最も高い(コストの高い)スキルから試す
    • 満たせないことが早い段階でわかりやすい
  • 同じスキルポイントの装飾品は、スロット数が多いものから試す

という感じで、唯一トリッキーなのは、どの装飾品をどのスロットにはめるかということで、例えば空きスロットが3と2だった場合、1スロの装飾品はどこにはめるべきかでしょうか？3にはめた場合、2-2となり、3スロの装飾品を試せなくなり、２にはめた場合、3-1となり、2スロの装飾品を一つしか試せなくなります。
で、どうすればいいかというと、新しい装飾品を試すたびに、今まで選んだ装飾品を見て、新しい装飾品のスロット数のものを一番多くはめるにはどうすればいいかを計算しなおします。
計算式は1スロは超単純で、空きスロを数えればいいです。3スロはまず丁度いいサイズのスロットを全部埋めて、その後は優先的に2スロを埋めて3スロをあけるようにします。2スロが若干面倒で、同じく丁度良いサイズを全部埋めた後に、3スロに1スロの装飾品をはめて2スロに変換した上で、余った1-2スロの装飾品を*5埋める感じになります。

以上がMH4スキルシミュ（泣）の仕組みでした。

実は頑シミュさんもアルゴリズムを公開しているのですが、そんなことは知らずに自分で作り始めたので、全体的なアプローチが異なっています。もしご興味がある方はこちらも御覧ください。色々と組み合わせるともっと速くなるかもしれません。

次回はyoruakiさんの「地雷について考えます」です。おつかレイア

*1:なんでこんな名前かというと、シミュレータスレの79番だったから

*2:こっちは306番とかだった気がするけど、別に特に名前つけてない

*3:昔は20分かかる検索があったとか。参照：http://www.geocities.jp/masax_mh/logic/page3_hone.html

*4:参照：http://sealedabstract.com/rants/why-mobile-web-apps-are-slow/。シミュレータでも十倍かは不明だけど間違いなく遅い

*5:3スロの装飾品は3スロ以外でははまらないため、ちょうどいいサイズの空きが必ずあるはず

モンハン4闘技大会

mh

そういやモンハン４の話はブログには書いてなかったけど、どちらかというとこっちに書いたほうがいい気がするからこっちに書いていこう。

今日二人で闘技大会埋めてって、とりあえずイヤンクックとケチャワチャ以外はAとって*1、Sもザボアザギルで出せた。二人でやればAは全く難しくはないんだけど、いくつか楽になりそうなポイントを。

  • アルセルタスとゲネル・セルタスはアルセルタスは多分再生しない。
  • ザボアザギルのSは余裕っぽい(後述)
  • ティガレックスの片手は高耳に加えて、回転する攻撃が見てからガードが間に合うので楽。火力はないかも。
    • Ｓは5:30で、太刀使いと二人でやって5:52だった。その後もう１回やったけど、6分越えた。
  • ジンオウガ亜種は笛とハンマーでやったけど、完全に失敗だった気がする
    • 両方共火力低い上、麻痺ハンマーが竜やられと相性悪すぎる
  • イビルジョーは慣れないスラッシュアクスを持ってハンマー使いと行ったけど、9:30いけた。8:00がSだから、割と楽かも
  • レイア・レウス同時は分断さえできれば難しくない。
  • グラビモス二種は撃龍槍当てて、虫棒でぴょんぴょん飛びながら同士討ち狙えば楽。棒初めて使ったけど、それでも余裕なくらい楽だった。

で、Sランクの勲章のためにザボアザギルを何度もやった。4:30でSのところを大剣*2で最初から4:43で、あとちょっとでいけるんじゃないか、と色々武器変えたりして試したりしたけど、結局は大剣*2で3:30くらいで倒せた。工夫したのは本当に開幕だけで、後は割といつも通りにやって、一発で1:30くらい短くなった。多分乗った回数も1-2回だったと思う。

  • 大剣二名
  • 飯食わずに左側から入場。ザボアザギルの後ろから入場になる
  • ダッシュで近づけば気付かれずに溜め開始できる
  • 耳栓あるから、溜め3→横打ち→強溜め3→強薙ぎ払いまでが叩き込める
  • すぐ氷がつく

それまでは氷がつくまでそこそこ時間があったけど、この開幕手順だと、最初に相当なダメージを叩き込めるから、後は抜刀→納刀で普通に立ちまわって、乗った後は溜め3→横切り→強溜め3→強薙ぎ払い、という感じでSいけると思う。

*1:相手がすでにこの２つAとってたから飛ばした