我正在开发一个存储与文件系统的 inode 树非常相似的东西的系统。它已经具有与 ls
命令等效的功能,但尚不支持递归选项。我正在研究添加递归选项的实现选择。我想最大限度地提高了解 POSIX ls
的用户的熟悉度,并最大限度地提高任何为使用 POSIX ls -R
的输出而编写的脚本的可移植性。
ls -R
似乎可以用深度优先遍历或广度优先遍历来实现。但是,对于特定遍历顺序是由规范规定还是留作实现选择,我无法找到明确的答案。
在POSIX documentation for ls
,我找不到任何具体的答案。这是我能找到的与递归实现相关的唯一声明:
Implementations are expected to traverse arbitrary depths when processing the -R option. The only limitation on depth should be based on running out of physical storage for keeping track of untraversed directories.
我还尝试查看 nftw
的文档.同样,我在那里没有找到遍历顺序的具体说明。
为了一些实证测量,我在 CentOS 机器上运行了一个测试,那里的行为显然是深度优先遍历。
> uname -a
Linux centos 3.10.0-229.el7.x86_64 #1 SMP Fri Mar 6 11:36:42 UTC 2015 x86_64 x86_64 x86_64 GNU/Linux
> yum info coreutils
Loaded plugins: fastestmirror
Repodata is over 2 weeks old. Install yum-cron? Or run: yum makecache fast
Loading mirror speeds from cached hostfile
* base: mirror.pac-12.org
* elrepo: ftp.osuosl.org
* epel: linux.mirrors.es.net
* extras: repos.lax.quadranet.com
* updates: ftp.osuosl.org
Installed Packages
Name : coreutils
Arch : x86_64
Version : 8.22
Release : 11.el7
Size : 14 M
Repo : installed
From repo : anaconda
Summary : A set of basic GNU tools commonly used in shell scripts
URL : http://www.gnu.org/software/coreutils/
License : GPLv3+
Description : These are the GNU core utilities. This package is the combination of
: the old GNU fileutils, sh-utils, and textutils packages.
> tree testTraversal/
testTraversal/
├── dir1
│ └── dir8
│ └── dir9
│ └── dir10
├── dir2
│ ├── dir4
│ │ └── dir5
│ ├── dir6
│ ├── file1
│ └── file2
├── dir3
└── dir4
└── dir5
└── dir6
└── dir7
├── file3
├── file4
└── file5
> ls -R testTraversal/
testTraversal/:
dir1/ dir2/ dir3/ dir4/
testTraversal/dir1:
dir8/
testTraversal/dir1/dir8:
dir9/
testTraversal/dir1/dir8/dir9:
dir10/
testTraversal/dir1/dir8/dir9/dir10:
testTraversal/dir2:
dir4/ dir6/ file1 file2
testTraversal/dir2/dir4:
dir5/
testTraversal/dir2/dir4/dir5:
testTraversal/dir2/dir6:
testTraversal/dir3:
testTraversal/dir4:
dir5/
testTraversal/dir4/dir5:
dir6/
testTraversal/dir4/dir5/dir6:
dir7/
testTraversal/dir4/dir5/dir6/dir7:
file3 file4 file5
我不知道这是规范规定的行为还是 GNU coreutils 的实现细节。
我自己的观察是,文件系统中的目录结构往往比深度更宽。这表明深度优先通常是内存效率更高的实现选择,尽管可以提出广度优先内存效率更高的反例。
遍历顺序是否在规范中的任何地方规定?如果不是,那么深度优先遍历是否广泛用于实现,因此是比广度优先更安全的假设?
最佳答案
coreutils确实是深度优先。 busybox是深度第一。 BSD/OS X 是深度优先的(实验性的;源代码不可读)。我希望大多数实现都是深度优先的,因为它很容易递归执行,并且因为 POSIX 对路径长度的限制非常严格地限制了深度优先遍历的内存/堆栈使用。
关于algorithm - POSIX ls -R 是否规定了特定的遍历顺序?如果不是,那么哪个假设更可能是可移植的 : depth-first or breadth-first?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/34730190/