2010-05-08

フェルミ推定の元ネタ

フェルミ推定という言葉は聞いたことがある人が多いと思います。
おおざっぱな情報から, 何かの数字をそれなりの精度(普通は有効数字1ケタ以下)で見積もるというものです。「シカゴに調律師は何人いるか?」とか, 「富士山を移動するにはどうすればよいか? (あるいは, 何台のトラックが必要か)?」という問題は有名ですね。MicrosoftやGoogleが採用試験に使ったという話も聞きます。

Wikipediaの説明ではこうなっています。
実際に調査するのが難しいようなとらえどころのない量を、いくつかの手掛かりを元に論理的に推論し、短時間で概算すること。
この推定方法の語源は, 有名な物理学者エンリコ・フェルミがそのような推定が得意だった(あるいは多用した)からと言われてますが, その中でも 「トリニティ原爆実験ので, 空中に紙切れを投げ, 落下する紙片が爆発の衝撃波で吹き跳ばされた距離から, 爆発の規模をかなり正確に見積もった」というエピソードが有名(らしい)です。

その話を聞いて, 具体的にフェルミは爆発の規模を一体どういう計算で見積ったのか興味が湧いたので調べてみました。すると, 計算方法そのものは見付けられなかったものの, その時のエピソードを示すフェルミ自身の文章を見付けました。

これが非常に興味深いので, 下に翻訳して載せてみます。
Webをざっと検索した限りだと, 翻訳した人はまだいないようなので, (少なくともWebでは) 日本初公開!? どうでもいいことだけど。
ちなみに, 結局フェルミが実際にやった方法はわかりませんでした...。
フェルミが実際にやった推定方法を見付けた! とか, 物理に詳しくて, フェルミがやった推定方法の検討がつく方, ぜひ教えて下さい!!




1945年7月16日のトリニティ実験での爆発についての私の観察
E. フェルミ


7月16日の朝、私は爆発地点から10マイルほどのベースキャンプにいた。
爆破の時刻は午前5時半だった。 私は溶接用の黒いガラスのはまった大きな板で顔を保護していた。爆発の最初の印象は, とても強烈な閃光と, 体の露出していた部分に感じた熱だった。直接は爆発の方向を見たりしなかったが, 田舎が突然に真昼よりも明るくなったという印象だった。
その後爆発の方向へ, 黒いガラス越しに目をやると, すぐに炎の塊のようなものが上昇し始めているように見えた。数秒して炎が輝きを失うと, 巨大なきのこのような頭の煙の柱がせり上がって, すぐに雲を越えた。
煙は一番高いところまで到達すると, 風に散らされるまでしばらくそのままだった。


爆発からおよそ40秒後, 衝撃波が到達した。 私は, 衝撃波の通過前,通過中,そして通過後に6フィートの高さから小さな紙片を落してその強度を見積もろうとした。その時は無風状態だったので, 衝撃波が通過中に落下していた紙片がどれくらいの距離変位するかをはっきりと測定できた。移動距離は約 2.5 メートルで, 私はその時これはTNT火薬10キロトン相当の爆発による衝撃波だと見積もった。



ちなみにフェルミの推定では爆発の規模は約10キロトンで, 正確な値は18.9キロトンだったらしいです。
しかしなぜ高さがフィートで距離がメートルなんだ??

2010-05-06

mighttpdはbusyboxのhttpdの1/5のコード量

