2009年3月アーカイブ

Movable Type 4.25 が出てた ので、ちょっと遅ればせながら更新しました。コミュニティ機能が無い無償版を使っているので、多分セキュリティfixくらいだと思いますけど。

最近、仕事でDSLの機能拡張をする機会があったのですが、構文解析とかその辺の話はあんましよく知らない(EBNFは適当に書けるし、 boost::spirit も触ったことはあるけど、本格的なのは初めて。ちなみに仕事のはRubyの Racc が使われてる)ので、手習いにPerlで使えるパーサジェネレータで逆ポーランド記法の電卓を書いてみようと思い立った。

EBNF は超有名な

expr: expr expr '+'
    | expr expr '-'
    | expr expr '*'
    | expr expr '/'
    | NUM

です。

とりあえず、Perlのパーサジェネレータで有名だと思っているのは Parse::RecDescent なので、早速

...

...

動いてくれないので色々調べてみたら P::RD が使ってる再帰下降法は 逆ポーランド記法の様な 最左再帰 の構文を処理できないということでした。ションボリ

気を取り直して LR法を使っているパーサジェネレータということで、 Parse::Eyapp を試してみた

前回 の追試。

List::Compareに食わす前に sort+uniq したものと、 IO::*printするときにjoin("\n", LIST) で一気に食わしたものとを追加しておうちマシン(Core2Duo 3GHz, 3GBメモリ)で再計測してみました。(後、後ろ切れるので普通のparagraphで..)

Benchmark: timing 10000 iterations of IO::Scalar(join)+Search::Dict, IO::Scalar+Search::Dict, IO::String(join)+Search::Dict, IO::String+Search::Dict, List::Compare, List::Compare(sorted), hash, hash+exists...
IO::Scalar(join)+Search::Dict: 32 wallclock secs (31.75 usr + 0.00 sys = 31.75 CPU) @ 314.96/s (n=10000)
IO::Scalar+Search::Dict: 39 wallclock secs (38.56 usr + 0.00 sys = 38.56 CPU) @ 259.32/s (n=10000)
IO::String(join)+Search::Dict: 32 wallclock secs (31.83 usr + 0.00 sys = 31.83 CPU) @ 314.19/s (n=10000)
IO::String+Search::Dict: 51 wallclock secs (50.67 usr + 0.00 sys = 50.67 CPU) @ 197.35/s (n=10000)
List::Compare: 83 wallclock secs (82.03 usr + 0.05 sys = 82.08 CPU) @ 121.84/s (n=10000)
List::Compare(sorted): 110 wallclock secs (109.73 usr + 0.14 sys = 109.87 CPU) @ 91.01/s (n=10000)
hash: 22 wallclock secs (21.30 usr + 0.05 sys = 21.34 CPU) @ 468.52/s (n=10000)
hash+exists: 21 wallclock secs (21.00 usr + 0.02 sys = 21.02 CPU) @ 475.83/s (n=10000)

IO::*joinしてから食わすのは、ずいぶんと早くなりますね。その代わりメモリ食うんでしょうけど。

逆に、事前にsort+uniqしたList::Compare版はえらく遅くなってしまってます。余計なことすんなってか..

元ネタ の方にコメントもしてますが..
Perlで2配列の積集合(Intersection)を取る方法を何個か考えたので、Benchmark取ってみた。

use strict;
use warnings;
use Benchmark;
use List::Compare;
use IO::String;
use IO::Scalar;
use Search::Dict;
use List::MoreUtils qw/uniq/;

my @l1 = map { int rand 1000 } 1..1000;
my @l2 = map { int rand 1000 } 1..1000;

