ディレクトリツリーから最下層（リーフ）のディレクトリのみ列挙する

id:eel3:20091026:1256558649 でやり残した宿題みたいなエントリ。

元々はWindows上でフォルダツリーを辿り、最下層のフォルダ（つまり中にファイルはあってもフォルダは無いもの）で且つ特定の名前だったらその中にフォルダを作る、ということをやりたかった。

Windowsでは長ったらしいけどWSHのJScriptでフォルダを再帰的に辿るコードの雛形を作ったので、それを使えば多分何とかなるはずだ。

ではシェルスクリプトではどうだろうか？　具体的には、最下層のディレクトリのみを列挙するにはどうすれば良いのだろうか？

その1：find(1)の2段重ね

findを使ってディレクトリツリーの最下層（リーフ）のディレクトリをピックアップすることは可能なのだろうか？　空ディレクトリなら簡単にできそうだ。

find ./ -type d -empty -print

しかし最下層のディレクトリといっても、ディレクトリは無くてもファイルを保持している場合もある。findのオプションを眺めてみたものの、私には良い方法は思い浮かばなかった。

なのでfindを使いつつも地道に最下層であることを調べることにした。

#!/bin/sh

if [ $# -ne 1 ]; then
    echo "usage: `basename $0` directory" > /dev/stderr
    exit 1
fi
if [ ! -d "$1" ]; then
    echo "`basename $0`: $1: No such directory" > /dev/stderr
    exit 1
fi

find "$1" -type d | while read DIR; do
    if [ "`find "$DIR" -maxdepth 1 -type d | wc -l`" = "1" ]; then
        echo "$DIR"
    fi
done

exit 0

findで一旦全てのディレクトリを列挙し、その上で各ディレクトリに対してfindを使って子ディレクトリを列挙してその数をチェックしている。比較する値が `0' でなく `1' なのは、上記の方法で子ディレクトリを列挙する時に自分自身（つまり `.'）も列挙されてしまうからだ。

その2：再帰してみる

なるほど、findを使う方法はシェルスクリプトらしいといえば確かにそうだ。しかし何というか、ディレクトリツリーを辿るとなるとやはり再帰の文字がチラつく。

そこでシェル関数を作って再帰させてみた。

#!/bin/sh

if [ $# -ne 1 ]; then
    echo "usage: `basename $0` directory" > /dev/stderr
    exit 1
fi
if [ ! -d "$1" ]; then
    echo "`basename $0`: $1: No such directory" > /dev/stderr
    exit 1
fi

enum_leaf_dir() {
    find "$1" -maxdepth 1 -type d | sed '1d' | {
        DIR=
        NODIR=true
        while read DIR; do
            enum_leaf_dir "$DIR"
            NODIR=false
        done
        $NODIR && echo "$1"
    }
}

enum_leaf_dir "$1"
exit 0

Bourne Shellではパイプを使うとサブシェルになり、whileの中で操作した変数の値を後で使用できなくて嵌ることが多々ある。ここでは安直にグルーピングで回避したけど、この回避方法に移植性はあっただろうか？

その3：もっと大胆(？)に再帰してみる

関数で再帰するのも良いけど、折角だからシェルスクリプト自身を再帰させてみた。

#!/bin/sh

if [ $# -ne 1 ]; then
    echo "usage: `basename $0` directory" > /dev/stderr
    exit 1
fi
if [ ! -d "$1" ]; then
    echo "`basename $0`: $1: No such directory" > /dev/stderr
    exit 1
fi

find "$1" -maxdepth 1 -type d | sed '1d' | {
    DIR=
    NODIR=true
    while read DIR; do
        $0 "$DIR"
        NODIR=false
    done
    $NODIR && echo "$1"
}
exit 0

処理の始めと終わりを特別扱いしたい場合には向いてなさそうが気がする。でもその必要がなければ割とすんなり書けるようだ。

どれが速い？

実験してみた。諸事情によりディレクトリの中身は伏せておく。

eld1.shかfindを2段重ねした版、eld2.shがシェル関数で再帰した版、eld3.shがスクリプト自体を再帰的に実行した版だ。

$ time ./eld1.sh testdir > /dev/null

real    0m10.000s
user    0m6.050s
sys     0m3.399s
$ time ./eld2.sh testdir > /dev/null

real    0m8.219s
user    0m5.939s
sys     0m3.647s
$ time ./eld3.sh testdir > /dev/null

real    0m13.906s
user    0m9.031s
sys     0m4.692s
$ _

プロセス生成数が多いだろうeld3.shが最も遅いのは予想通りだった一方、eld2.shが最も高速だったのは意外だった。