▼一番新しいファイルを探す▼

ディレクトリ再帰しながら、一番新しいファイルを探したい。

「最近３日以内に更新されたファイル」なら find(1) で 簡単に探せますが、 「一番新しいファイル」をどうやって探し当てるか、 というコマンドラインを作ろうとした際の思考過程。

	# ファイル数が1024個以下程度の時
	% ls -t `find . -type f` | head -1

	# ファイル数が10万個程度までの時
	% find . -type f | xargs -n 100 sh -c 'ls -t $@ | head -1' | xargs ls -t | head -1

	# ファイル数がとても多いとき
	% find $1 -type f -print0 |
	  xargs -0 -n100 stat -f "%m %N" |
	  awk 't<$1{t=$1;n=$0} END{print n}' |
	  sed -e 's/^[^ ]* //'
	

$Id: newest-file.html,v 1.7 2016-10-27 09:36:11+09 kabe Exp $

ls -t だろう

	% ls -t
	newest-file.html.vim          xon.html                      C1400.html
	newest-file.html              sjis.ASCII.article.html       hearts.html.ko
	RCS                           joy.news                      anon.html
	...

	% ls -t | head -1
	newest-file.html.vim

	% find . -type f
	./tips.html
	./fonts.html
	./garbled.html
	...

	% ls -t `find . -type f`
	./newest-file.html.vim                       ./2ch-portscan-ref.html
	./newest-file.html                           ./RCS/xon.html,v
	...

	% ls -t `find . -type f` | head -1
	./newest-file.html.vim

計算オーダーとかの話

(argc制限) ls -t `find . -type f` は、 lsの引数として直接、全部のファイルを詰め込んでいるので、 ファイル数が大きすぎると使えない。 だいたい1024個あたりで限界がくる。

	% ls -t `find /opt/f-secure -type f` | head -1
	find: /opt/f-secure/fsigk/auth/global/cert: Permission denied
	/bin/ls: Argument list too long.

(処理コスト) ファイル数をＮとすると、

• find は Ｏ(Ｎ)
• ls -t は ソートが支配的として、Ｏ(ＮlogＮ)

最新(mtime値が一番大きいもの)だけ拾い出したいなら Ｏ(Ｎ)でできるはずだが、そういうプログラムを書く必要がある。 Ｎの値が大きい (100万ファイルとか)だと考える必要がある。

(空白の処理) これだとファイル名に空白が入っているとうまく動かない、 かもしれない。MacOS X とか。 シェルのバッククオート引数渡しにせず、 素直にxargs使ったほうがいいかも。

ファイル数が大きいとき

	% ls -t `find /opt/f-secure -type f` | head -1
	find: /opt/f-secure/fsigk/auth/global/cert: Permission denied
	/bin/ls: Argument list too long.

えーと、100個くらいずつにちぎって、後でマージソートしよう。

	% find /opt/f-secure -type f | _

xargs -n 100 を使うか。

	% find /opt/f-secure -type f | xargs -n 100 _

	% find /opt/f-secure -type f | xargs -n 100 ls -t _

…こうか

	% find /opt/f-secure -type f | xargs -n 100 sh -c 'ls -t "$@" | head -1' _

	% find /opt/f-secure -type f | xargs -n 100 sh -c 'ls -t "$@" | head -1' | _

こんなんか？もう一回 xargsを使う。

	% find /opt/f-secure -type f | xargs -n 100 sh -c 'ls -t "$@" | head -1' | xargs ls -t
	find: /opt/f-secure/fsigk/auth/global/cert: Permission denied
	/opt/f-secure/fsigk/log/admin/catalina.out
	/opt/f-secure/fsigk/log/http/access.log
	/opt/f-secure/fsigk/log/pop/access.log
	...

	% find /opt/f-secure -type f | xargs -n 100 sh -c 'ls -t "$@" | head -1' | xargs ls -t | head -1
	find: /opt/f-secure/fsigk/auth/global/cert: Permission denied
	/opt/f-secure/fsigk/log/admin/catalina.out

計算オーダーとかの話

(空白の処理) 問題あり。 find -print0 と xargs -0 のコンビが本来は必要。 ２段目以降のxargsでは -0 が使えない。 (GNU xargs ならxargs --delimiter で逃げられるが)
ふっるいshだと "$@" がうまく展開できないやつも あるかもしれない。 この辺の移植性については autoconf のマニュアルが 地味に参考になる。

(処理コスト) ファイル数をＮとすると、

• find は Ｏ(Ｎ)。ただし、ディスク負荷は意外に大きい。 ファイルシステムの構造とか考え始めるとＯ(Ｎ)では足らないかも？
• xargs -n 100 sh -c 'ls -t $@ | head -1' は、Ｏ(ＮlogＮ) を ∝Ｎ回 繰り返し、だから Ｏ(Ｎ²logＮ) かもしれないけど、 100個のカタマリづつでソートしてるだけだから、 全体としてはＯ(ＮlogＮ)だろう。 ただ、いちいち /bin/sh を起動してるから、あんまり速くない。
• 最後のls -t は Ｏ(ＮlogＮ)

Ｎの値が100万ファイルとかなら、1000個くらいずつに区切れば一応処理できるかもしれない。 もっと多そうなら、ls -t を２段ロケットにして…

いやいやいや。

そもそも find で時間・負荷がかかりすぎて破綻すると思う。 ディレクトリの atime 更新だけでディスクI/Oがお腹いっぱいになってしまう。 こういう全数検査ではなくて、「ディレクトリのmtimeを見て、更新があったら探しに行く」 みたいなことをしないと。

１回だけならこれでもいいけど、定期起動するバッチファイルに埋めるなら ちゃんと考えて設計・実装しないと駄目ですね。 ちゃんと作れば Ｏ(Ｎ) になりそう。

ファイル数がとても大きいとき

ls -t では真面目に全部ソートしてしまうので、 100万ファイルとかだと無駄な処理が多すぎる。Ｏ（Ｎ）で作りたい。

find $1 -type f -print0 |	# ファイル名を全部吐かせる
xargs -0 -n100 stat -f "%m %N" | # mtimeとファイル名を吐かせる。GNU(Linux) stat(1)なら stat -c "%Y %n"
awk 't<$1{t=$1;n=$0} END{print n}' | # Ｏ（Ｎ）で、mtime が一番大きい行を抽出
sed -e 's/^[^ ]* //' # ファイル名だけ抽出。ファイル名にスペースがあってもok

xargsはスペースでも引数が区切られるので、スペース入りファイル名を 正しく扱うには find -print0 と xargs -0 のコンビが必要。

これでも stat(2) がファイルあたり２回実行されるので、無駄あり。 本気で作るならシェルではなく Ｃやperlで再帰下降＋最大mtime抽出、を書くほうがいい。
プログラミング演習の課題に最適ですな…

トップへ戻る