[bash] sed だけで 1 次元セルオートマトンを作る

sed コマンドだけで 1 次元セルオートマトンを作るアイデアを
思いついたので、実装してみました。

メインループの中は実質的に sed コマンドしか使っていません。
また、スクリプト全体でも、コマンドは sed, expr, echo の
3 種類だけしか使っていません（for, while などの構文は使っていますが）。

１次元セルオートマトンとは何か、については
セル・オートマトン - Wikipedia の「1次元セル・オートマトン」の項目
をご覧ください。

スクリプト本体と実行方法

スクリプトを示します。

前準備が少し長いですが、
本質は最後のほうの while ループ内です。

#!/bin/bash
# 1D cellular automaton

# rule number
NRULE=90
#NRULE=30
#NRULE=110

# number of generation
NSTEP=300

# half size of width (width = HALFSIZE * 2 + 1)
HALFSIZE=300

# function to repeat string $2 $1 times
rep(){
  n=$1
  s=$2
  ss=""
  i=0
  while [ "$i" != "$n" ]; do
    ss=${ss}${s}
    i=`expr $i + 1`
  done
  echo -n $ss
}

# initial state
zeros=`rep $HALFSIZE 0`
str=$zeros"1"$zeros

next=()
tmp=$NRULE
i=7
while [ "$i" != "-1" ]; do
  next[$i]=`expr 2 + $tmp % 2`
  tmp=`expr $tmp / 2`
  i=`expr $i - 1`
done

# PBM header
echo "P1"
echo `expr $HALFSIZE \* 2 + 1` $NSTEP

# main
istep=0
while [ "$istep" != "$NSTEP" ]; do

  # output PBM
  echo $str | sed -e "s/\([01]\)/\1 /g"

  # calculate next generation
  str=0${str}0   # 0 is boundary
  for i in 1 2 3; do
    str=`echo $str | sed \
      -e "s/111/11${next[0]}11/g" \
      -e "s/110/11${next[1]}10/g" \
      -e "s/101/10${next[2]}01/g" \
      -e "s/100/10${next[3]}00/g" \
      -e "s/011/01${next[4]}11/g" \
      -e "s/010/01${next[5]}10/g" \
      -e "s/001/00${next[6]}01/g" \
      -e "s/000/00${next[7]}00/g"`
  done
  str=`echo $str | sed -e "s/[01]//g"`
  str=`echo $str | sed -e "s/2/0/g" -e "s/3/1/g"`

  istep=`expr $istep + 1`
done

実行方法ですが、

上記をたとえば cellular_automaton.sh という名前で保存して

    $ ./cellular_automaton.sh > rule090.pbm

と実行します。
私の手元 (CPU: Intel Core i7-3770 @ 3.40GHz, OS: Debian wheezy) では
5 秒弱かかりました。

得られた結果を、pbm 形式をサポートしているビューアで開くと
以下のような絵が見えるはずです。
時間は上から下に流れています。

スクリプト内のルール番号 NRULE を変更すると違う絵が描けます。
ルール番号の数字の意味は最初に示した参考文献のとおりです。

縦の長さは NSTEP、横の長さは HALFSIZE で調節できます。

アルゴリズム解説

