c - POSIX 操作系统的 C 语言文件浏览器

Question

我为嵌入式设备创建了一个文件浏览 UI。在嵌入式方面，我能够获取硬盘目录中的所有文件并返回名称、大小、修改等统计信息。这是使用 opendir 和 closedir< 完成的 和一个 while 循环遍历每个文件，直到没有文件为止。

这很酷，直到文件数量达到很大数量。我需要实现分页和排序。假设我在一个目录中有 10,000 个文件——我怎么可能遍历这么多文件并根据大小、名称等进行排序，而不轻易破坏 RAM(大约 1mb 的 RAM...!)。也许硬盘操作系统或驱动程序中已经存在某些东西？

Answer 1

这里有两个建议，它们都占用很小的内存空间。第一个将使用的内存不会超过您希望为请求返回的结果数。这是一个恒定时间的 O(1) 内存——它只取决于结果集的大小，但如果用户真的翻阅所有结果，最终是二次时间(或更糟):

您只是在寻找一个小的分页结果(例如 r=25 条目)。您可以通过扫描所有文件名并维护您将返回的项目的排序列表来生成这些，使用长度为 r 的插入排序，并且对于插入的每个文件，仅保留前 r 个结果。 (实际上，如果文件 F 低于第 r 条目，您将不会插入文件 F)。

您将如何生成结果的第 2^nd 页？您已经知道上一个请求的第 25 个文件 - 因此在扫描期间忽略之前的所有条目。 (如果对有重复的字段进行排序，您将需要更加努力)

好处是所需的最小内存 - 所需的内存不会比您希望返回的 r 结果大很多(如果您不缓存名称，甚至可以更少)。缺点是生成的完整结果将在时间上与您拥有的文件总数成二次方。实际上，人们不会对结果进行排序然后翻阅所有页面，因此这可能是可以接受的。

如果您的内存预算较大(例如少于 10000 个文件)但您仍然没有足够的空间来对所有 10000 个文件名执行简单的内存排序，那么 seekdir/telldir 是您的 friend 。即通过流式传输 readdir 并使用 telldir 捕获每个条目的位置来创建一个多头数组。 (您甚至可以将每个 telldir 之间的增量压缩为 2 字节短)。作为一个最小的实现，您可以使用 clib 的排序函数对它们进行排序，并编写您自己的回调以将位置转换为可比较的值。您的回调将使用 seekdir 两次来读取这两个文件名。

上面的方法有点矫枉过正——你只是对所有条目进行了排序，而你只需要一页 ~25，所以为了好玩，为什么不阅读 Hoare 的 QuickSelect 算法并使用它的一个版本来识别要求范围内的结果。您可以递归地忽略所需范围之外的所有条目，只对结果的第一个和最后一个条目之间的条目进行排序。