Hatena::ブログ(Diary)

独りの超電波プログラマ このページをアンテナに追加 RSSフィード

2017-01-05

[][] Google App Engine + Django地雷

基本的には https://cloud.google.com/python/django/appengine にそって行けばいいんだけど、地雷を一杯踏んだので書いておく。

2014-05-09

[][] feedparser置き換え

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してみて、2つのパーサが生成するオブジェクトのフィールドを比べてみたところ、更新日時の解釈が若干違うけど、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分の大部分がいくつか返事が返ってこないフィードの待ち時間で、過半数はあっという間に終わってた。

f:id:kudzu:20140510034137p:image

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

追記2:

f:id:kudzu:20140510035521p:image

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

2013-12-23

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

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

こんにちわ!kudzuです。よろしくっく!

MH4用のスキルシミュレータのMH4スキルシミュ(泣)*1や、お守りスナイプ用のウェブページ*2とかを作ってます。

f:id:kudzu:20131223020441j:image

f:id:kudzu:20131223020216j:image

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

MH3Gでは水冷と麻痺が速射できるイケメンのガノシュトロームが愛銃でしたが、今作は属性速射と麻痺速射が使える銃が大きく減った上に、高レベルギルクエの状態異常耐性の上昇率の高さのせいで、麻痺速射が大幅に弱体化してしまい、大変がっかりしてしまいます。

MH4では、普段は烈日やブリザードタビュラを担いでいます。後はラージャン狩りにアイルーヘルドール。あまり使いませんが、ダークデメントや鬼ヶ島も大好きです。

あまり使う人を見ないですが、ライトボウガンは速射、リミカ、サポと、プレイスタイルが幅広い上に、納刀(納銃?)も素早いので、戦闘中に罠や閃光玉なども織り交ぜやすく、機動力が高く、立ち回りがしやすく、ヘビィほどではありませんが、火力も十分高く、とても面白い武器です。

貫通しゃがみヘビィをお使いの方は、増弾リミカタビュラを是非お試しください。フルリロードからの立ち貫通弾20連発は大変爽快です。

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

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

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

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

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

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

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

フィルタリング

まず要求された条件に関係ない防具を除外します。

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

グルーピング

残った防具の中から、要求されたスキルポイントの値とスロットが同じものは、組み合わせを減らすために、一つの防具としてまとめます。

例えば切れ味+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スロットがあるとすると、残り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スロの装飾品を試せなくなり、2にはめた場合、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スロ以外でははまらないため、ちょうどいいサイズの空きが必ずあるはず