09/03/03 09:57:03
お前の書くコードがdiffよりオーバーヘッドが少ないわけがない。
431:名無しさん＠お腹いっぱい。
09/03/03 10:09:27
>>429
普通のdiffコマンドは高速でないアルゴリズム( O(ND) )を使ってるから、
gitとかpythonのライブラリに使われてるやつのが速い
ってわけで、速度を追い求めるなら差分取得のアルゴリズムについて調べてがんばれ
432:名無しさん＠お腹いっぱい。
09/03/03 10:12:30
いや高速でないってこたないんですよ、それより速いのがあるだけで
433:429
09/03/03 10:29:38
あー書き方が悪かったかな。
もし diff ということで LCS とかそこらへんに脊髄反射されてたらごめんなさい。
自分が知りたいのは dirA と dirB の内容が違うか同じかだけなんです。
この場合むしろディレクトリの階層に効率よくアクセスできることが重要なんじゃないかと
思ったんですが、違います? fts とかですかね?
それにファイルを処理するようなソフトならありがちな処理のような気がするので、
どこかに適切なコードのサンプルがあればと思って...
434:名無しさん＠お腹いっぱい。
09/03/03 10:37:16
>>433
> 自分が知りたいのは dirA と dirB の内容が違うか同じかだけなんです。
内容の比較は必要か
タイムスタンプの比較だけでいいか
同じファイル名が存在するだけでいいのか
rsync --dry-runの出力結果を使うとか。
435:429
09/03/03 10:50:52
>>434
「同じ」とはディレクトリ構造が同じで、その中に存在するファイルの名前&内容が同じ
という積もりです。
タイムスタンプは比較しません。
>rsync --dry-runの出力結果を使うとか。
はい、確かにそれも速そうですが、自分のプログラムだと比較的浅いディレクトリに
対してそれを何度も呼ぶことになりそうなので、C の何かの API で書いた方がいいのか
なあと。
ある意味 rsync みたいなプログラムなんですが、syncするときにいろいろカスタムな
ロジックを入れたいので、コードを書いているといいますか....
436:名無しさん＠お腹いっぱい。
09/03/03 11:32:23
内容比較がcmp -sレベルでいいなら、
readdir/lstatで自分で書けばいいんじゃない?
質問せずに書けば、今頃書き終わっている頃かと。
437:名無しさん＠お腹いっぱい。
09/03/03 13:31:30
ファイルとディレクトリの equality は適当に定義出来
るとして、↓みたいになるかな。
for (File src = each of srcDir) {
File dst = dstDir.Find(src);
if (dst == null) {
// src にしかない
} else if (src != dst) {
// 違う
}
}
for (File dst = rest of dstDir) {
// dst にしかない
}
each of …は都度 readdir して、Find は保持してるプー
ルから探して、無ければ見つかるまで readdir、してプー
ルに入れていく感じ。見つかったらプールから削除して
おいて rest of …でそれを得る。
438:名無しさん＠お腹いっぱい。
09/03/03 14:07:34
両方コレクションにいれて、ソートして、
先頭二つ、計四つを比較しながら取り出せばいい。
四つになるのはどちらが欠けているかわからないから。
どれも違う場合、四つの中で小さいの二つを捨てればいい。
AB
AB
AB
BC
BC
AB
-
AB
CD
AC
BD
439:名無しさん＠お腹いっぱい。
09/03/03 14:16:00
>>438
ファイル／ディレクトリの equality と同様に順序付け
も定義出来るなら（ソートするからには出来るはずだ）、
先読みする必要はない。マージソートの要領だ。
440:名無しさん＠お腹いっぱい。
09/03/12 19:41:22
dirp=opendir(".");
printf("1 :%d;\n",telldir(dirp));
printf("2 :%d;\n",telldir(dirp));
printf("3 :%d;\n",telldir(dirp));
closedir(dirp);
とすると返す値は1,2,3とどんどんインクリメントしていくだけだし
seekdirは無反応rewinddirは巻き戻すばかりかtelldirをひとつ進めるだけ
readdirとかはちゃんとできているんだけれど
何か呪文とかいるのかダメダメな関数なのか情報please
441:名無しさん＠お腹いっぱい。
09/03/12 19:51:28
>>440 OSはFreeBSDです。
442:名無しさん＠お腹いっぱい。
09/03/12 20:15:55
たぶん実装がおかしいんだろう。MacOS Xも同様らしい。
URLﾘﾝｸ(idm.s9.xrea.com)
dirent読むのにtelldirやseekdir使うようなやつはいないから放置されてると想像。
443:名無しさん＠お腹いっぱい。
09/03/12 20:24:17
追加。このへん関係あるかも。
URLﾘﾝｸ(www.freebsd.org)
444:名無しさん＠お腹いっぱい。
09/03/12 20:32:49
>>440です。rewinddirの記述は間違っていました。
rewinddirとreaddirだけが使えます。
で調べたらscandirというのがありました。
mallocしてくれて配列に入れて関数指定すればsortもしてくれるようなので
コールバックもsort関数に入れます。
>>435もscandir+lstatでいいのでは?
しかしひどすぎるなtelldir+seekdir
ファイルの多いディレクトリーでちょろちょろよむもん作りたかったんだけど
一気読みが基本ですか?
445:名無しさん＠お腹いっぱい。
09/03/12 20:38:50
とりあえずコールバック抜きのアルファソートやってみた。
c = scandir(dirname, &namelist, NULL, alphasort);
if(c == -1) {
puts("not opendir");
return(1);
}
printf ("%d\n", c);
for (i = 0; i < c; ++i) {
printf ("%s\n", namelist[i]->d_name);
free(namelist[i]);
}
free(namelist);
opendirの苦労は一体....orz
446:名無しさん＠お腹いっぱい。
09/03/12 20:40:17
>>435
opendir -> ディレクトリをファイルとして開く
readdir -> ディレクトリのエントリを一つ読み込む(ポインタ一個進む)
seekdir -> ディレクトリのエントリを x 番目にセットする
telldir -> 今いるエントリ位置を報告する
を組み合わせて, 双方のエントリを比較して
1. 対象物の inode が同じなら処理スキップ
2. 対象物が ディレクトリなら, 自分自身を再帰的に呼び出す
3. 対象物がファイルなら中身を比較
すればええんちゃう?
447:名無しさん＠お腹いっぱい。
09/03/12 20:46:16
既に読んだエントリに戻って読み直すシチュエーションがわからん。
仮にtelldir/seekdirの動作がまともでも、
いちいち物理的にディレクトリ読みに行くような実装だったりしたら、
遅いし最中に誰かがいじらんとも限らんし、いいことなしでは？
キャッシュしてるんだとすれば一気読みと何も変わらんし。
というわけで、telldir/seekdirは価値なしなんじゃないかと。
448:名無しさん＠お腹いっぱい。
09/03/12 21:00:32
>>447
再帰して必要物がなくって、バックトラックするときに
変わってしまった状態を元に戻すために必要
recur_dir(...
here = telldir(...
if (このエントリが dir && 比較対象と違う)
if (recur_dir(...) == succeed)
return なんとか
ここに戻ってきた場合何がどうなってるか保証できない
seekdir(here)
続きの処理
449:名無しさん＠お腹いっぱい。
09/03/12 21:56:26
何がどうなってるか保証できない状態なら
telldirしたところにseekdirしても保証できないだろう
450:名無しさん＠お腹いっぱい。
09/03/15 11:44:20
ストリームとしてファイルリストをチェックしていくならseekとかは必須だと思うけれど
telldirもseekdirも機能しないんだから必要でも存在しない事実をどうする。
一旦readdirだかscandirでざっくりと読み込んで
それに対して操作するしか方法が無いのが現実。
バックアップとかで完全一致を目指す場合
「ほぼあっている」前提ならば結局ファイル自体の完全マッチをするしかないと思うが
事前にMD5とかSHA1とかとったリストをディレクトリーに入れとけばそれで済む気はする。