Die Community zu .NET und Classic VB.
Menü

VB.NET-Tipp 0098: Breadth-First-Traversion statt Rekursion

 von 

Beschreibung

Der sehr listige Ordner rekursiv nach Dateien durchsuchen [Tipp 23] bietet eine hohe Flexiblität der Suche, indem die Rekursion in eine Klasse ausgelagert ist, die die "Fundstücke" per Event an den Aufrufer sendet, wo sie validiert werden. Es zeigt sich dort sehr deutlich ein prinzipielles Problem von Rekursionen - nämlich, dass Mechanismen entwickelt werden müssen, die den Kontext (dort: Suchbedingungen) bis in die innerste Verschachtelung der rekursiven Aufrufe hineinreichen. Ordner rekursiv nach Dateien durchsuchen [Tipp 23] ist dementsprechend komplex. Das Verfahren erfordert eine extra Klasse, die Validierung der Suchbedingungen ist auf 2 Eventhandler verstreut, und eine Framework-konforme Ausgestaltung der Events würde es noch erfordern, für jedes Event eine spezielle EventArgs-Klasse anzulegen.

Eine einfachere Alternative zum rekursiven Durchgang ist die Breadth-First-Traversion. Ihr Vorteil liegt vor allem darin, dass sie innerhalb einer While-Schleife ausgeführt wird und somit den Methoden-Kontext gar nicht verlässt, wordurch also auch keine Umständlichkeit entsteht, Suchbedingungen inklusive Fehlerbehandlung zu exportieren. Als Nachteil einer Breadth-First-Traversion kann man den temporär hohen Speicherverbrauch ansehen, da die Kindknoten eines Elementes zunächst in einer Queue zwischengespeichert werden. Der "Nachteil" erweist sich aber als praktisch irrelevant: Selbst die vollständige Durchsuchung eines Laufwerkes (C: - 22000 Verzeichnisse) führte lediglich zu einer maximalen Queue-Länge von 4410 Elementen.

Schwierigkeitsgrad:

Schwierigkeitsgrad 2

Framework-Version(en):

.NET Framework 2.0, .NET Framework 3.0, .NET Framework 3.5

.NET-Version(en):

Visual Basic 2005, Visual Basic 2008

Download:

Download des Beispielprojektes [9,17 KB]

' Dieser Quellcode stammt von http://www.activevb.de
' und kann frei verwendet werden. Für eventuelle Schäden
' wird nicht gehaftet.

' Um Fehler oder Fragen zu klären, nutzen Sie bitte unser Forum.
' Ansonsten viel Spaß und Erfolg mit diesem Source!

' Projektversion:   Visual Studio 2005
' Option Strict:    An
'
' Referenzen: 
'  - System
'  - System.Data
'  - System.Xml
'
' Imports: 
'  - Microsoft.VisualBasic
'  - Microsoft.VisualBasic.ControlChars
'  - System
'  - System.Collections
'  - System.Collections.Generic
'  - System.Data
'  - System.Diagnostics
'

' ##############################################################################
' ################################ modMain.vb ##################################
' ##############################################################################
Imports Microsoft.VisualBasic.ControlChars
Imports System.IO
Imports System.Environment

Public Module modMain

    Public Sub Main()
        Dim windows As String = _
            (New DirectoryInfo(GetFolderPath( _
                SpecialFolder.System))).Parent.FullName
        Dim root As String = Path.GetPathRoot(windows)
        Dim dokumenteUndEinstellungen As String = _
            (New DirectoryInfo(GetFolderPath( _
                SpecialFolder.Desktop))).Parent.Parent.FullName
        Dim programs As String = GetFolderPath(SpecialFolder.ProgramFiles)
        Dim excludeds As New List(Of String)

        Console.WriteLine("Mindestens im ersten Durchlauf empfiehlt es " & _
            "sich, möglichst viele Ordner zu überspringen, um die " & _
            "Laufzeit abzukürzen." & Lf & Lf)

        For Each folder As String In New String() _
            {windows, dokumenteUndEinstellungen, programs}

            If Confirm("""" & folder & """ überspringen?") Then _
                excludeds.Add(folder)
        Next

        Dim sl As New List(Of String)
        sl.Add(Lf & "Durchsuchter Ordner:     " & root)
        sl.Add("Gesuchte Endung:         .exe" & Lf)
        sl.Add("Ausgeschlossene UnterOrdner:" & Lf)

        For Each s As String In excludeds
            sl.Add(s)
        Next
        sl.Add(Lf)

        Dim inputSummary As String = String.Join(Lf, sl.ToArray)
        sl.Clear()
        Console.WriteLine(inputSummary)

        If Not Confirm("Anfangen?") Then Return

        Dim children As New Queue(Of String)
        Dim fileCount, dirCount, queueMax As Integer
        children.Enqueue(root)

        While children.Count > 0
            Dim dir As String = children.Dequeue
            If excludeds.Contains(dir) Then
                Console.WriteLine("{0}##### überspringe        ""{1}""", _
                    Lf, dir)
                If Not Confirm("Fortfahren?") Then Return
            Else
                Try
                    Array.ForEach(Directory.GetDirectories(dir), _
                        AddressOf children.Enqueue)
                    dirCount += 1
                    If children.Count > queueMax Then queueMax = children.Count

                    For Each s As String In Directory.GetFiles(dir, "*.exe", _
                        SearchOption.TopDirectoryOnly)

                        fileCount += 1
                        Console.WriteLine(s)
                    Next
                Catch ex As UnauthorizedAccessException
                    Console.WriteLine("{0}##### UnauthorizedAccessException" & _
                        " bei Zugriff auf:{0}""{1}""{0}", Lf, dir)
                    If Not Confirm("Fortfahren?") Then Return
                End Try
            End If
        End While

        sl.Add(Lf & Lf & "Zusammenfassung" & Lf & inputSummary & Lf)
        sl.Add("durchsuchte Directories: " & dirCount)
        sl.Add("gefundene Dateien:       " & fileCount)
        sl.Add("Maximale Queue-Größe war:" & queueMax)
        sl.Add("Programm-Ende")
        Console.Write(String.Join(Lf, sl.ToArray))
        Console.ReadKey()
    End Sub

    Private Function Confirm(ByVal msg As String) As Boolean
        Console.Write(msg & " [j]")
        Confirm = Console.ReadKey.KeyChar = "j"c
        Console.WriteLine()
        Console.WriteLine()
    End Function
End Module

Ihre Meinung  

Falls Sie Fragen zu diesem Artikel haben oder Ihre Erfahrung mit anderen Nutzern austauschen möchten, dann teilen Sie uns diese bitte in einem der unten vorhandenen Themen oder über einen neuen Beitrag mit. Hierzu können sie einfach einen Beitrag in einem zum Thema passenden Forum anlegen, welcher automatisch mit dieser Seite verknüpft wird.

Archivierte Nutzerkommentare 

Klicken Sie diesen Text an, wenn Sie die 1 archivierten Kommentare ansehen möchten.
Diese stammen noch von der Zeit, als es noch keine direkte Forenunterstützung für Fragen und Kommentare zu einzelnen Artikeln gab.
Aus Gründen der Vollständigkeit können Sie sich die ausgeblendeten Kommentare zu diesem Artikel aber gerne weiterhin ansehen.

Kommentar von Jo am 08.06.2009 um 08:48

Ganz ehrlich - für ein Funktionsbeispiel ist der Code mit vielzuviel unnötigen Abfragen gespickt.

Ein einfaches: So gehts hätte locker gereicht und wäre für Einsteiger weniger verwirrend. Schade!