☰

如何快速找到最深的子目录

tag-icon • tag-icon filesystem
如何快速找到最深的子目录

这个自我回答的问题更多的是一个新颖性或好奇心的问题。

我知道这可以通过递归遍历所有目录的 bash 脚本来完成。但是它可能需要花费很多时间才能运行。

如何才能快速发现最深的目录级别？

答案1

locate命令是最快的

在这种情况下，locate 命令是你的好朋友：

$ time locate "/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*"
/mnt/clone/home/rick/.gradle/wrapper/dists/gradle-4.6-all/bcst21l2brirad8k2ben1letg/gradle-4.6/samples/userguide/multiproject/dependencies/java/services/personService/src/main/java/org/gradle/sample/services/PersonService.java
/mnt/clone/home/rick/.gradle/wrapper/dists/gradle-4.6-all/bcst21l2brirad8k2ben1letg/gradle-4.6/samples/userguide/multiproject/dependencies/java/services/personService/src/test/java/org/gradle/sample/services/PersonServiceTest.java
/mnt/clone/home/rick/.gradle/wrapper/dists/gradle-4.6-all/bcst21l2brirad8k2ben1letg/gradle-4.6/samples/userguide/multiproject/dependencies/javaWithCustomConf/services/personService/src/main/java/org/gradle/sample/services/PersonService.java
/mnt/clone/home/rick/.gradle/wrapper/dists/gradle-4.6-all/bcst21l2brirad8k2ben1letg/gradle-4.6/samples/userguide/multiproject/dependencies/javaWithCustomConf/services/personService/src/test/java/org/gradle/sample/services/PersonServiceTest.java

real    0m1.731s
user    0m1.653s
sys     0m0.072s

填入足够多的内容/*/*，直到没有结果显示出来，然后减一/*得到最深的子目录层级。最深层级的文件也将被显示出来。

笔记：在这台机器上返回了四个不同的路径。每个路径包含一个文件。

有关定位的一些详细信息

定位使用的数据库由 cron 每日更新。如果您今天安装了应用程序或创建了新目录，则需要使用以下命令更新数据库：

sudo updatedb

在 Ubuntu 19.10 中，locate 命令不再默认安装。希望它会在 20.04 中恢复，但与此同时，您需要使用以下命令安装它：

sudo apt install mlocate

为了了解locate速度，请查看它为即时检索而编制的索引：

$ locate -S

Database /var/lib/mlocate/mlocate.db:
    381,154 directories
    2,548,775 files
    213,049,136 bytes in file names
    92,287,412 bytes used to store database

使用脚本

评论指出人们不知道起点。我写了一个脚本，默认起点为 50 级，并从那里向后工作。你可以用 6 到 126 个子目录级别的起点进行覆盖。

脚本输出：

$ time deepdir

Search point 50 levels deep: /*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*
Common path followed by unique sub-paths (deepest subdir 25 levels):
+- /mnt/clone/home/rick/.gradle/wrapper/dists/gradle-4.6-all/bcst21l2brirad8k2ben1letg/gradle-4.6/samples/userguide/multiproject/dependencies/
|--- /java/services/personService/src/main/java/org/gradle/sample/services/PersonService.java
|--- /java/services/personService/src/test/java/org/gradle/sample/services/PersonServiceTest.java
|--- /javaWithCustomConf/services/personService/src/main/java/org/gradle/sample/services/PersonService.java
|--- /javaWithCustomConf/services/personService/src/test/java/org/gradle/sample/services/PersonServiceTest.java

real    0m45.141s
user    0m44.552s
sys     0m0.588s

$ time deepdir 26

Search point 26 levels deep: /*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*
Common path followed by unique sub-paths (deepest subdir 25 levels):
  (... SNIP repeated parts ...)

real    0m6.123s
user    0m6.041s
sys     0m0.080s
  • 第一次运行脚本时，您不知道子目录的深度。因此，默认的 50 级将需要 43 秒才能运行。
  • 第二次运行脚本时传递已知计数 + 1，并且仅需 6 秒即可运行。
  • 第二次之后，取出输出行/*/*.../*并将其（少 1 组）复制到剪贴板作为调用locate或另一个命令的参数。

bash 脚本

#!/bin/bash

# NAME: deepdir
# PATH: $HOME/askubuntu/
# DESC: Answer for: https://askubuntu.com/questions/1187624/how-to-quickly-find-the-deepest-subdirectory/1187625?noredirect=1#comment1985731_1187625
# DATE: November 11, 2019.

StartLevel=50
[[ $1 != "" ]] && StartLevel="$1"
[[ $StartLevel -gt 126 ]] && { echo Max levels 126 ; exit 1 ; }
[[ $StartLevel -lt   6 ]] && { echo Min levels   6 ; exit 2 ; }

Big="/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*" # 33
Big="$Big/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*" # 31
Big="$Big/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*" # 31
Big="$Big/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*" # 31
                                                       # Total supported: 126

# If starting level populated it is too small.
Search="${Big:0:StartLevel*2}"
echo "Search point $StartLevel levels deep: $Search"
Count=$(locate "$Search" | wc -l)
[[ $Count -gt 0 ]] && { echo "Levels too small. $Count files found" ; exit 3 ; }

# Loop backwards to find first populated level, always more than 5
for (( l=StartLevel; l>5; l-- )) ; do
    Search="${Big:0:l*2}"
    Count=$(locate "$Search" | wc -l)
    [[ $Count -gt 0 ]] && break
done

Arr=( $(locate "$Search") )

# Enhancement using Q&A: Longest common prefix of two strings in bash
#                        https://stackoverflow.com/a/17475354/6929343

Common=\
"$(IFS=$'\n'; sed -e '$!{N;s/^\(.*\).*\n\1.*$/\1\n\1/;D;}' <<<"${Arr[*]}")"
Common="${Common%/*}/"
echo "Common path followed by unique sub-paths (deepest subdir $l levels):"
echo "+- $Common"
Len="${#Common}"

for p in "${Arr[@]}" ; do
    # echo "DEBUG: $p"
    Curr="$(dirname "$p")"
    [[ $Curr != "$Last" ]] && echo "|--- /${p:$Len}"
    Last="$Curr"
done

exit 0

答案2

find -type d \
  -wholename "$(find -type d -print0 |
                tr -d --complement '/\0' |
                sort -zur |
                sed 's:/:*/*:g' |
                head -z -n1 |
                tr -d '\0' )"

