C例程opendir(),readdir()和closedir()为我提供了遍历目录结构的方法 . 但是,readdir()返回的每个dirent结构似乎都没有为我提供一个有用的方法来获取我需要递归到目录子目录的DIR指针集 .
当然,他们给我文件的名称,所以我可以将该名称附加到目录路径和stat()和opendir()它们,或者我可以通过chdir()和roll更改进程的当前工作目录它通过chdir(“..”)回来 .
第一种方法的问题是,如果目录路径的长度足够大,那么将包含它的字符串传递给opendir()的成本将超过打开目录的成本 . 如果你有点理论上的话,可以说你的复杂性可能超过线性时间(在目录树中(相对)文件名的总字符数) .
而且,第二种方法存在问题 . 由于每个进程都有一个当前工作目录,因此除了一个线程之外的所有进程都必须在多线程应用程序中进行阻塞 . 此外,我不知道当前工作目录是否仅仅是方便(即,在文件系统查询之前将相对路径附加到它) . 如果是这样,这种方法也会效率低下 .
我接受这些功能的替代品 . 那么如何有效地遍历UNIX目录树(在其下的文件的总字符数中的线性时间)?
4 回答
你试过
ftw()
又名 File Tree Walk ?来自
man 3 ftw
的Snippit:int ftw(const char *dir, int (*fn)(const char *file, const struct stat *sb, int flag), int nopenfd);
可能是你的应用程序有点过分,但这里有一个库,用于遍历包含数亿个文件的目录树 .
https://github.com/hpc/libcircle
您似乎缺少一个基本点:目录遍历涉及从磁盘读取数据 . 即使/如果该数据在缓存中,您最终也会通过相当数量的代码将缓存中的数据传入您的进程 . 路径通常也很短 - 任何超过几百个字节都是非常不寻常的 . 这些意味着您可以非常合理地为所需的所有路径构建字符串,而不会出现任何实际问题 . 与从磁盘读取数据的时间相比,构建字符串所花费的时间仍然很少 . 这意味着您通常可以忽略在字符串操作上花费的时间,并专门用于优化磁盘使用 .
我自己的经验是,对于大多数目录遍历而言,广度优先搜索通常是可取的 - 当您遍历当前目录时,将所有子目录的完整路径放在类似优先级队列的内容中 . 完成遍历当前目录后,从队列中拉出第一个项目并遍历它,继续直到队列为空 . 这通常会改善缓存局部性,因此可以减少读取磁盘所花费的时间 . 根据系统(磁盘速度与CPU速度,可用总内存等),它几乎总是至少与深度优先遍历一样快,并且可以轻松地达到两倍(或左右) .
使用
opendir
/readdir
/closedir
的方法是使函数递归!在Dreamincode.net上查看此处的代码段 .希望这可以帮助 .
EDIT 谢谢R.Sahu,这个链接已经过期了,然而,通过wayback archive找到它并冒昧地将它添加到gist . 请记住,相应地检查许可证并将原作者归于源代码! :)