在bash中查找重复文件的时间复杂性

Question

我今天必须编写一个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哈希存储在一个文件中,但后来我想"不,因为检查给定的MD5是否在这个文件中需要每次都重新读取它".现在,我想知道:使用"在目录中创建文件"方法时它是一样的吗？当同一目录中有大量文件时,Bash [-f]是否检查线性或准常量复杂度？

如果它取决于文件系统,那么tmpfs的复杂性是多少？

Answer 1

我将尝试定性地回答 tmpfs 上文件存在测试的速度有多快，然后我可以建议如何使整个程序运行得更快。

首先，tmpfs 目录查找（在内核中）依赖于目录条目缓存哈希表查找，这对目录中的文件数量并不那么敏感。它们受到影响，但呈次线性影响。这与以下事实有关：O(1)无论哈希表中的项数有多少，正确完成的哈希表查找都需要一些恒定的时间 。

为了解释这一点，我们可以看看coreutils ( gitweb )中的test -f,​​ 或,完成的工作：[ -f X ]

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：first /，获取其inode，然后在其内部查找tmp，获取该inode（它是一个新的挂载点），然后获取hashesinode，最后获取测试文件名及其inode。您可以期望索引节点一直/tmp/hashes/被缓存，因为它们在每次迭代中都会重复，因此这些查找速度很快并且可能不需要磁盘访问。每次查找都取决于父目录所在的文件系统。在这/tmp/部分之后，查找发生在 tmpfs 上（这一切都在内存中，除非您耗尽内存并需要使用交换）。

Linux中的tmpfs依赖于simple_lookup获取目录中文件的inode。tmpfs 以其旧名称位于linux mm/shmem.c树中。tmpfs 与 ramfs 非常相似，似乎没有实现自己的数据结构来跟踪虚拟数据，它只是依赖于 VFS 目录项缓存（在Directory Entry Caches下）。

因此，我怀疑在目录中查找文件的索引节点就像哈希表查找一样简单。我想说，只要所有临时文件都适合您的内存，并且您使用 tmpfs/ramfs，那么有多少文件并不重要——每次查找都是 O(1) 的。

然而，其他文件系统（例如 Ext2/3）将产生与目录中存在的文件数量呈线性关系的损失。

将它们存储在内存中

正如其他人所建议的，您还可以通过将 MD5 存储在 bash 变量中来将它们存储在内存中，并避免文件系统（和相关的系统调用）惩罚。将它们存储在文件系统上的优点是，如果您要中断循环，您可以从离开的位置恢复（您的 md5 可能是其摘要匹配的文件的符号链接，您可以在后续运行中依赖它），但是慢点。

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"

所以它们是可以互换的。