我们将使用find来定位所有目录，然后选择路径中斜线最多的目录。值得注意的是，我们将允许任何可能的名称，包括奇数字符，例如换行符、空格或其他字符。

答案3

确实有一种更简单的方法，find有一个-printf动作，其%d格式可以打印 fs 层次结构的深度。

单行

为了获得 10 个最深的目录（从慢性肾脏病）你只需要使用：

find . -type d -printf '%03d %p\n' | sort -n -k 1 | tail -n 10

或者-u您可以通过在命令中添加开关来打印 10 个最大且独特的深度sort：

find . -type d -printf '%03d %p\n' | sort -n -k 1 -u | tail -n 10

例子

该命令的主要形式将输出如下列表：

019 ./vendor/magento/magento2-base/setup/src/Magento/Setup/Test/Unit/Module/Di/_files/app/code/Magento/SomeModule/etc/source/PhpExt.php
020 ./vendor/magento/magento2-base/dev/tests/integration/testsuite/Magento/Framework/View/_files/fallback/design/frontend/Vendor/default/ViewTest_Module/web/i18n/ru_RU
020 ./vendor/magento/magento2-base/dev/tests/integration/testsuite/Magento/Setup/Console/Command/_files/root/lib/internal/Magento/Framework/Test/Unit/View
020 ./vendor/magento/magento2-base/dev/tests/integration/testsuite/Magento/Setup/Module/I18n/Dictionary/_files/source/app/code/Magento/FirstModule/view/frontend
021 ./vendor/magento/magento2-base/dev/tests/integration/testsuite/Magento/Setup/Console/Command/_files/root/lib/internal/Magento/Framework/Test/Unit/View/Element

表现

删除所有虚拟机缓存后，echo 3 > /proc/sys/vm/drop_caches在路径上对脚本进行了测试41454子目录。两种变体花费的时间大致相同：

real    0m6.310s
user    0m0.446s
sys     0m0.708s

这是在一台相对功率不足的服务器上执行的，磁盘被硬限制为3000 IOPS。

笔记

脚本经过测试CentOS 7，不是 Ubuntu，但是我认为它应该可以在具有 GNU 实用程序的 shell 之间轻松移植。

相关内容