Haskell で掛れた mighttpd という httpd がある。
CGIもサポートして, なんと536行!
なんと, 今 mew.org はこの mighttpd で運用されてるらしいです。
$ wc -l mighttpd/*.hs
114 mighttpd/Config.hs
90 mighttpd/File.hs
86 mighttpd/LogMsg.hs
84 mighttpd/Mighttpd.hs
2 mighttpd/Setup.hs
65 mighttpd/URLMap.hs
95 mighttpd/mkindex.hs
536 total
一方 組み込みでfootprintの小ささに定評のある busyboxでの実装は 2935 行
$ wc -l busybox/networking/httpd*.c
2421 busybox/networking/httpd.c
344 busybox/networking/httpd_indexcgi.c
170 busybox/networking/httpd_ssi.c
2935 total
機能を厳密に比べたわけじゃないから単純に比較できないけれど busybox の実装と比べて実に 1/5 以下のコード量。
Haskell すごいなぁ!

mighttpd については, 作者の山本さんが去る4/16に Haskellers Meeting 2010 Spring で発表された時のスライド(pdf)が公開されてます。

2010-04-30

FirefoxからKindle向けにPDFを素敵に作成

ブラウザでブログとか見てると, PDFにしてKindleで読みたい! ってことがあるわけです。

手作業でチマチマ印刷するのもタルいなー, と思っていたら, 面白いのを見付けました。Firefoxで, コマンドラインから印刷できるようにする拡張「commandlineprint2

そこで, Webで公開されてる「Real World Haskell」をKindle向けPDFにできないものかと挑戦してみました。(※Ubuntu環境です。Windows/Macでできるか不明)

手順の流れはこんな感じです。
  1. 普段のFirefox環境と設定を別にするために, Firefoxのプロファイルマネージャーを起動して新しいプロファイルを作ります。
  2. Firefoxの「Stylish」拡張で, ページの余計な余白は装飾を削ぎ落します。
  3. user.jsを編集して, 余白や紙のサイズを調整します。
  4. commandlineprint2」インストールしてバッチ処理的にコマンドラインから印刷します。
    firefox -P CmdlinePrint -printprinter kindle -print http://xxx


1. 新しいプロファイルの作成

普段のFirefox環境と設定を別にするためにFirefoxのプロファイルマネージャーを起動して新しいプロファイルを作ります。
firefox -ProfileManager
ここでは "CmdlinePrint" という名前のプロファイルを作ることにしましょう。


2. スタイルシートの調整

Firefoxの「Stylish」拡張で, ページの余計な余白は装飾を削ぎ落します。
commandlineprint2」インストールします。印刷したいページ/サイトに合せて作る必要があるので多少面倒かも知れません。
例えばこんな感じ:

@namespace url(http://www.w3.org/1999/xhtml);
@-moz-document domain("book.realworldhaskell.org") {
body {
margin: 0em !important;
padding: 0em !important;
}
.navheader, .book, .preface, .chapter, .appendix, .bibliography,
.navfooter, .basetemplate, div.preface {
margin: 0em!important;
padding: 0em!important;
width: 95%!important;
}
div.toc, div.navheader, div.rwhfooter, div.navfooter,
.comment, .commenttoggle, .comment_header, .comment_help
{
display: none;
}
div {
margin: 0em;
padding: 0em;
}
}

3. user.jsを編集して, 余白や紙のサイズを調整します。
直接 .mozilla/firefox/xxxxxx.CmdlinePrint/user.js を編集します。
print.printer_kindle.xxxx という設定が "kindle" という名前のプリンタに対応するようです。
/* To omit typing "-printmode PDF" etc */
user_pref("extensions.cmdlnprint.mode", 1); //PDF
//user_pref("extensions.cmdlnprint.mode", 2); //PNG
//user_pref("extensions.cmdlnprint.mode", 3); //PostScript

/* fake printer "drupal pdf dummy" */
user_pref("print.printer_kindle.print_downloadfonts", true);
user_pref("print.printer_kindle.print_edge_bottom", 0);
user_pref("print.printer_kindle.print_edge_left", 0);
user_pref("print.printer_kindle.print_edge_right", 0);
user_pref("print.printer_kindle.print_edge_top", 0);
user_pref("print.printer_kindle.print_in_color", true);

user_pref("print.printer_kindle.print_bgcolor", false);
user_pref("print.printer_kindle.print_bgimages", false);

/* Note that margins are string, while unwritable margins are integer. */
user_pref("print.printer_kindle.print_margin_top", "0");
user_pref("print.printer_kindle.print_margin_bottom", "0");
user_pref("print.printer_kindle.print_margin_left", "0");
user_pref("print.printer_kindle.print_margin_right", "0");

user_pref("print.printer_kindle.print_unwritable_margin_top", 0);
user_pref("print.printer_kindle.print_unwritable_margin_bottom", 0);
user_pref("print.printer_kindle.print_unwritable_margin_left", 0);
user_pref("print.printer_kindle.print_unwritable_margin_right", 0);

user_pref("print.printer_kindle.print_headercenter", "");
user_pref("print.printer_kindle.print_headerleft", "");
user_pref("print.printer_kindle.print_headerright", "");

user_pref("print.printer_kindle.print_footercenter", "");
user_pref("print.printer_kindle.print_footerleft", "");
user_pref("print.printer_kindle.print_footerright", "");

/* paperWidth is also string, as it stands for float (or double). */
user_pref("print.printer_kindle.print_paper_width", "180");
user_pref("print.printer_kindle.print_paper_height", "240");
user_pref("browser.sessionstore.resume_from_crash", false);

4.「commandlineprint2」インストールしてコマンドラインから印刷

commandlineprint2」をインストールします。
すると以下のようなコマンドラインで URL の内容を印刷できるようになります。
firefox -P CmdlinePrint -printprinter kindle -print http://xxx
Real World Haskellのページを全部印刷したいなら, チマチマURLをコピペしてコマンド実行してもいいし, wget とか sed とか awk とか perl とか駆使するのも良いでしょう。
for url in `cat rwh-url-list.txt`
do
firefox -P CmdlinePrint -printprinter kindle -print $url
done
CreativeCommonsだから, PDF化したのを公開しても良いんだよね??
気が向いたら。
...あ, Kindle版が売ってるじゃん! 買えよ!! っていう突っ込みもありですね。


今後の課題とか
  • 出力ファイル名をもっと柔軟に指定したい。
  • 日本語もいけるのかなぁ...?(未挑戦)
  • kindlegen 使うともっと素敵にできる?? (試した限りだと, コマンドラインのレイアウトがメタメタ...)
  • なんでLinux版Firefoxの印刷回りってこんなヘボなのよ!!?? (設定が保存されないとか, GUIで余白設定できないとか)
  • PDFがバラバラのファイルだと, Kindleでメンドクサイ。ひとつに纏めて目次を付けたいな。








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"