最近点検索

404 Blog Not Found:algorithm - 最近点検索と404 Blog Not Found:algorithm - correction - 最近点検索に小飼さんがいろいろな解法を示されていますが、ここでは xgawk の時間関数拡張を使って個々の時間を出しながら処理を行ってみます。 元々の問題は 二次元の値(x, y)をもつ集合P から任意の点p の近似点を検索するアルゴリズムを考えています 高速、低負荷で検索するにはどうしたらいいでしょうか？ 条件は次の通りです .. - 人力検索はてな ですが、ここでは小飼さんのもののように近い順にソートしてみます。

#! /usr/bin/gawk -f
# distance.awk

@load time

BEGIN {
    num = ARGV[1] ? ARGV[1] : 1000;
    pos_x = 500;
    pos_y = 500;

    time_1 = gettimeofday();

    srand();            # 乱数の初期化

    for (i = 1; i <= num; i++) {
        position[i] = int(rand() * 1000) " " int(rand() * 1000);
    }

    time_2 = gettimeofday();

    for (i = 1; i < num; i++) {
        split(position[i], a_pos);
        distance = sqrt((a_pos[1] - pos_x) ^ 2 + (a_pos[2] - pos_y) ^ 2);
        arr_distance[i] = sprintf("%10.5f %s", distance, position[i]);
    }

    time_3 = gettimeofday();

    asort(arr_distance);

    time_4 = gettimeofday();

    for (i = 1; i <= num; i++) {
        print substr(arr_distance[i], 12);
    }

    time_5 = gettimeofday();

    print "配列の生成にかかった時間:   " time_2 - time_1 " (sec)";
    print "距離計算にかかった時間:     " time_3 - time_2 " (sec)";
    print "距離のソートにかかった時間: " time_4 - time_3 " (sec)";
    print "表示にかかった時間:         " time_5 - time_4 " (sec)";
}

実際に実行してみると分かりますが、確かに距離計算にかかるコストは大きいのですが、1000 個レベルであると 0.01 sec 程度で計算できます。

$ xgawk -f distance.awk
<snip>
配列の生成にかかった時間:   0.0106919 (sec)
距離計算にかかった時間:     0.0176971 (sec)
距離のソートにかかった時間: 0.000696898 (sec)
表示にかかった時間:         0.021801 (sec)

では 10000 個の場合を計算してみます。

$ xgawk -f distance.awk 10000
<snip>
配列の生成にかかった時間:   0.0374529 (sec)
距離計算にかかった時間:     0.0573392 (sec)
距離のソートにかかった時間: 0.0105679 (sec)
表示にかかった時間:         1.63537 (sec)

awk は元々遅いと言われていますが、かなり高速に処理できていることが分かります。

今回、座標を配列として保有し、これを split() 関数で毎回展開をしていますが、ここでもそれなりのコストがかかってしまいます。 また、gawk の asort() 関数は相当おかしくないに書いたように asort() を使うために故意に sprintf() で asort() が誤解しないようにデータを揃えています。 データを工夫することでさらに高速化することはできそうです。

今回は xgawk の gettimeofday() 関数を用いているため、xgawk 専用ですが、時間的な計算を行わず、asort() をgawk の asort() 関数は相当おかしくないで示したようなソート関数に置き換えれば一般的な awk でも動作します。

tag_xgawk.png