rcmdnk's blog

grep Pocket Reference (Pocket Reference (OReilly))

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

Sponsored Links

やりたいこと

array.sh
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#!/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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#!/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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#!/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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
$ ./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)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
$ ./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

結果のまとめ

BSD(Mac)の場合にはgrepの方がuser時間に加えて sysで使ってる時間がだいぶ増えて結果倍以上時間がかかっています。

また、当たり前ですが、早い段階で帰る物が多ければ配列使ってやるものが 圧倒的に速くなっています。

Linux(Debian)の場合にはgrepを行うとuser+sysの時間は短くなってますが、 realでの時間はこれらと比べて大幅に大きくなってます。

arrayでの方が殆どuser+sys=realな状態なのでこの時に 他の大きなプロセスが動いていたわけではないはずですが、 grepを呼ぶのに余計な負荷がかかる?のかも(適当)。 (BSDの場合と計測する対象が違うだけな感じもしますがよく分かってない。)

いずれにしろ実際に掛った時間はやはりgrepを使ったほうが長くなっています。

ということで、取り敢えず配列をぶん回しても grpe等余計な物を呼ぶよりは速そうだ、ということです。

ただ、Linuxの方の結果を見るとgrepの方がuser+sysの時間が圧倒的に短くなってるので 環境によっては速くなるのかもしれません。

Sponsored Links
Sponsored Links

« brew-fileのデフォルトをpython versionにした iTerm2上でHyperSwitchなどが使えなくなったのでターミナル.appに乗り換えた »