在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哈希存储在一个文件中,但后来我想“不,因为检查给定的MD5是否在这个文件中需要每次都重新读取它”.现在,我想知道：使用“在目录中创建文件”方法时它是一样的吗？当同一目录中有大量文件时,Bash [-f]是否检查线性或准常量复杂度？ 如果它取决于文件系统,那么tmpfs的复杂性是多少？ 解决方法
我将尝试定性地回答文件存在测试在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().没有目录列表通过测试显式完成,但stat的运行时可能会受到目录中文件数量的影响. stat调用的完成时间取决于不可靠的文件系统实现. 对于每个文件系统,stat会将路径拆分为目录组件,然后向下拆分.例如,对于路径/ tmp / hashes / the_md5：first /,获取其inode,然后查找其中的tmp,获取该inode(它是一个新的挂载点),然后获取散列inode,最后获取测试文件名及其i节点.您可以期望inode一直到/ tmp / hashes /被缓存,因为它们在每次迭代时都会重复,因此这些查找很快并且可能不需要磁盘访问.每次查找都取决于父目录所在的文件系统.在/ tmp /部分之后,查找发生在tmpfs(全部在内存中,除非你的内存不足并且需要使用swap). linux中的tmpfs依赖于simple_lookup来获取目录中文件的inode. tmpfs位于树 linux mm/shmem.c 中的旧名称下.tmpfs与ramfs非常相似,似乎没有实现自己的数据结构来跟踪虚拟数据,它只依赖于VFS目录条目缓存(在Directory Entry Caches下). 因此,我怀疑在目录中查找文件的inode就像哈希表查找一样简单.我会说只要你的所有临时文件都适合你的内存,而你使用tmpfs / ramfs,那里有多少文件并不重要 – 每次都是O(1)查找. 但是,像Ext2 / 3这样的其他文件系统会产生与目录中存在的文件数量成线性关系的惩罚. 将它们存储在内存中 正如其他人所建议的那样,您也可以通过将MD5存储在bash变量中来将MD5存储在内存中,并避免文件系统(和相关的系统调用)处罚.将它们存储在文件系统中的优势在于,如果要中断循环,可以从中断的位置继续(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" 所以它们是可以互换的. （编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |