本当にあったgrepが遅い話

自己紹介

• TwitterID

  @techno_neko

• お仕事

  組み込み系

• 所属

  Hokkaido.pm

本当にあったgrepが遅い話

※タイトルは釣りデス

grepは超便利（1/3）

ソートされた配列の中から、しきい値より大きい値の中で、一番小さい値が入っている添字は？

答え   2

grepは超便利（2/3）

ソートされた配列を用意する

# スライドの都合上、データ数は2のn乗
my $cnt = 0x10000;
my @data = map $_ * 5, 1..$cnt;

grepは超便利（3/3）

しきい値より大きな値を抽出して、
一番小さな値が入っている添字を返す

sub grep_search {
    my $th = shift;

    my @tmp = grep {
        $th < $data[$_]
    } 0..(scalar(@data) - 1);
    return ( shift @tmp );
}

超便利！！１

やり方は一つじゃない

例えば・・・？

二分探索

二分探索

例題）28より大きい値の中で、一番小さな値が格納されている添字は？

my @data = ( 5, 10, 15, 20, 25, 30, 35, 40 );
my $i = scalar(@data) - 1; # 探索結果（仮）

二分探索

20は28以下なので、前半は探索範囲から外す

二分探索

この中で一番小さいのは30なので、後半は探索範囲から外す

二分探索

25は28より小さいので選択しない

二分探索

探索完了！

二分探索

コードはこんな感じ

sub binary_search {
    my $th = shift;

    my $i = scalar(@data) - 1;
    my $step = $i;
    while ( 0 < ($step /= 2) ) {
        $i -= $step if $th < $data[$i-$step];
    }

    return $i;
}

速度比較のコード

use v5.10;
use strict;
use warnings;
use Time::HiRes qw/time/;

# スライドの都合上、データ数は2のn乗
my $cnt = 0x10000;
my @data = map $_ * 5, 1..$cnt;

sub binary_search {
    my $th = shift;

    my $i = scalar(@data) - 1;
    my $step = $i;
    while ( 0 < ($step /= 2) ) {
        $i -= $step if $th < $data[$i-$step];
    }

    return $i;
}

sub grep_search {
    my $th = shift;

    my @tmp = grep {
        $th < $data[$_]
    } 0..(scalar(@data) - 1);
    return ( shift @tmp );
}

#
# 確実に存在するデータを入力して、
# その値が存在する要素の添字を得る
#

my $th = 10000;
say 'scalar(@data) = ', scalar(@data);
say '$th = ', $th;

{
    my $start = time();
    my $index = binary_search( $th );
    say '$index = ', $index, ', $data[$index] = ', $data[$index];
    say time() - $start;
}

{
    my $start = time();
    my $index = grep_search( $th );
    say '$index = ', $index, ', $data[$index] = ', $data[$index];
    say time() - $start;
}

実行結果

$ perl aaa.pl
scalar(@data) = 65536
$th = 10000
$index = 2000, $data[$index] = 10005
0.000295877456665039
$index = 2000, $data[$index] = 10005
0.0136890411376953

• Perlのバージョンは5.18.1

• CPU 1.8 GHz Intel Core i5

• メモリ 4GB

まとめ

• 結果ありきで作りました

• grepに恨みとかないです

• grep大好き！

ご静聴、ありがとうございました