Bashでループを回すのとgrepで検索する時間の比較

grep Pocket Reference (Pocket Reference (OReilly))

大量の配列の中からいくつか該当するものを探して提示するようなスクリプトを書こうとするときに簡単な方法として単に配列に詰めて一つ一つ比較するのと全体を1つの文字列にしてしまってgrepするのはなんとなくgrepした方が一気で早そうだったと思ってましたがそうでもなかったと言う話。

やりたいこと
配列でチェックしていく方法とgrepで見つける方法の時間のかかり方
- Macでやった場合
- Linuxでやった場合
結果のまとめ

やりたいこと

array.sh

#!/usr/bin/env bash
array_check () {
  for i in ${check[@]};do
    if [ $1 -eq $i ];then
      return 1
    fi
  done
  return 0
}

check=($(seq 500 600))
num=($(seq 1 10000))
for n in ${num[@]};do
  array_check $n
done

こんなスクリプト。 1から10000について調べて、該当するもの(500から600)には成功(0)、そうでないものには失敗(1)を返す関数を適用しています。 (実際に使うときはarray_checkのあとでif [ $? -eq 0 ];then... とかで進めて行きます。)

配列でチェックしていく方法とgrepで見つける方法の時間のかかり方

これをgrepを使って一気にチェックした方が速いんじゃないかと思って

grepcheck.sh

#!/usr/bin/env bash
grep_check () {
  local i=$1
  local j
  if echo " ${check[*]} "|grep -q " $1 ";then
    return 1
  fi
  return 0
}

check=($(seq 500 600))
num=($(seq 1 10000))
for n in ${num[@]};do
  grep_check $n
done

こんな感じの物を考えました。ここでは全て数字で空白は含まない文字列なので、配列の全表示に加えて両端に空白を入れることで全て N の様に両側が空白でそれを含める事で全ての数字をgrepで区別出来ます。

配列で一つ一つチェックしてくのと違って一発(パイプでつなぐので2発?)コマンドなので速いかな、と思ったわけです。

これを試して見るために下みたいなスクリプトを考えて試してみます。

チェックする数を10000, 20000, 40000と変えたものと、後半ではarray_checkの方で全て一番最初に帰る様に常にチェック対象を1でチェックする数も1だけにしています。

check.sh

#!/usr/bin/env bash
array_check () {
for i in ${check[@]};do
  if [ $1 -eq $i ];then
    return 1
  fi
  done
  return 0
} # }}}
grep_check () {
  local i=$1
  local j
  if echo " ${check[*]} "|grep -q " $1 ";then
    return 1
  fi
  return 0
} # }}}

check=($(seq 500 600))

for max in 10000 20000 40000;do
  time {
    echo "array: $max"
    num=($(seq 1 $max))
    for n in ${num[@]};do
      array_check $n
    done
    echo
  }
  time {
    echo "grep: $max"
    num=($(seq 1 $max))
    for n in ${num[@]};do
      grep_check $n
    done
    echo
  }
done

echo "###############"
echo "return at 1"
echo

check=1

for max in 10000 20000 40000;do
  time {
    echo "array: $max"
    num=($(seq 1 $max))
    for n in ${num[@]};do
      array_check 1
    done
    echo
  }
  time {
    echo "grep: $max"
    num=($(seq 1 $max))
    for n in ${num[@]};do
      grep_check 1
    done
    echo
  }
done

grep自体もBSDとGNUで違ったりもするので、 BSD(Mac)とLinux(Debian)でチェックしてみました。

Macでやった場合

Mac OSX 10.9.5
bash 4.3.26
grep (BSD grep) 2.5.1-FreeBSD

$ ./check.sh
array: 10000

real    0m10.606s
user    0m10.470s
sys     0m0.027s

grep: 10000

real    0m29.172s
user    0m17.108s
sys     0m20.906s

array: 20000

real    0m24.255s
user    0m22.790s
sys     0m1.238s

grep: 20000

real    0m57.901s
user    0m33.296s
sys     0m42.242s

array: 40000

real    0m42.233s
user    0m39.909s
sys     0m2.145s

grep: 40000

real    1m36.241s
user    1m0.850s
sys     1m12.033s

###############
return at 1

array: 10000

real    0m1.764s
user    0m1.751s
sys     0m0.009s

grep: 10000

real    0m23.679s
user    0m15.030s
sys     0m17.628s

array: 20000

real    0m3.342s
user    0m3.321s
sys     0m0.018s

grep: 20000

real    0m51.142s
user    0m30.880s
sys     0m38.151s

array: 40000

real    0m7.286s
user    0m7.222s
sys     0m0.044s

grep: 40000

real    1m41.529s
user    1m0.430s
sys     1m16.004s

Linuxでやった場合

Debian 7.6
grep (GNU grep) 2.12
GNU bash, version 4.2.37(1)-release (x86_64-pc-linux-gnu)

$ ./check.sh
array: 10000

real    0m11.317s
user    0m11.041s
sys     0m0.268s

grep: 10000

real    0m13.048s
user    0m1.072s
sys     0m2.164s

array: 20000

real    0m23.659s
user    0m22.613s
sys     0m1.032s

grep: 20000

real    0m32.762s
user    0m2.216s
sys     0m5.328s

array: 40000

real    0m47.732s
user    0m45.647s
sys     0m2.060s

grep: 40000

real    1m54.354s
user    0m4.100s
sys     0m16.217s

###############
return at 1

array: 10000

real    0m1.921s
user    0m1.908s
sys     0m0.008s

grep: 10000

real    0m33.102s
user    0m1.780s
sys     0m3.960s

array: 20000

real    0m3.847s
user    0m3.816s
sys     0m0.032s

grep: 20000

real    1m6.348s
user    0m2.592s
sys     0m8.433s

array: 40000

real    0m7.708s
user    0m7.708s
sys     0m0.000s

grep: 40000

real    2m14.146s
user    0m7.416s
sys     0m15.985s