ログの集計

ときどきの雑記帖 めぐりあい電脳空間篇 2010年3月(上旬) からですが、「きっと、さいとうさんがきっちりしたのを書いてくれるに違いない :)」とありましたので、私なりに書いてみます。 元の問題は awk / sed のテキスト処理について - Coding Edge会議室 からですが、「ときどきの雑記帖」で言っているところは「stable stable」というタイトルから判断して、「戦場ヶ原ひたぎ」・・・ではなく、「安定ソート」かどうかというところです。

「プログラミングはアルゴリズムとデータ構造」と言われているように、どのようなアルゴリズムで組まれているかということと、そのためのデータ構造が最適であるかどうかというところで大きくプログラムが変わります。

特にソートでは、以下の点に気を付けます。

• ソートが安定ソートでなくても良い場合を除いては安定ソートを用いる
• 仮にソートが安定でなくても問題ないようなデータ構造を作る

GNU の sort コマンドはマージソートであり、安定ソートと分かっているのですが、安定ソートでなくても構わないデータを準備すれば、どの sort コマンドを用いたか考えなくて済みます。

#! /usr/local/bin/nawk -f
# stat_01.awk
# ファイルの集計を行う
#   Ref.: http://ap.atmarkit.co.jp/bbs/core/fcoding/20293
# usage: nawk -f stat_01.awk foo.txt

{
    if ($1 in time) {
        time[$1] = time[$1] " " $2;
    } else {
        time[$1] = $2;
    }
}

END {
    for (i in time) {
        print i, time[i];
    }
}

かなりシンプルに書いていますが、時間をインデックスとした配列を組むことで、ダブらないため sort が安定かどうかを考えなくて済みそうです。 09:00 以降かどうかの判定を行っていませんが、その分、コアの部分はシンプルになっています。

ここでは以下のようなテキストを用意しました。

$ cat test.txt
09:00 1
10:00 2
11:00 3
12:00 4
13:00 5
14:00 6
15:00 7
16:00 8
17:00 9
18:00 10
09:00 11
10:00 12
11:00 13
12:00 14
13:00 15
14:00 16
15:00 17
16:00 18
17:00 19
18:00 20
09:00 21
10:00 22
11:00 23
12:00 24
13:00 25

実行して、sort コマンドに渡せば良いわけです。

$ nawk -f stat_01.awk test.txt | sort
09:00 1 11 21
10:00 2 12 22
11:00 3 13 23
12:00 4 14 24
13:00 5 15 25
14:00 6 16
15:00 7 17
16:00 8 18
17:00 9 19
18:00 10 20

他にもいろいろな方法がありそうです。 コメントに Perl を使うと良いという話もありますが、Perl も安定ソートのマージソート、gawk の asort も安定ソートであるマージソートですが、安定ソートでない Quick Sort を用いる言語もないとは言いきれませんので、適切に前処理をしておいた方が安全でしょう。