POSIX ls -R 是否规定了特定的遍历顺序?如果不是,那么哪个假设更可能是可移植的:深度优先还是广度优先?
Does POSIX ls -R dictate a specific traversal order? If not, then which assumption is more likely to be portable: depth-first or breadth-first?
我正在开发一个存储与文件系统的 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 的一个实现细节。
我自己的观察是文件系统中的目录结构往往比深度更宽。这表明深度优先通常是内存效率更高的实现选择,尽管可以提出广度优先内存效率更高的反例。
遍历顺序是否在规范中的任何地方规定?如果不是,那么深度优先遍历在实现中是否被广泛使用,因此是比广度优先更安全的假设?
我正在开发一个存储与文件系统的 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 的一个实现细节。
我自己的观察是文件系统中的目录结构往往比深度更宽。这表明深度优先通常是内存效率更高的实现选择,尽管可以提出广度优先内存效率更高的反例。
遍历顺序是否在规范中的任何地方规定?如果不是,那么深度优先遍历在实现中是否被广泛使用,因此是比广度优先更安全的假设?