比较两个列表中的项，最快的方法是什么？

Question

我有两个大约拥有1万个文件的文件夹。我想编写一个脚本或程序，可以告诉我这些文件夹是否同步，并告诉我哪些文件在它们之间缺失，以使它们同步。

因此，在生成文件列表后，最快的算法是什么，可以用于对唯一文件进行排序？目前我在考虑的是比较每个列表上的第一个文件，然后如果它们不同，则删除其中一个，直到它们相同，然后从列表中删除两个文件（因为它们不唯一）。

这种方法是否有比这更快的算法呢？

- edude05

---

如果你想要脚本化它，那么使用一个脚本语言，如perl/php/ruby等。它们中的大多数都有内置函数来进行比较，或者拥有工具（函数）只需要进行少量调整就能完成。在PHP中，这将是4-5行简单的代码。 - Itay Moav -Malimovka

如果您正在处理已排序的大部分同质数据，我认为您可能拥有其中一种更快的方法。 - zellio

只是一个提示，不要建立一个大列表然后进行比较，相反你应该在生成文件的时候迭代文件列表（如果可以保证两个文件夹的内容以相同的顺序返回）。 - Matt Joiner

你已经描述了一个足够快的算法。获取文件名列表并复制任何缺失的文件将需要更长时间！无论是排序比较还是哈希输入和删除，很可能不会有显着的差异。 - Rex Kerr

Answer 1

diff -s [path1] [path2]

- Brian DesArmo

---

谢谢，但我特别要求一个算法，不幸的是我不能将其写入我的代码并使用。 - edude05

Answer 2

如果你使用C语言，可以使用 qsort() 来按升序对文件列表进行排序，然后使用一种“合并”方法：

在每个列表的开头设置两个指针。执行以下操作：

- 如果名称相同，则该名称存在于两个列表中 - 推进两个指针 - 如果 list1 中的名称 > list2 中的名称，则只有 list2 具有它 - 推进 list2 的指针 - 否则，list1 中的名称仅在 list1 中 - 推进 list1 的指针 - 重复

当你到达其中一个列表的末尾时，另一个列表中剩下的所有元素显然都缺失了。

或者，你可以将两个列表组合在一起，同时跟踪每个元素来自哪个列表。然后对组合列表进行排序。扫描排序后的列表。如果看到两个相同值的实例，则它在两个列表中都存在。否则，你将知道它来自哪个列表。

- user3458

Answer 3

此外，您还可以采用另一种方法：

如果空间不是问题，我会将一个文件夹中的文件存储在哈希表中。这需要O（N）的时间和一些空间。然后，我将检查第二个文件夹中的每个文件，看看第一个哈希表中是否存在此键。这又是O（1）的时间操作。问题在O（N）的时间内解决了。但是这对空间需求很大。

反过来做同样的事情，这取决于您想要速度还是空间。

- Kapil D

Answer 4

生成md5或sha1校验和并进行比较。就像这样

cd dir1; md5sum * | sort > /tmp/hash1
cd dir2; md5sum * | sort > /tmp/hash2
diff /tmp/hash1 /tmp/hash2  # could also use comm

如果您只关心文件名称而不关心文件的内容，那么 diff dir1 dir2 就可以了。

- lhf

---

如果文件相同，则哈希值应该相同。 - zellio

@Mimisbrunnr：相关引用：“然后告诉我各自缺少哪些文件，以使它们同步”。哈希在这里没有帮助，除非你是指分两步来完成，统计上假设大多数情况下两个目录将会同步。 - Itay Moav -Malimovka

Answer 5

如果您只需要同步这些信息，可以在单次操作中进行比较和复制：

• 从两个目录获取目录列表
• 按字典顺序排序两个列表
• 同时遍历两个列表：
  • 如果其中一个列表为空，则停止循环
  • 如果两个元素相同：将两个索引一起向前移动
  • 否则，取出字典顺序较小的元素，将其复制并仅移动此索引
• 复制任何剩余的非空列表元素（如果存在）

如果您想要分两次进行，或需要知道复制到哪里的信息，请用“放置名称和方向到结果列表中”替换“复制”。

- Svante