timethese(10000, {
    q/List::Compare/ => sub {
      List::Compare->new(\@l1,\@l2)->get_intersection;
    },
    q/hash/ => sub {
      my %in_l1 = map { $_ => 1 } @l1; 
      grep { $in_l1{$_} } @l2;
    },
    q/hash+exists/ => sub {
      my %in_l1 = map { $_ => undef } @l1;
      grep { exists $in_l1{$_} } @l2;
    },
    q/IO::String+Search::Dict/ => sub {
      my $ios = IO::String->new;
      $ios->print($_,"\n") for (uniq sort {$a cmp $b} @l1);
      grep { -1 != look $ios, $_ } @l2;
    },
    q/IO::Scalar+Search::Dict/ => sub {
      my $ios = IO::Scalar->new(\my $data);
      $ios->print($_,"\n") for (uniq sort {$a cmp $b} @l1);
      grep { -1 != look $ios, $_ } @l2;
    },
  }
);

Search::Dictは二分木検索の実装です。が、辞書ファイルからの検索を目的としてるモジュールのようなので、一旦辞書を作る必要があります。

手元のマシン(PenD 3.20GHz, メモリ3.5GB)での実行結果は、

Benchmark: timing 10000 iterations of IO::Scalar+Search::Dict, IO::String+Search::Dict, List::Compare, hash, hash+exists...
IO::Scalar+Search::Dict:  83 wallclock secs ( 81.27 usr + 0.03 sys =  81.30 CPU) @ 123.01/s (n=10000)
IO::String+Search::Dict: 110 wallclock secs (108.52 usr + 0.02 sys = 108.53 CPU) @  92.14/s (n=10000)
          List::Compare: 167 wallclock secs (166.36 usr + 0.23 sys = 166.59 CPU) @  60.03/s (n=10000)
                   hash:  35 wallclock secs ( 34.64 usr + 0.05 sys =  34.69 CPU) @ 288.28/s (n=10000)
            hash+exists:  34 wallclock secs ( 33.75 usr + 0.08 sys =  33.83 CPU) @ 295.61/s (n=10000)

やっぱり hash 強いなー。 そして分かりやすさではダントツの List::Compare はスピード面では散々な結果に..

元ネタ: ``Sorting XSLT output items'' -- comp.text.xml

index.xml

<root>
  <link href="data1.xml" />
  <link href="data2.xml" />
</root>

data1.xml

<root>
  <data index="6">VI</data>
  <data index="2">II</data>
</root>

data2.xml

<root>
  <data index="1">I</data>
  <data index="4">IV</data>
  <data index="2">II</data>
  <data index="10">X</data>
</root>

上記のindex.xmlに対して下記のXSLTを適応すると、 data1.xml/data2.xml の 全ての /root/data/@index に対してソートが適応されます。

<xsl:stylesheet version="2.0"
  xmlns:xsl="http://www.w3.org/1999/XSL/Transform"
  exclude-result-prefixes="xsl"
  >

  <xsl:output method="xml" />

  <xsl:template match="/" >
    <root>
      <xsl:for-each select="document(root/link/@href)/root/data">
        <xsl:sort select="./@index" data-type="number"/>

        <data><xsl:value-of select="." /></data>
      </xsl:for-each>
    </root>
  </xsl:template>

</xsl:stylesheet>

結果

<root>
  <data>I</data>
  <data>II</data>
  <data>II</data>
  <data>IV</data>
  <data>VI</data>
  <data>X</data>
</root>

XSLT2.0勧告の§16.1 をみたら、document() はuriのsequenceを引数に取るって書いてある。いやー、知らんかった.

AUTHOR

  • turugina (虎王 剱奈)
  • E-mail: turugina {at} floralcompany.jp
  • pixiv
  • ニジエ

2014年5月

        1 2 3
4 5 6 7 8 9 10
11 12 13 14 15 16 17
18 19 20 21 22 23 24
25 26 27 28 29 30 31

アーカイブ

OpenID対応しています OpenIDについて
Powered by Movable Type 5.2.10

- 警 告 -

本サイトにはいわゆる「18禁画像」(イラスト)へのリンクが存在します。 未成年の方や、その手の画像に不快感を覚える方は、 該当記事(「えちぃの」及び「ちょっとえちぃの」カテゴリ) をご覧にならないようお願いいたします。

上記を理解した上で非表示のブログパーツを表示する
あわせて読みたいブログパーツ
ついった
drawr/pixiv/twitpic