今日の井原

　日曜日だけどヒマだったので、「もぶろげっと」のソースコードを開いてリファクタリングをしていた。リファクタリングというほど偉そうなものでもないんだけど、バックエンド部分の動作をもう少し軽くしたいと前々から思っていたので。

　バックエンドのソースコードは概ねC#で書いてある。これを適当に解析してみると、HTMLからタグを除去する部分で割りと大きな処理時間を喰っているということが分かった。さあ、何とかしよう。
　
　（まあ、本当はWebからリソースをダウンロードする部分や、文字コードの変換をしている部分のほうが時間を喰ってるんだけど。ダウンロードはほとんど相手サーバとのレスポンスタイムの問題だし、文字コード変換はライブラリに丸投げしているので手が出せず、自分で弄れる範囲で手っ取り早そうなのがそこだった。）

　HTMLからタグを除去するのに、今まではこんなコードを書いていた。

		private string RemoveTag(string article)
		{
			Regex regex = new Regex("<[^<]*>");
			MatchCollection matchcollection = regex.Matches(article);//タグのリストをget

			if(matchcollection.Count != 0) 

				for(int i=0; i
					article = article.Replace(matchcollection[i].Value, "");

			return article;

		}

　正規表現でタグをすべて抜き出して、String.Replaceで空文字列に置換していくというアルゴリズム。やってることをこうやって書き下しただけで如何にも重そうで富豪的って感じがする。String.Replaceは内部では文字列の一致検査をやってるやや重めの関数で、これをタグの数だけ実行するのは能率が悪すぎる。よく今までこんな関数使ってたな……。

　さあ、どう書き直そうか。文字列ってデータ構造としては文字の配列だから、いちばん高速にするには先頭から末尾まで一回だけ走査して終わるというのが望ましいだろうと思われる。タグの除去をするにはbool型の状態を一つだけ、つまり今タグの中に居るかどうかだけを持てばいいので楽勝だ。じゃあ書いてみようか。というので下のようなコードが出来た。

		private string RemoveTag2(string article)
		{
			char[] chars = article.ToCharArray();
			bool isTag = false;
			StringBuilder result = new StringBuilder();

			for ( int i=0; i
				if ( chars[i] == '<' )

					isTag = true;

				else if ( chars[i] == '>' )

					isTag = false;

				else if ( !isTag )

					result.Append( chars[i] );

			return result.ToString();

		}

　とりあえず、２つ関数が書けたので比較してみる。
　今日の井原（このblog）のトップページのHTMLを使って、両方の関数でそれぞれ１００回ずつ処理をさせて、その時間を出してみた。

　RemoveTag 8.843
　RemoveTag2 0.078 (sec)

　うへ。桁が２つ違うのか。やっぱこの手の関数はローレベルなアルゴリズムを自分で書いた方が良いね。めでたしめでたし。

　……とは行かないのだった。続く。

You can ping this entry by using http://windy.ac/MT/mt-tb.cgi/792 .