linux - 如何递归列出某个位置的所有目录，广度优先？

Question

广度优先列表很重要，在这里。此外，限制搜索的深度会很好。

$ find . -type d
/foo
/foo/subfoo
/foo/subfoo/subsub
/foo/subfoo/subsub/subsubsub
/bar
/bar/subbar

$ find . -type d -depth
/foo/subfoo/subsub/subsubsub
/foo/subfoo/subsub
/foo/subfoo
/foo
/bar/subbar
/bar

$ < what goes here? >
/foo
/bar
/foo/subfoo
/bar/subbar
/foo/subfoo/subsub
/foo/subfoo/subsub/subsubsub

如果可能的话，我想使用 bash 单线来做到这一点。如果有一个 javascript-shell，我会想象类似的东西

bash("find . -type d").sort( function (x) x.findall(/\//g).length; )

score 35 · Accepted Answer

该find命令支持-printf识别大量占位符的选项。

一个这样的占位符是%d呈现给定路径的深度，相对于find开始的位置。

因此，您可以使用以下简单的单线：

find -type d -printf '%d\t%P\n' | sort -r -nk1 | cut -f2-

它非常简单，不依赖于繁重的工具，例如perl.

这个怎么运作：

它在内部生成文件列表，每个文件都呈现为两个字段的行
第一个字段包含深度，用于（反向）数字排序，然后切掉
结果是简单的文件列表，每行一个文件，按最深的第一顺序

score 24 · Accepted Answer

如果您想使用标准工具执行此操作，则应使用以下管道：

find . -type d | perl -lne 'print tr:/::, " $_"' | sort -n | cut -d' ' -f2

那是，

一阶深度查找并打印此处的所有目录
计算每个目录中的斜杠数量并将其添加到路径中
按深度排序（即斜线数）
只提取路径。

要限制找到的深度，请将 -maxdepth 参数添加到 find 命令。

如果您希望以与 find 输出它们的顺序相同的顺序列出目录，请使用“sort -n -s”而不是“sort -n”；“-s”标志使排序稳定（即，保留相等比较的项目之间的输入顺序）。

score 8 · Accepted Answer

您可以使用 find 命令， find /path/to/dir -type d 下面是当前目录中目录的示例列表：

find . -type d

score 7 · Accepted Answer

我的感觉是，这是一个比前面提到的更好的解决方案。它涉及 grep 等以及一个循环，但我发现它工作得很好，特别是对于您希望行缓冲而不是完整的 find 缓冲的情况。

它更耗费资源，因为：

很多分叉
很多发现
当前深度之前的每个目录被 find 命中的次数与文件结构的总深度一样多（如果您实际上有任何数量的 ram，这应该不是问题......）

这很好，因为：

它使用 bash 和基本的 gnu 工具
它可以随时被打破（就像你看到你正在寻找的东西飞过一样）
它按行而不是按查找工作，因此后续命令不必等待查找和排序
它基于实际的文件系统分离工作，所以如果你有一个带有斜杠的目录，它不会被列出得比它更深；如果您配置了不同的路径分隔符，您仍然可以。

#!/bin/bash
深度=0

同时找到-mindepth $depth -maxdepth $depth | grep '.'
做
    深度=$((深度+1))
完毕

你也可以很容易地将它放在一条线上（？）：

depth=0; while find -mindepth $depth -maxdepth $depth | grep --color=never '.'; do depth=$((depth + 1)); done

但我更喜欢小脚本而不是打字......

score 6 · Accepted Answer

我认为您不能使用内置实用程序来做到这一点，因为在遍历目录层次结构时，您几乎总是需要深度优先搜索，无论是自上而下还是自下而上。这是一个 Python 脚本，可以为您提供广度优先搜索：

import os, sys

rootdir = sys.argv[1]
queue = [rootdir]

while queue:
    file = queue.pop(0)
    print(file)
    if os.path.isdir(file):
        queue.extend(os.path.join(file,x) for x in os.listdir(file))

编辑：

使用os.path-module 代替os.stat-function 和stat-module。
使用list.popandlist.extend代替deland+=运算符。

score 3 · Accepted Answer

我试图找到一种方法来做到这一点，find但它似乎没有任何类似的-breadth选择。如果不为其编写补丁，请尝试以下 shell 咒语（对于 bash）：

LIST="$(find . -mindepth 1 -maxdepth 1 -type d)";
while test -n "$LIST"; do
    for F in $LIST; do
        echo $F;
        test -d "$F" && NLIST="$NLIST $(find $F -maxdepth 1 -mindepth 1 -type d)";
    done;
    LIST=$NLIST;
    NLIST="";
done

我有点偶然发现了这个，所以我不知道它是否一般有效（我只是在你询问的特定目录结构上测试它）

如果要限制深度，请在外部循环中放置一个计数器变量，如下所示（我也在为此添加注释）：

# initialize the list of subdirectories being processed
LIST="$(find . -mindepth 1 -maxdepth 1 -type d)";
# initialize the depth counter to 0
let i=0;
# as long as there are more subdirectories to process and we haven't hit the max depth
while test "$i" -lt 2 -a -n "$LIST"; do
    # increment the depth counter
    let i++;
    # for each subdirectory in the current list
    for F in $LIST; do
        # print it
        echo $F;
        # double-check that it is indeed a directory, and if so
        # append its contents to the list for the next level
        test -d "$F" && NLIST="$NLIST $(find $F -maxdepth 1 -mindepth 1 -type d)";
    done;
    # set the current list equal to the next level's list
    LIST=$NLIST;
    # clear the next level's list
    NLIST="";
done

（将 2 替换-lt 2为深度）

基本上，这实现了标准的广度优先搜索算法，使用$LIST和$NLIST作为目录名称的队列。这是后一种方法，作为一种简单的复制和粘贴方法：

LIST="$(find . -mindepth 1 -maxdepth 1 -type d)"; let i=0; while test "$i" -lt 2 -a -n "$LIST"; do let i++; for F in $LIST; do echo $F; test -d "$F" && NLIST="$NLIST $(find $F -maxdepth 1 -mindepth 1 -type d)"; done; LIST=$NLIST; NLIST=""; done

score 2 · Accepted Answer

没有应得的排序：find -maxdepth -type d

要获得应得的排序，您必须自己使用这个小 shellscript 进行递归：

#!/bin/bash
r () 
{
    let level=$3+1
    if [ $level -gt $4 ]; then return 0; fi
    cd "$1"
    for d in *; do
        if [ -d "$d" ]; then
            echo $2/$d
        fi;
    done
    for d in *; do
        if [ -d "$d" ]; then
            (r "$d" "$2/$d" $level $4)
        fi;
    done
}
r "$1" "$1" 0 "$2"

然后您可以使用参数基目录和深度调用此脚本。

score 1 · Accepted Answer

这是一种可能的方法，使用查找。我还没有彻底测试它，所以用户要小心......

depth=0
output=$(find . -mindepth $depth -maxdepth $depth -type d | sort); 
until [[ ${#output} -eq 0 ]]; do 
  echo "$output"
  let depth=$depth+1
  output=$(find . -mindepth $depth -maxdepth $depth -type d | sort)
done

score 0 · Accepted Answer

像这样的东西：

find . -type d | 
  perl -lne'push @_, $_;
    print join $/,
      sort { 
        length $a <=> length $b || 
          $a cmp $b 
        } @_ if eof'

linux - 如何递归列出某个位置的所有目录，广度优先？

9 回答 9

Related

Reference