いくつかのファイルの一致を確認するプログラミングの作り方。

質問

いくつかのファイルの一致を確認するプログラミングの作り方。
例えば７個のtxtファイル　a,　b,　c,　d,　e,　f,　g　があるとします。
a,　b,　c,　d,　e,　f,　g　はそれぞれのファイルのファイル名です。
そのうち、 a, b, g　のファイルの内容が全く同じであった場合、
a, b, g　は一致していると判断するには、どんなプログラムを作成すればよいのでしょう？

ちなみにファイルの中身は　数字が配列のように並んでおり、文字数は5000文字程度です。

回答No.3

hanabutako · ベストアンサー

単純な方法)
各ファイルを逐次比較。aとb,c,d,e,f,gを比較し、bとc,d,e,f,gを比較し、cとde,e,f,gを比較し...というのをfまで繰り返す。一致を発見したら随時記録するか表示するかする。
ファイルの平均サイズをnとしたら、比較にかかる計算時間はO(n)なので、m個のファイルを逐次比較するのにかかるコストはO(n*m^2)。
fstatなどでファイルサイズを取得して、ファイルサイズが一致するもののみ比較すると、すべてファイルサイズが違う場合がおそらく最良のケースで、O(m^2)で調査可能。
さらに、前の調査で一致している場合は調査済みとマークするなどして飛ばすようにすると、すべて同じファイルだったときに最良で、計算時間はO(n*m)。

一致するものが少ない時に有効な方法)
まず、各ファイルのチェックサムを計算。チェックサムを二分木に入れて、一致したものがあった場合は対応するファイル名を記録、後で対応表にあるファイルのみ比較する。
ファイルサイズをnとすると、ファイルのチェックサムを計算する計算時間はO(n)なので、m個のファイルのチェックサム計算時間はO(n*m)。
m個のファイルに付いて二分木を使って1つを比較する計算時間はO(log m)なので、m個これをやるとO(m log m)。
次に、対応表にあるファイルの比較の計算時間を考えると、最悪時はすべてが一致しているケースでO(n*m^2)。この場合、比較に律速されるのでO(n*m^2)が計算時間のオーダーとなる。最良はすべてが一致していないケースで、この場合は比較について計算する必要はない。この倍、計算時間のオーダーはmに比べてよほどnが小さくない限り、O(n*m)。

こう考えると、ファイルサイズについて二分木を使った比較をして、残ったものがしきい値以上だったらチェックサムで比較をし、それで一致した場合は実際のファイルで比較するというのが滅多に一致するファイルがない場合に効率的でしょうか。

逆に、ほとんど同じファイルしかない場合は、上で書いた単純な方法で、一致した場合はマークをして飛ばすというのが一番効率がいいと思います。

お礼

皆様へ

お早い解答、ありがとうございます。
C言語の質問をしたのは初めてだったので
質問に不足な点もあったかとは思いますが
伝えることが出来たので良かったです。
これは学校とは全く無関係ですので
宿題を皆様に問いかけたのではないんです。
そう受け取られたにも関わらず
解答してくださって感謝しています。
アドバイス等もありがとうございます。
今後、参考にしていきたいとおもいます。

回答No.2

yuki-alpha

一応確認だけど、これって学校の宿題をやらせようってわけじゃじゃないよね？

(1)各ファイルのハッシュ値を算出。
(2)ハッシュ値が同じものは内容も同じ。
(3)内容が同じものをリストアップ。
(4)結果を表示。

ハッシュ値に関してはGoogleで調査してね。

こんなとこかな。

お礼

お早い解答ありがとうございます。
C言語の質問は初めてだったので
質問に不足する点があったとは思うのですが
伝えることが出来たので良かったです。
これは学校とは全く無関係ですので
宿題を皆様に問いかけたのではないんです。
そう受け取られたにも関わらず
解答してくださって感謝しています。
アドバイス等もありがとうございます。
今後、参考にしていきたいとおもいます。

回答No.1

D400V

言語を書かないとレスが付かないかも。
あと、質問する場所もプログラミングにしないと専門職の方が見てくれないかもです。

お礼

お早い解答ありがとうございます。
C言語の質問は初めてだったので
質問に不足する点があったとは思うのですが
伝えることが出来たので良かったです。
これは学校とは全く無関係ですので
宿題を皆様に問いかけたのではないんです。
そう受け取られたにも関わらず
解答してくださって感謝しています。
アドバイス等もありがとうございます。
今後、参考にしていきたいとおもいます。