にひりずむ::しんぷる - 勝手に添削

2009年11月16日

勝手に添削 - ハッシュを使おう

hail2u.net - Weblog - CSSのプロパティをソートするPerlスクリプト

を見て、「こりゃあかんわ」と思いました。

何があかんのか

この実装だとものすごくの遅いです。

要素数が、少ない場合はまぁそんなに時間がかからないかなーという感じでしょうが、1000行ぐらいのCSSファイルを処理したらいつまでも終わらないでしょう。

どこがあかんのか

問題の個所は以下の場所。

    sub check_order {
      my $line = shift;
      my $order = 0;

      for (my $i = 0; $i <= $#property_order; $i++) {
        if ($line =~ /^\s*$property_order[$i]:/) {
          $order = $i;
          last;
        }
      }

      return $order;
    }

1つの要素番号を得るために、毎回、最大数百回のfor文（このプログラムだと454回）が実行されます。
しかもこれがsortのたびに発生するので、とんでもない回数の処理（最悪でO(n2)*O(n)？よくわからんけど）が発生して、いつまでも終わらないことになります。

どうすればいいのか

こういう場合は、ハッシュを使うのが有効的な手段です。
書き換えると以下のような感じになります。

use strict;
use warnings;

my @property_order = qw(
margin
margin-top
# snip...
);

# key => property, value => index のハッシュを生成
my %property = do {
    my $i = 0;
    map { $_ => $i++ } @property_order;
};

my $css = join "", <STDIN>;
$css =~ s/{(.*?)}/"{".sort_properties($1)."}"/imgse;

print $css;

sub sort_properties {
    my @formatted = sort {
        check_order($a) <=> check_order($b)
    } split "\n", shift;
	
    return join("\n", @formatted) . "\n";
}

sub check_order {
    my $line = shift;
    my $order = 0;
	
    if ($line =~ /^\s*(.+)\s*:/) {
        if ($property{$1}) {
            $order = $property{$1};
        }
        else {
            warn "Unkown property $1";
        }
    }
	
    return $order;
}

解説

# key => property, value => index のハッシュを生成
my %property = do {
    my $i = 0;
    map { $_ => $i++ } @property_order;
};

の部分でkeyがproperty名でvalueが配列の要素数のハッシュを生成しています。

sub check_order {
    my $line = shift;
    my $order = 0;
    
    if ($line =~ /^\s*(.+)\s*:/) {
        if ($property{$1}) {
            $order = $property{$1};
        }
        else {
            warn "Unkown property $1";
        }
    }
    
    return $order;
}

check_order関数ではforループをやめ、単純にハッシュへのアクセスだけとなるため、常に計算は1回ですみます。
あとはついでに存在しないpropertyに警告だすとかついかしましたが。

それから、sort_propertiesのなかのさらにsortの中にcheck_orderがあるのは、よろしくありません。
この書き方だと、check_orderはあたかもsortの中でしか使えないように見えますが、実際はコンパイル時にシンボルテーブルに登録されて、どこからでも使えます。
あと、sortの中がごちゃごちゃして、処理が分かりづらいので、素直に外に書いた方がいいでしょう。

まとめ

なにかいろいろと偉そうなこと書きましたが、「ハッシュをうまくつかうといいよ」というお話でした。

情報処理とかようしらんので、O(n)とかはてきとーです。

追記

id:kitu @formatted = のところでシュオーツ変換できそう。

~~ちょっと括弧が入ってダサい感じなんですがこんな感じですかね。~~

sub sort_properties {
    return join("\n" => sort {
        check_order($a) <=> check_order($b)
    } split "\n", shift) . "\n";
}

追追記

自分がダサいことが判明しました！！シュオーツ変換についてはコメント参照のこと！！

シュオーツ変換を使えば、check_orderも一回ですむので更に高速です。アルゴリズムはとても大事ですね

修正してgistにあげました

gist: 236860 - GitHub

すぐわかるオブジェクト指向 Perl (大型本)

深沢千尋

おすすめ平均 star

タグ: Perl CSS

xaicron at 09:07│Perl

編集

コメント一覧

1. Posted by 北村(kits) 2009年11月17日 00:20

シュオーツ変換(シュワルツ変換)は、ソート対象となる値の計算(ここでは check_order() )を先に済ませてからソートするという手法です。
http://perl-mongers.org/2008/05/schwartzian_transform_and_orcish_maneuver.html

この場合だと以下のような感じです。

my @formatted =
map { $_->[0] }
sort { $a->[1] <=> $b->[1] }
map { [$_, check_order($_)] } split "\n", shift;

2. Posted by xaicron 2009年11月17日 19:30

おおお！ありがとうございます！！

「すぐわかるオブジェクト指向 Perl」にも書かれていたのにすっかり忘れてました。
http://www.amazon.co.jp/o/ASIN/4774135046/