Wie kann ich mit `find` eine Breitensuche durchführen?

14

Die -depthprimäre findUrsache bewirkt, dass eine Tiefensuche durchgeführt wird.

Die Standardsequenz ist jedoch keine Breitensuche.

Die Standardsequenz könnte informell als "Tiefen-Erste-Durchquerung, die Knoten behandelt, wenn sie zum ersten Mal angetroffen werden, anstatt dies während des Zurückverfolgens zu tun" beschrieben werden.

Ich habe ein tatsächliches Bedürfnis nach einer breiten ersten Suche. Wie kann ich mich so findverhalten?

Zur Veranschaulichung mit folgendem Setup:

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

find hat das folgende Standardverhalten:

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

und mit -depthführt es wie folgt aus:

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

Was ich jedoch möchte, ist die folgende (fiktive) Option:

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

Mit anderen Worten, ich muss alle Dateien / Verzeichnisse in einer bestimmten Tiefe findverarbeiten / melden, bevor ich fortfahre.

Wie kann ich das machen?

find Platzhalter
quelle

Nicht mit find(zumindest nicht nur mit find). Möchten Sie nur die Dateien auflisten oder andere Primärdaten verwenden?

Gilles 'SO - hör auf böse zu sein'

@ Gilles, eigentlich wurde mir klar, dass -bfsdas nicht ganz das ist, was ich brauche ... Ich habe ein einfaches Skript, das einen Index für ein großes GitLab-Projekt generiert, das für die Aufnahme in das GitLab-Wiki geeignet ist. Die Header werden hierarchisch basierend auf Verzeichnisnamen erstellt. Es funktioniert hervorragend, außer dass es in der obigen Beispieldateistruktur deltaunter dem charlieUnterheader und nicht unter dem übergeordneten alphaHeader abgelegt wird .

Wildcard

Eine weitere seltsame Sache ist , dass meine findAusgabe ist alphabetisch sortiert. Keine Ahnung warum ....

Wildcard

Trotzdem denke ich , -bfs könnte nützlich sein, auch wenn es nicht perfekt diesen Anwendungsfall passt.

Wildcard

2

Ich habe ein solches Tool implementiert: bfs . Es ist noch nicht 100% funktionskompatibel mit GNU find, aber es ist da.

Tavian Barnes

6

Sie können dies nur mit Shell-Platzhaltern tun. Erstellen Sie ein Muster mit zunehmend mehr Verzeichnisebenen.

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

Hier fehlen Punktedateien. Verwenden Sie FIGNORE='.?(.)'in ksh, shopt -s dotglobin bash oder setopt glob_dotsin zsh, um sie einzuschließen.

Vorsichtsmaßnahmen:

Dies wird den Speicher sprengen, wenn viele Dateien vorhanden sind.
Dadurch werden symbolische Verknüpfungen zu Verzeichnissen rekursiv durchlaufen.

Wenn Sie die Reihenfolge oder Verzeichnisse und Nichtverzeichnisse auswählen möchten und die Leistung nicht kritisch ist, können Sie zwei Durchgänge durchführen und [ -d "$file" ]bei jedem Durchgang testen .

Gilles 'SO - hör auf böse zu sein'
quelle

@ Wildcard Ja, das habe ich getan.

Gilles 'SO - hör auf böse zu sein'

1

Nett! Noch eine fast triviale Einschränkung: Eine Datei, die die einzige Datei in einem Verzeichnis ist, kann nicht verarbeitet werden, wenn die Datei buchstäblich benannt ist *. :)

Wildcard

@ Wildcard Oh ja, das habe ich vergessen zu erwähnen. Verwenden Sie bash oder zsh mit nullglobund (($#))als Schleifenbedingung, um diesen Randfall zu vermeiden.

Gilles 'SO - hör auf böse zu sein'

5

# cat ./bfind

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

Dies funktioniert durch Erhöhen der Tiefe findund Wiederholen. Ich denke, es kann Ergebnisse wiederholen, könnte aber leicht gefiltert werden

user239175
quelle

Entschuldigung, ich wusste nichts über den Formatierungsmechanismus. Wie auch immer, eigentlich wiederholt es sich nicht, denke ich, weil es weniger als mindepth abschneidet

user239175

3

Sie können Ihre findin eine Sortierung umleiten, die hauptsächlich nach der Anzahl der /Zeichen im Pfadnamen sortiert ist . Beispielsweise,

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

Hiermit wird awkdem Pfadnamen die Anzahl der Schrägstriche sedvorangestellt und dieses Präfix am Ende entfernt.

Da Sie wahrscheinlich möchten, dass der Inhalt des Verzeichnisses alpha/charlie+danach aufgelistet wird alpha/charlie, müssen Sie bis sort -t/ -k1,1 -k2,2 -k3,3 -k4,4zur gewünschten Tiefe sagen .

meuh
quelle

0

Eine andere Antwort, die nicht auf 'find', sondern auf bash basiert - verwenden Sie zuerst die "Länge des übergeordneten Verzeichnisses" und sortieren Sie dann nach Alpha.

Die Antwort stimmt nicht ganz überein, da Ihre Ergebnisse "charlie, bravo, delta" haben, aber ich habe mich gefragt, ob es "bravo, charlie, delta" in Alpha-Reihenfolge sein sollte.

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-
}

Das produziert

  $ 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

qneill
quelle

Wie kann ich mit `find` eine Breitensuche durchführen?

Antworten: