在 bash 中查找重复文件的时间复杂度
Time complexity of finding duplicate files in bash
我今天不得不编写一个 Bash 脚本来删除重复的文件，使用它们的 md5 哈希值。我将这些哈希值作为文件存储在一个临时目录中：
for i in * ; do
hash=$(md5sum /tmp/msg | cut -d " " -f1) ;
if [ -f /tmp/hashes/$hash ] ;
then
echo "Deleted $i" ;
mv $i /tmp/deleted ;
else
touch /tmp/hashes/$hash ;
fi ;
done
它工作得很好，但让我想知道：这是一种节省时间的方法吗？我最初想到将 MD5 哈希值存储在一个文件中，但后来我想到 "no, because checking whether a given MD5 is in this file requires to re-read it entirely every time"。现在，我想知道：使用 "create files in a directory" 方法时是否相同？当同一目录中有很多文件时，Bash [-f] 是否检查线性或准常数复杂度？
如果它取决于文件系统，tmpfs 的复杂性是多少？
在读取包含散列的文件内容和在作为散列的文件名目录中查找散列之间的选择基本上归结为 "is the kernel quicker at reading a directory or your program at reading a file"。两者都将涉及对每个哈希的线性搜索，因此您最终会得到几乎相同的行为。您可能会争辩说内核应该快一点，但幅度不会太大。请注意，大多数情况下，线性搜索将是详尽无遗的，因为散列不存在（除非您有很多重复文件）。因此，如果您正在处理几千个文件，则搜索将总共处理几百万个条目 — 这是二次行为。
如果您有数百或数千个文件，您最好使用两级层次结构 - 例如，一个目录包含两个字符的子目录 00 .. FF，然后存储其余部分子目录中的名称（或全名）。例如，在 terminfo 目录中使用了此技术的一个小变体。优点是内核只需要读取相对较小的目录来查找文件是否存在。
我还没有 "hashed" 这个，但我会尝试将你的 md5sums 存储在 bash 散列中。
见How to define hash tables in Bash?
将 md5sum 存储为键，如果需要，还可以将文件名存储为值。对于每个文件，只需查看密钥是否已存在于散列 table 中。如果是这样，您不关心该值，但可以使用它来打印出原始重复文件的名称。然后删除当前文件（使用重复键）。不是 bash 专家，这就是我开始寻找的地方。
我喜欢使用正确的工具来完成工作。在这种情况下，您只想查看重复的文件。我已经针对我手头的数千个文件对此进行了测试，重新阅读该文件似乎没有任何问题。另外我注意到我有数百个重复文件。当我将散列存储在单独的文件中然后处理如此大量的文件时，我的系统在一个目录中存储了大约 10,000 个散列文件后慢慢地爬行。将所有哈希值放在一个文件中大大加快了速度。
# This uses md5deep. An alternate is presented later.
md5deep -r some_folder > hashes.txt
# If you do not have md5deep
find . -type f -exec md5sum \{\} \;
这会为您提供所有内容的哈希值。
cut -b -32 hashes.txt | sort | uniq -d > dupe_hashes.txt
这将使用 cut 获取每个文件的哈希值，对哈希值进行排序，然后找到任何重复的哈希值。这些被写入 dupe_hashes.txt 而没有附加文件名。现在我们需要将哈希映射回文件。
(for hash in $(cat dupe_hashes.txt); do
grep "^$hash" hashes.txt | tail -n +2 | cut -b 35-
done) > dupe_files.txt
这对我来说似乎并不运行慢。 Linux 内核在将此类文件保存在内存中而不是经常从磁盘读取它们方面做得非常好。如果你更喜欢强制它在内存中，你可以只使用 /dev/shm/hashes.txt 而不是 hashes.txt。我发现在我的测试中没有必要。
这会为您提供重复的每个文件。到目前为止，一切都很好。您可能想要查看此列表。如果您还想列出原始版本，请从命令中删除 tail -n +2 | 位。
当您觉得可以删除每个列出的文件时，您可以将内容通过管道传输到 xargs。这将以 50 个为一组删除文件。
xargs -L 50 rm < dupe_files.txt
我将尝试定性地回答文件存在性测试在 tmpfs 上的速度有多快，然后我可以建议您如何使整个程序 运行 更快。
首先，tmpfs 目录查找（在内核中）依赖于目录条目缓存散列 table 查找，这对目录中的文件数量不那么敏感。它们受到影响，但呈次线性。它与这样一个事实有关，即正确完成的散列 table 查找需要一些恒定的时间 O(1)，而不管散列 table.
中的项目数量如何。
为了解释，我们可以看看 test -f 或 [ -f X ] 所做的工作，来自 coreutils (gitweb):
case 'e':
unary_advance ();
return stat (argv[pos - 1], &stat_buf) == 0;
...
case 'f': /* File is a file? */
unary_advance ();
/* Under POSIX, -f is true if the given file exists
and is a regular file. */
return (stat (argv[pos - 1], &stat_buf) == 0
&& S_ISREG (stat_buf.st_mode));
所以它直接在文件名上使用stat()。 test 没有明确列出目录，但 stat 的 运行 时间可能会受到目录中文件数量的影响。 stat 调用的完成时间将取决于底层文件系统的实现。
对于每个文件系统，stat 会将路径拆分为目录组件，然后向下移动。例如，对于路径 /tmp/hashes/the_md5：首先 /，获取其 inode，然后在其中查找 tmp，获取该 inode（它是一个新的挂载点），然后获取 hashes inode，最后是测试文件名及其 inode。您可以期望一直到 /tmp/hashes/ 的 inode 都被缓存，因为它们在每次迭代时都会重复，因此这些查找很快并且可能不需要磁盘访问。每个查找将取决于父目录所在的文件系统。在 /tmp/ 部分之后，查找发生在 tmpfs 上（它都在内存中，除非你 运行 内存不足并且需要使用交换）。
tmpfs in linux依赖simple_lookup获取目录中文件的inode。 tmpfs 位于树中的旧名称下 linux mm/shmem.c . tmpfs, much like ramfs, doesn't seem to be implementing data structures of its own to keep track of virtual data, it simply relies on VFS directory entry caches (under Directory Entry Caches)。
因此，我怀疑在目录中查找文件的索引节点与哈希查找一样简单 table。 我会说，只要所有临时文件都适合您的内存，并且您使用 tmpfs/ramfs，有多少文件并不重要——每个文件的查找时间为 O(1)时间.
然而，其他文件系统，如 Ext2/3，将受到与目录中存在的文件数量成线性关系的惩罚。
将它们存储在内存中
正如其他人所建议的，您还可以通过将 MD5 存储在 bash 变量中来将它们存储在内存中，并避免文件系统（和相关的系统调用）惩罚。将它们存储在文件系统上的好处是，如果你要中断你的循环，你可以从你离开的地方恢复（你的 md5 可以是一个符号链接到其摘要匹配的文件，你可以依赖，在随后的 运行 s), 但速度较慢。
MD5=d41d8cd98f00b204e9800998ecf8427e
let SEEN_${MD5}=1
...
digest=$(md5hash_of <filename>)
let exists=SEEN_$digest
if [[ "$exists" == 1 ]]; then
# already seen this file
fi
更快的测试
您可以使用 [[ -f my_file ]] 而不是 [ -f my_file ]。命令 [[ 是一个 bash 内置命令，比每次比较都生成一个新进程 (/usr/bin/[) 快得多。这将产生更大的不同。
什么是/usr/bin/[
/usr/bin/test 和 /usr/bin/[ 是两个不同的程序，但是 [ (lbracket.c) 的源代码与 test.c 相同（同样在coreutils):
#define LBRACKET 1
#include "test.c"
所以它们是可以互换的。
我今天不得不编写一个 Bash 脚本来删除重复的文件，使用它们的 md5 哈希值。我将这些哈希值作为文件存储在一个临时目录中：
for i in * ; do
hash=$(md5sum /tmp/msg | cut -d " " -f1) ;
if [ -f /tmp/hashes/$hash ] ;
then
echo "Deleted $i" ;
mv $i /tmp/deleted ;
else
touch /tmp/hashes/$hash ;
fi ;
done
它工作得很好，但让我想知道：这是一种节省时间的方法吗？我最初想到将 MD5 哈希值存储在一个文件中，但后来我想到 "no, because checking whether a given MD5 is in this file requires to re-read it entirely every time"。现在，我想知道：使用 "create files in a directory" 方法时是否相同？当同一目录中有很多文件时，Bash [-f] 是否检查线性或准常数复杂度？
如果它取决于文件系统，tmpfs 的复杂性是多少？
在读取包含散列的文件内容和在作为散列的文件名目录中查找散列之间的选择基本上归结为 "is the kernel quicker at reading a directory or your program at reading a file"。两者都将涉及对每个哈希的线性搜索，因此您最终会得到几乎相同的行为。您可能会争辩说内核应该快一点，但幅度不会太大。请注意，大多数情况下，线性搜索将是详尽无遗的，因为散列不存在（除非您有很多重复文件）。因此，如果您正在处理几千个文件，则搜索将总共处理几百万个条目 — 这是二次行为。
如果您有数百或数千个文件，您最好使用两级层次结构 - 例如，一个目录包含两个字符的子目录 00 .. FF，然后存储其余部分子目录中的名称（或全名）。例如，在 terminfo 目录中使用了此技术的一个小变体。优点是内核只需要读取相对较小的目录来查找文件是否存在。
我还没有 "hashed" 这个，但我会尝试将你的 md5sums 存储在 bash 散列中。
见How to define hash tables in Bash?
将 md5sum 存储为键，如果需要，还可以将文件名存储为值。对于每个文件，只需查看密钥是否已存在于散列 table 中。如果是这样，您不关心该值，但可以使用它来打印出原始重复文件的名称。然后删除当前文件（使用重复键）。不是 bash 专家，这就是我开始寻找的地方。
我喜欢使用正确的工具来完成工作。在这种情况下，您只想查看重复的文件。我已经针对我手头的数千个文件对此进行了测试，重新阅读该文件似乎没有任何问题。另外我注意到我有数百个重复文件。当我将散列存储在单独的文件中然后处理如此大量的文件时，我的系统在一个目录中存储了大约 10,000 个散列文件后慢慢地爬行。将所有哈希值放在一个文件中大大加快了速度。
# This uses md5deep. An alternate is presented later.
md5deep -r some_folder > hashes.txt
# If you do not have md5deep
find . -type f -exec md5sum \{\} \;
这会为您提供所有内容的哈希值。
cut -b -32 hashes.txt | sort | uniq -d > dupe_hashes.txt
这将使用 cut 获取每个文件的哈希值，对哈希值进行排序，然后找到任何重复的哈希值。这些被写入 dupe_hashes.txt 而没有附加文件名。现在我们需要将哈希映射回文件。
(for hash in $(cat dupe_hashes.txt); do
grep "^$hash" hashes.txt | tail -n +2 | cut -b 35-
done) > dupe_files.txt
这对我来说似乎并不运行慢。 Linux 内核在将此类文件保存在内存中而不是经常从磁盘读取它们方面做得非常好。如果你更喜欢强制它在内存中，你可以只使用 /dev/shm/hashes.txt 而不是 hashes.txt。我发现在我的测试中没有必要。
这会为您提供重复的每个文件。到目前为止，一切都很好。您可能想要查看此列表。如果您还想列出原始版本，请从命令中删除 tail -n +2 | 位。
当您觉得可以删除每个列出的文件时，您可以将内容通过管道传输到 xargs。这将以 50 个为一组删除文件。
xargs -L 50 rm < dupe_files.txt
我将尝试定性地回答文件存在性测试在 tmpfs 上的速度有多快，然后我可以建议您如何使整个程序 运行 更快。
首先，tmpfs 目录查找（在内核中）依赖于目录条目缓存散列 table 查找，这对目录中的文件数量不那么敏感。它们受到影响，但呈次线性。它与这样一个事实有关，即正确完成的散列 table 查找需要一些恒定的时间 O(1)，而不管散列 table.
为了解释，我们可以看看 test -f 或 [ -f X ] 所做的工作，来自 coreutils (gitweb):
case 'e':
unary_advance ();
return stat (argv[pos - 1], &stat_buf) == 0;
...
case 'f': /* File is a file? */
unary_advance ();
/* Under POSIX, -f is true if the given file exists
and is a regular file. */
return (stat (argv[pos - 1], &stat_buf) == 0
&& S_ISREG (stat_buf.st_mode));
所以它直接在文件名上使用stat()。 test 没有明确列出目录，但 stat 的 运行 时间可能会受到目录中文件数量的影响。 stat 调用的完成时间将取决于底层文件系统的实现。
对于每个文件系统，stat 会将路径拆分为目录组件，然后向下移动。例如，对于路径 /tmp/hashes/the_md5：首先 /，获取其 inode，然后在其中查找 tmp，获取该 inode（它是一个新的挂载点），然后获取 hashes inode，最后是测试文件名及其 inode。您可以期望一直到 /tmp/hashes/ 的 inode 都被缓存，因为它们在每次迭代时都会重复，因此这些查找很快并且可能不需要磁盘访问。每个查找将取决于父目录所在的文件系统。在 /tmp/ 部分之后，查找发生在 tmpfs 上（它都在内存中，除非你 运行 内存不足并且需要使用交换）。
tmpfs in linux依赖simple_lookup获取目录中文件的inode。 tmpfs 位于树中的旧名称下 linux mm/shmem.c . tmpfs, much like ramfs, doesn't seem to be implementing data structures of its own to keep track of virtual data, it simply relies on VFS directory entry caches (under Directory Entry Caches)。
因此，我怀疑在目录中查找文件的索引节点与哈希查找一样简单 table。 我会说，只要所有临时文件都适合您的内存，并且您使用 tmpfs/ramfs，有多少文件并不重要——每个文件的查找时间为 O(1)时间.
然而，其他文件系统，如 Ext2/3，将受到与目录中存在的文件数量成线性关系的惩罚。
将它们存储在内存中
正如其他人所建议的，您还可以通过将 MD5 存储在 bash 变量中来将它们存储在内存中，并避免文件系统（和相关的系统调用）惩罚。将它们存储在文件系统上的好处是，如果你要中断你的循环，你可以从你离开的地方恢复（你的 md5 可以是一个符号链接到其摘要匹配的文件，你可以依赖，在随后的 运行 s), 但速度较慢。
MD5=d41d8cd98f00b204e9800998ecf8427e
let SEEN_${MD5}=1
...
digest=$(md5hash_of <filename>)
let exists=SEEN_$digest
if [[ "$exists" == 1 ]]; then
# already seen this file
fi
更快的测试
您可以使用 [[ -f my_file ]] 而不是 [ -f my_file ]。命令 [[ 是一个 bash 内置命令，比每次比较都生成一个新进程 (/usr/bin/[) 快得多。这将产生更大的不同。
什么是/usr/bin/[
/usr/bin/test 和 /usr/bin/[ 是两个不同的程序，但是 [ (lbracket.c) 的源代码与 test.c 相同（同样在coreutils):
#define LBRACKET 1
#include "test.c"
所以它们是可以互换的。