2010-01-31

いつもtimeコマンド

「計測なければ改善なし」ということで、実行してるコマンドがどれくらいかかるのか測定するのは良いことですよね。

sys/user timeとか欲ければ time を使うのが良いですが、コマンドを実行した後で「あ、timeしておけばよかった!」ってことも多いわけですよ。後悔先にたたず。

そんなわけで、私のおすすめは、zsh で実行に6秒以上掛ったコマンドはすべからく時間を表示するようにしてます。これでビルドに一体どれくらい時間がかかったんだろう??って後で悩まなくてすみますヨ。


$ sleep 3
$ sleep 6
<Command took 0m 0s>
$ git clone git://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux-2.6.git
Initialized empty Git repository in /home/rook/OpenSource/linux-2.6/.git/
remote: Counting objects: 1457202, done.
remote: Compressing objects: 100% (234925/234925), done.
remote: Total 1457202 (delta 1211981), reused 1456232 (delta 1211241)
Receiving objects: 100% (1457202/1457202), 317.73 MiB | 903 KiB/s, done.
Resolving deltas: 100% (1211981/1211981), done.
Checking out files: 100% (31564/31564), done.
<Command took 19m 36s>


bashでもできるのかな?誰か教えて!



それにしても GitHub 便利だな。

2010-01-17

経路探索問題

ちょっと前にtwitterで流行ってた(?)人材獲得作戦・4 試験問題ほかの問題を試しに解いてみました。
(今ごろ...)
CとかC++とかRubyとかいるので、他にいなさそうなシェルスクリプトで実装。
Dijkstraのアルゴリズムを使いました。
配列の実装がヒドいので(それだけじゃないが)なんと、実行に3分も掛ります。

しかも、くだらないところ(evalとかスペルミス)でつまづいてしまって、
実装に約2時間もかかってしまった...。

反省:
  • こういうalgorithmicなものをシェルスクリプトで書いちゃだめだろ
  • evalは諸刃の刃
  • 未定義の変数は空文字列に置換される、というのとevalを組み合わせると見付けにくいバグの温床
  • ksh, bash, zshで評価のされかたが微妙に違う(設定によるのかな?)
  • Dijkstraとか忘れてる...
  • A*にしたらもうちょっと早くなるかなー。(もうあきたのでやらないけど)
  • こんな下らないのに2時間も浪費した自分に反省。

なぜシェルスクリプトかって?
それは最近仕事でこんな程度のコードしか書いてないヘタレだからです。




使い方:

問題の図をコピペしてファイルへ保存し、シェルスクリプトの引数として食わせて実行します。
$ ./dijkstra.sh data.txt

-------- data.txt --------
**************************
*S* * *
* * * * ************* *
* * * ************ *
* * *
************** ***********
* *
** ***********************
* * G *
* * *********** * *
* * ******* * *
* * *
**************************


#!/bin/bash
MSG () { echo "$@"; }
DIE () { MSG ERROR "$@"; exit 1; }
x_of () { echo ${1%,*}; }
y_of () { echo ${1#*,}; }

load_data_file () {
local mazename="$1"
local datafile="$2"
local y=0
local xmax=0
[ -r "$datafile" ] || DIE "No data file given"
while read line
do
let y++
for x in $(seq 0 ${#line})
do
local status=${line:$x:1}
local value
case "$status" in
"*"|" ") value="$status";;
"S") value="S"; eval "${mazename}_start=$((x+1)),$y";;
"G") value="G"; eval "${mazename}_goal=$((x+1)),$y";;
esac
eval "${mazename}_DATA_$((x+1))_${y}='$value'"
if [ $x -gt $xmax ]; then
xmax=$x
fi
done
done < "$datafile"
eval "${mazename}_height=$y"
eval "${mazename}_width=$xmax"
}

dump_data () {
local mazename="$1"
local width=$(eval echo \$"${mazename}_width")
local height=$(eval echo \$"${mazename}_height")
echo "---- $mazename: ${width}x${height} ----"
echo " 1 5 1 5 1"
for y in `seq 1 $height`
do
printf '%2d ' $y
for x in `seq 1 $width`
do
printf "%c" "`get_value ${mazename}_DATA $x,$y`"
done
printf '\n'
done
}

get_value() {
local mazename="$1"
local xy="$2"
local value
eval value=\"\$"${mazename}_$(x_of $xy)_$(y_of $xy)"\"
echo "$value"
}

set_value () {
local mazename="$1"
local xy="$2"
local value="$3"
eval "${mazename}_$(x_of $xy)_$(y_of $xy)='$value'"
}

get_adj () {
local xy="$1"
local dir="$2"
local x=$(x_of $xy)
local y=$(y_of $xy)

case $dir in
N) echo $x,$((y-1));;
E) echo $((x+1)),$y;;
S) echo $x,$((y+1));;
W) echo $((x-1)),$y;;
esac
}

get_from () {
local mazename="$1"
local xy="$2"
local value
eval value=\"\$"${mazename}_FROM_$(x_of $xy)_$(y_of $xy)"\"
echo "$value"
}

is_reachable () {
local mazename="$1"
local xy="$2"

local data=$(get_value ${mazename}_DATA $xy)
case "$data" in
'*')
return 1;;
S|G|_|@|' ') return 0;;
*) DIE "BUG: Unknown data in $mazename:$xy='$data'";;
esac
}

is_not_yet_reached () {
local mazename="$1"
local xy="$2"
local value=$(get_value $mazename $xy)
if [ -z "$value" ]
then
return 0
else
return 1
fi
}

search_maze () {
local mazename="$1"
local start="$2"
MSG "$start"
local start_value=$(get_value $mazename $start)

set_value ${mazename}_DATA $start "@"

for dir in N E S W
do
local adj=$(get_adj $start $dir)
local adj_value=$(get_value $mazename $adj)

if is_reachable $mazename $adj
then
if [ -z "$adj_value" ] || [ $adj_value -gt $((start_value+1)) ]
then
set_value ${mazename} $adj $((start_value+1))
set_value ${mazename}_FROM $adj $start
search_maze $mazename $adj
fi
fi
done

set_value ${mazename}_DATA $start "_"
}

backtrace () {
local mazename="$1"
local goal="$2"

local from=$(get_from $mazename $goal)
while [ -n "$from" -a "$(get_value ${mazename}_DATA "$from")" != S ]
do
set_value ${mazename}_DATA "$from" '%'
from=$(get_from $mazename $from)
done
}

trap 'echo; dump_data HOGE; exit' INT

main () {
load_data_file HOGE "$1"

set_value HOGE $HOGE_start 0
search_maze HOGE $HOGE_start

set_value HOGE_DATA $HOGE_start 'S'
set_value HOGE_DATA $HOGE_goal 'G'
backtrace HOGE $HOGE_goal
dump_data HOGE
}

main "$1"