我正在编写一个C程序,用于计算给定目录中文件的总大小。我知道每个文件都指向一个inode,因此我打算使用stat
来查找inode值和文件大小。由于我想避免错误的计算,当有多个硬连接和/或sym连接到一个inode时,我想将inode存储在一个数组中。问题是,现在要检查inode对于给定文件是否是唯一的,我将不得不遍历inode数组,给出大约n^2
的运行时间。我想避免过度复杂的结构,如RB树。有没有更快,更聪明的方式来实现这一点?我知道有这样的系统工具,我想知道他们是如何实现这样的。检查文件是否在C中唯一的好方法
0
A
回答
3
即使二叉树是一个不错的选择,因为根据随机数据他们是相对平衡。这也是一个非常简单的实施结构。
通常,选择的结构是具有恒定平均搜索时间的散列表。这里面临的挑战是为您的数据找到一个好的散列函数。散列表的实现并不困难,我想你可以找到很多好的库来实现它们。
但是,如果你愿意等待,直到你存储在阵列中的所有inode,那么你可以排序这个数组,为了找到重复遍历它..
编辑:
Inode包含一个引用计数。这将计算硬链接的数量。因此,您可以检查参考计数> 1的inode中的重复项。
2
使用散列表。这是O(1)(虽然对于小套来说有点贵)。当然,你可能会发现这个“过于复杂”,正如你对红黑树所说的那样,但是如果你想要好的最坏情况的表现,你需要做一些比普通数组更复杂的东西(顺便说一下尽管理论上的时间复杂性更差,但是对于小集合来说最快)
如果没有一个已有(这是C毕竟)哈希表的实现呢,有几个在这里的概述:https://stackoverflow.com/a/8470745/4323
相关问题
- 1. 什么是使用PHP检查图像是否唯一的好方法?
- 2. 检查t-sql中的值是否唯一的最佳方法
- 3. C++,检查文件是否存在的最快方法?
- 4. 插件名称检查是否唯一
- 5. 更好的方法来检查一个句子是否是Python中的回文
- 6. 这是检查DyanmoDB表是否存在的最好方法吗?
- 7. 最好的方法来检查一个URL是否有效
- 8. C检查文件是否存在
- 9. 检查DLL文件是否是C#中的CLR程序集的最佳方法
- 10. 检查一个文件是否是C中的特定类型
- 11. 什么是一个很好的方法来检查一个double是否是C#中的整数?
- 12. 检查文件是否是C#中的媒体文件
- 13. 如何检查文件是否是C++中的常规文件?
- 14. 是否有更好的方法来覆盖文件,然后检查更改(在C#中)?
- 15. 更好的方法来检查是否执行查询
- 16. objective-c检查复制文件是否准备好
- 17. 检测isIpad是否更好的方法?
- 18. 检查结果是否唯一
- 19. Codeigniter - 检查值是否唯一
- 20. PHP检查数组值是否唯一
- 21. Z3:检查模型是否唯一
- 22. 什么是检查Web API是否可用的好方法?
- 23. 什么是检查屏幕是否被修改的好方法?
- 24. Python:有没有一种检查文本是否被加密的好方法?
- 25. 检查启动时文件是否存在的有效方法
- 26. 如何检查文件夹中是否存在文件C
- 27. 检查url命名空间是否唯一的最佳方法是什么?
- 28. 如何检查输入的ID是否与C唯一
- 29. 什么是检查文件是否改变的最快方法?
- 30. C#:什么是生成唯一文件名的最快方法?
通常,目录中的文件数量(未执行递归)可能不是很高以保证散列表。所以二叉树可能实际上比散列表更快。 – mrQWERTY 2015-02-24 01:16:44