URLを自動でリンクにする（smartyプラグイン）

11月 27th, 2007 admin

掲示板などでURLを書き込むと自動でリンクになるような仕組みです。
「[PHP-users 20308]自動リンク」にあったものをそのまま使っております。

smartyのプライグイン形式なのでSmarty/pluginsの中にmodifier.url2link.phpって名前で保存すれば
{$body|url2link}
ってな感じで使えます。

function smarty_modifier_url2link($string)
{
    return ereg_replace("(https?|ftp)(://[[:alnum:]\+\$\;\?\.%,!#~*/:@&=_-]+)", "<a href=\"\\1\\2\" target=\"_blank\">\\1\\2</a>" , $string);
}

Posted in PHP | コメントは受け付けていません。

単純挿入ソート（2分挿入ソート）

11月 27th, 2007 admin

今日は単純挿入ソートです。
前から順にひとつずつ値をチェックしていき、自分より前方に自分より大きな値があればそこに値を挿入するというもの。
直感的にも明らかに遅い感じだし、実際に計算量オーダはO（N^2）なのですが、ほとんど整列が終わっているデータに対しては大変効率がよいということです。

#単純挿入ソート
require 'pp'
before = Time.now
t = Time.now
srand(t.sec ^ t.usec ^ Process.pid)

#ソートする要素数
Num = 10000

def simpleSort(sort)
	(Num-1).times{|sorted|
		#ソート済みでない値を取り出す
		insert = sort[sorted+1];
		#挿入する場所を見つける
		for i in 0..sorted
			if sort[i] > insert then
				break
			end
		end

		if i == sorted then
			next
		end

		#ソート済み領域直後の値を挿入する
		while i <= (sorted + 1)
			temp = sort[i]
			sort[i] = insert
			insert = temp
			i+=1
		end
		}

	return sort
end

#ランダムな値の入った配列を作成
sort = Array.new
Num.times{
	sort.push rand(Num)
}

#ソート前の出力
pp sort

sort = simpleSort(sort);

#ソート後の出力
pp sort

#処理時間
p Time.now - before

Num=10000で実行してみると僕の環境では70秒程度かかる。バブルソートよりは早いということですかね。

2分挿入ソート

単純挿入ソートの改良版で2分挿入ソートというのがあるそうです。上記の「挿入する場所を見つける」という部分をバイナリサーチというのを使って改良したものだということです。バイナリサーチについては第2章で取り扱うということなのでとりあえず省略します。

※このシリーズは私がRubyでアルゴリズムとデータ構造を基礎から学ぶ記録です。全体の目次はこちらへ。

Posted in Ruby, アルゴリズムとデータ構造 | 1 Comment »