4

我想在 C++ 文件系统上查找重复文件。有没有算法可以尽可能快地做到这一点？我是否需要创建一个多线程应用程序，或者我可以只使用一个线程来完成它？

4

3 回答 3

11

我同意 Kerrek SB 的观点，即有比 C++ 更好的工具，但是，假设您确实需要在 C++ 中执行此操作，这里有一些建议和在您的实现中需要考虑的事项：

  1. 使用 boost::filesystem 进行可移植文件系统遍历

  2. 散列每个文件的建议是非常合理的，但首先制作一个文件大小是关键的多图可能更有效。然后仅在存在重复大小的文件时应用哈希。

  3. 决定如何处理空文件和符号链接/快捷方式

  4. 决定如何处理特殊文件，例如在 unix 上，您有目录 fifos、套接字等

  5. 考虑到在您的算法运行时文件或目录结构可能会更改、消失或移动的事实

  6. 考虑到某些文件或目录可能无法访问或损坏的事实（例如递归目录链接）

  7. 使线程数可配置，因为有意义的并行化量取决于底层磁盘硬件和配置。如果您使用的是简单的硬盘驱动器与昂贵的 san，情况会有所不同。但是，不要做出假设；测试一下。例如，Linux 非常擅长缓存文件，因此您的许多读取将来自内存，因此不会阻塞 i/o。

于 2012-08-01T13:52:30.267 回答
9

1) 不要使用 C++。您需要的所有工具都已经存在。

2) 散列每个文件（例如使用md5sum）并建立文件名、文件大小和散列值的索引。*

3) 按散列值排序并寻找重复的散列值和大小对（例如用sort）。

diff4）对候选副本做一个普通的。

您可以通过一些工作将步骤 2) 并行化，但您会受到存储的 I/O 速度的限制。您可以并行化第 3 步），方法是将您的大型索引文件拆分为多个位，分别对它们进行排序，然后将它们合并（sort -m）。

*) 正如@frankc 所说，实际上不要散列每个文件，而只散列那些大小不唯一的文件。从基于大小的索引开始。你必须散列很多小文件，但只有很少的大文件。

于 2012-08-01T13:36:06.473 回答
5

我会这样做：

  • 扫描您感兴趣的目录，查看每个文件的大小；将文件大小/路径对存储在 amultimap中，以文件大小为索引；
  • 然后，扫描multimap每个键只有一个元素的桶，即大小唯一的文件；那些肯定不能重复。
  • 对剩余文件的内容进行哈希处理，并执行与以前相同的操作（multimap将哈希作为键，将路径作为值）。
  • 然后仅对具有相同散列的文件执行真实（每个字节）比较。

这个过程应该比盲目地散列所有文件要快得多，因为大多数文件都有不同的大小，并且可以通过查看来区分；并且检查文件大小比散列文件便宜得多，因为它只是文件系统属性查找而不是读取文件的全部内容。

需要最后一步，因为不同的文件可能具有相同的哈希值；但是对于良好的散列函数，大部分工作已经完成，因为不相关文件的散列冲突应该非常罕见。

请注意，您的散列函数不需要加密安全，也不需要特别快（我想这个过程的时间将由 IO 控制）。

此外，由于您实际上不需要排序容器，因此multimap您可以使用 an而unordered_multimap不是reserve最大数量的元素，避免重新分配。

于 2012-08-01T13:37:54.373 回答