破棄されたブログ

このブログは破棄されました。

名前付きパイプを用いたシェルスクリプトでの幅優先探索

幅優先探索シェルスクリプトで実装するにあたり、キューを用意する必要があるわけですが、御存知の通り、while はサブシェルになるので、変数の受け渡しが糞めんどくさいですし、一時ファイルをディスク上に作成するのもなんか微妙な感じがします。 そこで、名前付きパイプ(FIFO)をキューとして利用することで、幅優先探索を実装してみます。

#/bin/sh

# キューの作成
QUEUE=`mktemp -u`.fifo
mkfifo $QUEUE

# 探索するディレクトリをキューに入れる
echo "/path/to/dir" > $QUEUE &

while read queue
do
    # デキューされたノードを表示
    echo $queue

    # キューの子ノードをループ
    for node in `ls $queue`
    do
            full_path="${queue}/${node}"

            # 子ノードに子ノードがいれば子ノードをエンキュー
            if [ -d "${full_path}" ]; then
                    echo $full_path > $QUEUE
            else
            # 子ノードに子ノードがいなければ表示
                    echo $full_path
            fi
    done
done < $QUEUE


# キューの削除
rm $QUEUE

これで、find /path/to/dir | sort とこのスクリプトの処理結果を sort したものは同様の結果を得られます。

広告を非表示にする