ファイル検索のアルゴリズムについて

質問

ファイル検索のアルゴリズムで一番高速なアルゴリズムについて教えて下さい。
やりたいことは、

あるフォルダ以下のファイル（フォルダであれば更にその下まで）検索し、
現在の時刻から一番近い更新日時の早い順にファイルを10個検索するというものです。

ファイル本体をすべて検索するプログラムについてはできていまして、
現在の時刻から一番近い更新日時の早い順にファイルを10個検索する方法に関して
高速なアルゴリズムがありましたら教えて下さい。

プログラミング言語がPHPなのでPHPで実現可能なアルゴリズムですと嬉しいです。

回答No.5

JaneDue

PHPのロジックとしては
該当ファイル取得 >> 各ファイルの更新時取得・配列生成 >> ソート >> 必要件数の取り出ししかないでしょう。
とりあえず10件更新日時を取得したら一旦ソートし、それ以降は10番目より新しい場合のみ配列に入れる等、小手先の方法はあるでしょうが煩雑になりそうです。
あるいはファイル名をタイムスタンプにすれば少しはよいかも知れません。

コマンドが利用できるのであれば
$newfiles = shell_exec("find ./data -mtime -31 -name '*.mp3' | xargs ls -l --time-style=long-iso | sort -k 6,7 -r | head -10");
のような方法もあるにはあります。
(./data 以下の1ヶ月以内に更新されたmp3ファイルから新しいものを10行取得 ※環境で若干異なる)
どちらにしてアクセスの度実行するのではなく、既回答のようにリストを生成しておき、ファイル更新時にリストも自動更新する方がよいかと。

ただ、ごちゃごちゃやるより、将来的なことも考えるとやはりSQLにすべきケースです。
理由はAno4さんの通り。他アクセス順/人気順など件数も含めて好きなように応用可能です。

回答No.4

shimix

私も「データベースを使う」に一票。

更新日時でもアーチスト名でも思いのままに検索出来ますからね。またファイル自体は特定のディレクトリに（重複さえしなければ）適当な名前で保存出来ますし、アーティスト名やアルバム名に（ファイル名がタイトルであればタイトルにも）「ファイルシステムで使えない文字」でも利用できます（ディレクトリ名にするわけではないので）。

最初にデータベース化するときにはFTPされたファイルを検索してinsertを繰り返す必要がありますが、追加していくときにはブラウザからの（アーティスト名やアルバム名を入力しての）アップロード処理で作れますよね。提示されたような階層構造だとFTP以外で追加するのは面倒です（前述のファイルシステムで使えない文字のチェックとかもありますから）。

回答No.3

noname#244856

「クイックソート」について述べられていますが、この問題とはあまり関係ない気がします。

C言語レベルで

int arr[] = { 3, 5, 1, 2, 4, 7 };

のような配列をソートするのとは本質が異なります。
今回一番ネックになってくるのが「更新日時の取得」です。

更新日時の取得 filetime関数
http://php.net/manual/ja/function.filemtime.php

ソートアルゴリズム云々以前にこれを6000回も毎回コールするのはさすがに正気とは思えませんね。

また、全ファイルの更新日時が格納された配列があるにしても、PHPレベルだと

sort($arr);

これで終了です。
ソートアルゴリズムの中身はPHP言語に実装されています。

PHP言語がC言語によって書かれていることはご存知ですか？

参考
http://d.hatena.ne.jp/suztomo/20080605/1212687962

【解決策】
データベースを利用する

回答No.2

bm_hiro

6,000件もあるとすると、配列使うのは きっと効率が悪いですね。
そもそも検索時に毎回総当りをする事が効率悪いです。

初回検索時に、リスト作っておいて、
ファイルの追加や削除のタイミングでリスト更新するのが良いかも。
PHP側でファイルの追加や削除を監視できていなければダメですけど。

DBが使える環境なら、その方がいいですし。

毎回総当りをする前提なら、早いかどうかは別として、配列に入れてPHPにソートしてもらうのが楽です。
日時をキーとする場合、キーの重複に気をつけないといけないですけど。

最速なのかと問われると、いろいろ試してみないと分かんない。と言うのが正直な本音です。

回答No.1

bm_hiro

どんだけのファイルを扱おうとしているのか分かりませんし、実際速さがどんなもんか分かりませんが、自分なら こうするかな程度の案です。

ファイル本体をすべて検索する時点で、日時をキーにして配列に入れておいて、後でソートするとか。
すべて検索する時点で、随時 順位づけするとか。

前回検索時の状態を保存しておいて、それ以降に追加変更された差分だけやるとか。

扱うファイル数と稼働状況によりけりという感じですかねー。

お礼

御回答有り難うございます。

補足

一番肝心な情報が抜けていましたすみません。
扱うファイルは音楽ファイルで6000曲ほどが
ルート→アーティスト名→アルバム名→ファイル
という階層構造で分類保存されています。
この量程度のファイル数ですと日時キー配列作成の後のソートアルゴリズムはクイックソートがやはり最速なのでしょうか？