什么是比较两个项目列表的最快方式？

我有两个文件夹，每个文件夹大约有10,000个文件。我想编写一个脚本或程序，告诉我这些文件夹是否同步，然后告诉我哪些文件从每个文件都丢失，以使它们同步。什么是比较两个项目列表的最快方式？

因此，生成一个文件列表后，什么是最快的算法来排序他们的唯一文件？我现在想的是比较每个列表上的第一个文件，然后如果他们不同，删除一个，直到他们是相同的，然后从列表中删除两个（因为他们不是唯一的。）

有没有更快算法比这个？

2010-03-14 edude05

如果你想编写脚本，然后使用脚本语言perl/php/ruby等。他们中的大多数都有内置的函数来做这种比较或者有工具（函数），只需要稍微调整就可以了。在PHP中，它将是4-5行简单的代码。 – 2010-03-14 02:35:28

我认为如果您正在处理已排序的大多数同质数据，您可能会有更快的方法之一。 – zellio 2010-03-14 02:37:57

只是一个注释，不要构建一个大量的列表然后进行比较，而是应该在生成文件时迭代文件列表（如果可以保证两个文件夹的内容以相同的顺序返回） – 2010-03-14 04:41:20

生成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工作正常。

2010-03-14 02:28:31 lhf

他需要这些文件的名字...... – 2010-03-14 02:35:55

如果文件相同，那么哈希应该是相同的 – zellio 2010-03-14 02:37:12

@Mimisbrunnr：相关引用：“然后告诉我哪些文件从每个文件中丢失，以使它们同步”hash在这里没有帮助，除非你的意思是分两步做，统计上假设大多数情况下两个dirs将同步。 – 2010-03-14 02:51:33

如果你用C的时候，使用qsort()以升序排列文件列表进行排序，然后用一种“合并：

有开始在每个列表的开头两个指针执行以下操作：

当你在列表中的一个结束，所有留在其他的元素显然从第一个缺失。

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

2010-03-14 02:47:18 Arkadiy

差异-s [路径1] [路径2]

2010-03-14 04:15:24

我喜欢无代码的答案。 – 2010-03-14 04:55:40

谢谢，但我特别要求一种算法，我不能将它写入我的代码并不幸使用它。 – edude05 2011-02-22 19:39:49

此外，您还可以按照另一种方法是

如果空间没有限制，我会去把一个文件夹的文件哈希.. 这将需要O（N）时间和一些空间..！然后我将采取每个文件的第二个文件夹，并检查密钥是否存在第一个哈希..这再次O（1）时间操作..！问题在O（N）时间解决..但这对空间要求很大..

重复相同的反向或相反取决于如果你想速度或空间..！

2010-03-14 04:40:13

如果您需要这些信息只是对他们进行同步，你可以做一个合格的比较和复印：

获取目录字典顺序从两个目录列出
排序两个列表
环通过这两个列表同时：
- 如果其中一个列表是空的，停止循环
- 若b超视距元素都是相同的：步骤两个指数
- 别人拿字典顺序较低的元素，将它复制过来，步骤仅此指数
复制的非空列表中的任何剩余的元素，如果存在的话

如果您想要两次完成，或需要复制的信息，请用“将名称和方向放入结果列表”替换“复制”。

2010-03-14 12:37:36 Svante

回答