本質的な部分だけを再掲します。
入力となる str にはセルの状態を表す文字（ここでは 1 または 0）
がセルの数だけ入っています。

  for i in 1 2 3; do
    str=`echo $str | sed \
      -e "s/111/11${next[0]}11/g" \
      (略)
  done
  str=`echo $str | sed -e "s/[01]//g"`
  str=`echo $str | sed -e "s/2/0/g" -e "s/3/1/g"`

3 行目で 111 を 11${next[0]}11 の 5 文字に変換しています。
${next[0]} には 111 の次の世代の文字が入っています。
本来なら

    s/111/${next[0]}/g

と置換したいところですが、
"111" のいずれの文字もあとから隣のセルが
参照するかもしれないので消せません。

これはどういうことかというと、
例えば ...01110... の並びの場合は
左から 011, 111, 110 の次の世代を計算する必要がありますが、
先に 111 を置換してしまうと、その結果は

    ...0(111 の次の世代の文字)0...

となってしまい,
両脇の 011, 110 の計算ができなくなります。

そこで、両脇のセルが参照できるように
上記のように 5 文字に置換しています。
変換後の 5 文字の意味はそれぞれ

    1 文字目、2 文字目、次の世代の文字、2 文字目、3 文字目

となっています。

このように置換した結果だと

    ...011(111 の次の世代の文字)110...

となるので、011, 110 の計算ができます。

別の変数を用意して、次の世代の文字はそこに格納しておけば
こんな複雑なことはしなくていいのですが、
それだとすっきりと書けない気がしたのでやりませんでした。

for ループを 3 周回しているのは、
sed は 1 回のコマンド内で変換した文字列は再変換しない
仕様になっているためです（でないと無限ループが起こりうる）。

これはたとえば

    $ echo 0000 | sed -e "s/00/0/g"
    00

という結果から確認できます。

先ほど示した
...011(111 の次の世代の文字)110... の結果は、
真ん中の 5 文字が変換済なので、
011, 110 の変換はできません。
ということで、3 文字から 1 文字を計算する
1 次元セルオートマトンを 1 ステップ回すためには
3 周回す必要があります。

このとき、変換前の世代と変換後の世代の文字を混ぜないため、
変換後の文字は 2 または 3 になっています。
これはスクリプト中間あたりの

    next[$i]=`expr 2 + $tmp % 2`

がそれに対応しています。

ループ 3 周を抜けたあとは、
もとが ...01110... の場合だと

    ...01311211310...

となります。新旧世代を塗り分けると

    ...01311211310...

となります。
旧世代が 3 文字続く場所がなくなったので、変換は終わりです
（端付近はこの限りではありません。
なので 4 周以上回すと文字数が保存されないことがあります）。

上記のままだと次の変換ができなくなるので

    str=`echo $str | sed -e "s/[01]//g"`

で旧世代の文字を削除し、

    str=`echo $str | sed -e "s/2/0/g" -e "s/3/1/g"`

で 2 を 0 に、3 を 1 に戻します。

SyntaxHighlighter でブログにコードを綺麗に表示

ブログにプログラムソースを載せることがあるのですが、

もう少し綺麗に見せたいと思ったので

[Blogger]ブログ上にプログラムソースを表示させる方法

を参考に SyntaxHighlighter を導入してみました。

テストも兼ねて使ってみたのが以下です。

#!/bin/bash
i=0
while [ $i != 10 ]; do
  i=`expr $i + 1`
  echo $i
done

[雑感] 第一印象が良すぎると、長期的には損をする？

人間には、第一印象が良い相手を信用するようなバイアスがあるように思えます。
そのようなバイアスを利用してお金を巻き上げるのが詐欺でしょう。

第一印象で人を信じてしまう人に、第一印象がとても良い人が出会うと、
高い評価を得ることができるでしょう。
短期的には得をします。

けれども、第一印象に比べて実力のレベルがとても低い人は、
長期的には損をするかもしれません。

前者が顧客で後者がサービス提供者の場合
（仕事に限るつもりはないですが、例えとして）、
信じ込んでしまった顧客は、提供者の仕事のチェックをしなくなるかもしれません。
提供者がミスをしても、それが致命的な状況に拡大するまでなかなか気づきません。

そして、その顧客は「なんて酷いことをするんだ、裏切られた」と言って、
第一印象の良いサービス提供者を逆恨みするかもしれません。

このような事態を避けるには、
自分が顧客側に立つ場合は、
相手の見た目と内容（仕事）のレベルは一致しないと思うようにし、
サービス提供側に立つ場合は、
見た目のレベルが内容のそれを卓越しすぎないように、
内容に強化していくことになるでしょう。

実際には上記の事態はあまり起こらなくて、
内容を活かすような見た目を作れなくてうまくアピールできない、
というのがほとんどなのでしょうけど。

[雑感] スルー力をつける他に、怒りをシフトさせるという提案

巷で「スルー力がほしい」「スルー力をつけたい」とよく聞きます。

私も最近、ある考え方（後日書きます）をするようになってから
少しスルー力がついた気がしますが、
手放しに喜べないと危惧しています。

年をとって、怒る元気がなくなっただけの可能性もあるので。

「ある考え方」だって、怒らない言い訳として、
自分を説得するためにでっち上げただけかもしれません。

細かいことにしょっちゅう腹を立てるのは馬鹿らしいことですが、
「細かいけれども、実は重要なこと」をスルーしてしまうまでに
神経が鈍感になってしまうのもまずいです。

そこで、「腹立たしいこと」を下手に全部なんとかしようとせず、
全体の怒る量を保存しながら、「重要なことには全力で怒る」ほうに
シフトするように仕向ける考え方もありだと思います。

実際に行う場合は、
予め「こういう件は重要なので怒ってよし」と決めておくとよいでしょう。
怒ってから考えると判断基準が揺らぐためです。

ダイエットに例えるなら、食べる量を減らしてひもじい思いをする方法よりも、
糖分や脂肪は制限するけど野菜は無制限、みたいな方法のほうが
本人の精神衛生にもよくて、定着しやすいと思うのです。

xargs コマンドを用いたお手軽並列化

カレントディレクトリにある複数の ps ファイルを eps に変換する場合、
これまでは

    for f in *.ps; do
      name=`basename ${f} .ps`
      convert -rotate 90 ${name}.ps ${name}.eps
    done

という感じでやっていました（bash の場合）。

ですがファイル数が万単位になってくるととても時間がかかるので、
xargs を使って並列化したのがこちらです。

    $ ls *.ps | xargs -I{} basename {} .ps | xargs -P2 -I{} convert -rotate 90 {}.ps {}.eps

拡張子の前の文字列が変換前後で同じであってほしい
（たとえば hoge.ps を変換したものは hoge.eps になってほしい）
ので、basename を挟んでいます。

実行して別窓で top してみると、convert が 2 本走っていることが分かります。