`find`를 사용하여 너비 우선 검색을 수행하려면 어떻게해야합니까? 깊이 우선 탐색”으로 설명 할

-depth1 차는 find그것이 깊이 우선 탐색을 수행시킨다.

그러나 기본 순서는 너비 우선 검색 이 아닙니다 .

기본 시퀀스는 비공식적으로 ” 백 트래킹 중에 수행되는 것이 아니라 처음 만나면 노드를 처리하는 깊이 우선 탐색”으로 설명 할 수 있습니다 .

광범위한 첫 번째 검색이 실제로 필요합니다. 어떻게 find이런 식으로 행동 할 수 있습니까?


예를 들어, 다음 설정으로 :

$ mkdir -p alpha/{bravo,charlie,delta}
$ touch alpha/charlie/{alpha,beta,gamma,phi}

find 기본 동작은 다음과 같습니다.

$ find alpha
alpha
alpha/charlie
alpha/charlie/alpha
alpha/charlie/phi
alpha/charlie/beta
alpha/charlie/gamma
alpha/delta
alpha/bravo

그리고와는 -depth다음과 같은 것이 수행

$ find alpha -depth
alpha/charlie/alpha
alpha/charlie/phi
alpha/charlie/beta
alpha/charlie/gamma
alpha/charlie
alpha/delta
alpha/bravo
alpha

그러나 내가 원하는 것은 다음과 같은 (가상) 옵션입니다.

$ find alpha -bfs
alpha
alpha/charlie
alpha/delta
alpha/bravo
alpha/charlie/alpha
alpha/charlie/phi
alpha/charlie/beta
alpha/charlie/gamma

즉 , 계속 진행하기 전에 주어진 깊이에서 모든 파일 / 디렉토리 find를 처리 /보고 해야 합니다 .

어떻게해야합니까?



답변

쉘 와일드 카드만으로도 가능합니다. 점점 더 많은 디렉토리 레벨로 패턴을 작성하십시오.

pattern='*'
set -- $pattern
while [ $# -ne 1 ] || [ "$1" != "$pattern" ]; do
  for file; do
    …
  done
  pattern="$pattern/*"
  set -- $pattern
done

도트 파일이 없습니다. 사용 FIGNORE='.?(.)', KSH에서 shopt -s dotglob떠들썩한 파티에서, 또는 setopt glob_dotszsh을에 포함 할 수 있습니다.

주의 사항 :

  • 파일이 많으면 메모리가 부족합니다.
  • 이것은 디렉토리에 대한 심볼릭 링크를 재귀 적으로 탐색합니다.

순서 나 디렉토리 및 비 디렉토리를 선택하고 성능이 중요하지 않은 경우 두 단계를 수행 [ -d "$file" ]하고 각 단계에서 테스트 할 수 있습니다 .


답변

# cat ./bfind

#!/bin/bash
i=0
while results=$(find "$@" -mindepth $i -maxdepth $i) && [[ -n $results ]]; do
  echo "$results"
  ((i++))
done

이것은 깊이 find와 반복 을 증가시켜 작동합니다. 결과가 반복 될 수 있지만 쉽게 필터링 할 수 있다고 생각합니다.


답변

경로 이름 find/문자 수를 기준으로 정렬하는 정렬로 파이프를 파이프 할 수 있습니다 . 예를 들어

find alpha |
awk '{n=gsub("/","/",$0);printf "%04d/%s\n",n,$0}' |
sort -t/ |
sed 's|[^/]*/||'

이 용도는 awk슬래시의 수와 경로 이름을 앞에, 그리고 sed마지막에이 접두사를 제거 할 수 있습니다.

실제로 디렉토리의 내용을 alpha/charlie+뒤에 나열 하려면 원하는 깊이까지 alpha/charlie말해야 sort -t/ -k1,1 -k2,2 -k3,3 -k4,4합니다.


답변

‘find’가 아니라 bash를 기반으로 한 또 다른 대답은 먼저 “부모 디렉토리의 길이”를 사용한 다음 알파로 정렬하십시오.

결과에 “charlie, bravo, delta”가 있으므로 대답이 일치하지 않지만 알파 순서로 “bravo, charlie, delta”여야하는지 궁금했습니다.

paths_breadth_first() {
  while IFS= read -r line; do
    dirn=${line%/*}         ## dirname(line)
    echo ${#dirn},$line     ## len(dirn),line
  done | sort -n | cut -d ',' -f 2-
}

그 생산

  $ cat /tmp/yy | paths_breadth_first
  alpha
  alpha/bravo
  alpha/charlie
  alpha/delta
  alpha/charlie/alpha
  alpha/charlie/beta
  alpha/charlie/gamma
  alpha/charlie/phi


답변