rcmdnk's blog

聖獣配列(上)

sentaku のissueで遅くなったというのをもらったので見てみたところ、 配列の初期化のところで遅くなってました。

ちょっと意識してないところだったのでメモ。

Sponsored Links

シェルスクリプトでの配列

Bashなどでは()を使って

x=(a b c)

みたいにすると

$ echo ${x[0]}
a
$ echo ${x[1]}
b
$ echo ${x[2]}
c

と言った配列を作ることが出来ます。 ただし、Zshではデフォルトでは配列番号は1から始まります。

Bashの様に0からにするには

setopt ksharrays

と、ksharraysオプションをセットしておく必要があります。

要素を加えるには

$ x=(${a[@]} d)

みたいに既存の要素+新しい物、みたいにして()に入れる方法があります。

()に入れた時の区切りは$IFSの値で、この値で区切られたところが一つの要素になります。 (デフォルトでは空白、タブ、改行。)

また、各要素に直接入れることも出来て、

$ x[0]=1

の様にします。この時、別に0から埋まってなくても大丈夫で、

$ echo ${x[@]}

$ x[0]=0
$ x[5]=5
$ echo ${x[0]}
0
$ echo ${x[1]}

$ echo ${x[5]}
5
$ echo ${x[@]}
$ echo ${x[@]}
0 5
$ echo ${#x[@]}
2

みたいな感じで途中にも直接入れられます。

配列の初期化

何も入ってない配列を作りたければ

$ x=()

と空の()を使えばOK。

これを10個の0を持つ配列にしたい時、 ()で追加していく方法だと

$ x=(); for i in $(seq 0 9);do x=(${x[@]} 0);done

みたいにします。 (勿論10個くらいなら直接(0 0 0 ...)を代入しても良いしその方が下に書くように 速いですが数が変化するときやもっと大量の時を考えて。)

要素を直接入れてく方法だと

$ x=(); for i in $(seq 0 9);do x[$i]=0;done

とも出来ます。

前者の方がZshで1から番号が始まる場合や 途中から入れる場合に何も考えなくて楽なんです。

あと、上にも書いたように、シェルスクリプトの配列だと途中の番号が抜けてる場合もあるので、 最大数の後に追加しようとして、

$ x=()
$ x[0]=0
$ x[2]=2
$ x[${#x[@]}]=x
0 x

みたいに、要素数を${#x[@]}で取ってきて入れようとすると すでに入っているところに被ってしまう可能性があります。

ただし、大量の要素に対して行うとき、2つの方法はかなり速度が違います。

Mac OS X 10.11、Bash 4.3.42(1)-releaseでやってみると

$ time (x=(); for i in $(seq 0 999);do x=(${x[@]} 0);done ;echo ${#x[@]})
1000

real    0m1.427s
user    0m1.360s
sys     0m0.065s
$ time (x=(); for i in $(seq 0 999);do x[$i]=0;done ;echo ${#x[@]})
1000

real    0m0.012s
user    0m0.010s
sys     0m0.003s

こんな感じで1000個位の要素だと100倍違いますが、 100個位だと10倍位の差で、 逆に10000個にするとx[$i]=0の方は0.1秒程で終わりますが、 x=(...)の方は10秒経っても終わりません。

Zsh (5.2)でも

$ time (x=(); for i in $(seq 0 999);do x=(${x[@]} 0);done ;echo ${#x[@]})
1000
( x=() ; for i in $(seq 0 999); do; x=(${x[@]} 0) ; done; echo ${#x[@]}; )  0.15s user 0.02s system 99% cpu 0.171 total
$ time (x=(); for i in $(seq 0 999);do x[$i]=0;done ;echo ${#x[@]})
zsh: x: assignment to invalid subscript range
( x=() ; for i in $(seq 0 999); do; x[$i]=0 ; done; echo ${#x[@]}; )  0.00s user 0.00s system 96% cpu 0.007 total

な感じで100倍以上違っています。

ということで、シェルスクリプトで配列に値を代入するときは ()を使って拡張していく方法は使わず x[$i]の様な直接代入を使って行くほうが圧倒的に高速化出来ます。

使い勝手は色々()の方が良いんですが、 なるべくそれに頼らなくて良いように (配列の穴を開けるようなことをしないとか、Bash/Zsh共通のスクリプトではsetopt ksharraysをしておくとか) して行くべきです。

ちなみに、すでにある配列を他の配列にコピーする場合は

$ y=(${x[@]})

の様に渡すのが圧倒的に速いです。 (ループを回して一つ一つ渡すのに比べて。)

感じとしては()で拡張していく方法だと 毎回全ての要素を上書きしていくことをするので大変なのかな、と。 まあ考えれば当たり前ですが。

ループの方法による速度

最初この問題が起きた時に、原因はループの回し方だと思いました。

というのも、この前の変更で、

for((i=0; i<10000;i++));do

な方法から

for i in $(seq 0 999);do

みたいな方法へ変更したからです。

前者はBashでは動くんですがZshでは動きません。 (何故か動くと勘違いしてたっぽい。)

ただ、もしこれがネックだとBash専用でも良いから戻すかな、とか思ってたんですが そんなことはありませんでした。

{0..99999}whileを使った方法を含めてチェックしてみると(Bash 4.3.32)

$ time (x=();echo pre: ${#x[@]}, ${x[0]}, ${x[99999]};for i in $(seq 0 99999));do x[$i]=0;done;echo post: ${#x[@]}, ${x[0]}, ${x[99999]})
pre: 0, ,
post: 100000, 0, 0

real    0m0.843s
user    0m0.792s
sys     0m0.055s

$ time (x=();echo pre: ${#x[@]}, ${x[0]}, ${x[99999]};for((i=0; i<100000;i++));do x[$i]=0;done;echo post: ${#x[@]}, ${x[0]}, ${x[99999]})
pre: 0, ,
post: 100000, 0, 0

real    0m1.327s
user    0m1.243s
sys     0m0.080s

$ time (x=();echo pre: ${#x[@]}, ${x[0]}, ${x[99999]};i=0;for i in {0..99999};do x[$i]=0;done;echo post: ${#x[@]}, ${x[0]}, ${x[99999]})
pre: 0, ,
post: 100000, 0, 0

eal 0m0.882s user 0m0.821s sys 0m0.058s

$ time (x=();echo pre: ${#x[@]}, ${x[0]}, ${x[99999]};i=0;while [ $i -lt 100000 ];do x[$i]=0;((i++));done;echo post: ${#x[@]}, ${x[0]}, ${x[99999]})
pre: 0, ,
post: 100000, 0, 0

real    0m2.212s
user    0m2.087s
sys     0m0.116s

time (x=();echo pre: ${#x[@]}, ${x[0]}, ${x[99999]};i=0;while(($i < 100000));do x[$i]=0;((i++));done;echo post: ${#x[@]}, ${x[0]}, ${x[99999]})
pre: 0, ,
post: 100000, 0, 0

real    0m1.524s
user    0m1.425s
sys     0m0.091s

な感じでむしろseqを使う方法が一番速いです。

{0..99999}の方法はBash機能で完結出来て 同じくらい速いですが、 この方法では 中に変数を使えないので固定数のみ、という欠点があって、 seqの方を使うほうが良いです。

2重括弧を使ったforwhileは同じくらい。 whileの方が別にiをインクリメントしなくては行けない分遅い?

ちなみに、whileの2重括弧の方で、iをインクリメントするのに ((i++))の代わりにi=$(expr $i + 1)exprを使うと果てしなく遅くなります。

[]で評価する方法は大分遅い結果となっています。

というわけで、このseqにした変更はむしろスピードアップになっていたようです。

Sponsored Links
Sponsored Links

« Vimのdiffモード関連Tips BatteryBar: Windowsでタスクバーにバッテリーの残り時間表示 »