Version 3 of Directory recursion

Updated 2006-12-05 13:30:36

AMG: This page gives some directory recursion scripts. Each prints the names of all subdirectories of the current directory, but of course you can change them to do whatever you need.

1. Iterative, breadth-first traversal, Tcl 8.5, [lappend]

 proc ftw_1 {{dirs .}} {
    while {[llength $dirs] != 0} {
       set dirs [lassign $dirs name]
       lappend dirs {*}[glob -nocomplain -directory $name -type d *]
       puts $name
    }
 }

2. Iterative, breadth-first traversal, Tcl 8.5, [list] + {*}

 proc ftw_2 {{dirs .}} {
    while {[llength $dirs] != 0} {
       set dirs [list {*}[lassign $dirs name] {*}[glob -nocomplain -directory $name -type d *]]
       puts $name
    }
 }

3. Iterative, breadth-first traversal, Tcl 8.4

 proc ftw_3 {{dirs .}} {
    while {[llength $dirs] != 0} {
       set dirs [concat [lrange $dirs 1 end] [glob -nocomplain -directory [lindex $dirs 0] -type d *]]
       puts $name
    }
 }

4. Iterative, depth-first traversal, Tcl 8.5, [lassign]

 proc ftw_4 {{dirs .}} {
    while {[llength $dirs] != 0} {
       set dirs [lassign $dirs name]
       set dirs [list {*}[glob -nocomplain -directory $name -type d *] {*}$dirs]
       puts $name
    }
 }

5. Iterative, depth-first traversal, Tcl 8.5, [lreplace]

 proc ftw_5 {{dirs .}} {
    while {[llength $dirs] != 0} {
       set dirs [lreplace $dirs 0 0 {*}[glob -nocomplain -directory [lindex $dirs 0] -type d *]]
       puts $name
    }
 }

6. Iterative, depth-first traversal, Tcl 8.5, [lrange]

 proc ftw_6 {{dirs .}} {
    while {[llength $dirs] != 0} {
       set dirs [list {*}[glob -nocomplain -directory [lindex $dirs 0] -type d *] {*}[lrange $dirs 1 end]]
       puts $name
    }
 }

7. Iterative, depth-first traversal, Tcl 8.4

 proc ftw_7 {{dirs .}} {
    while {[llength $dirs] != 0} {
       set dirs [concat [glob -nocomplain -directory [lindex $dirs 0] -type d *] [lrange $dirs 1 end]]
       puts $name
    }
 }

8. Recursive, depth-first traversal

 proc ftw_8 {{name .}} {
    puts $name
    foreach subdir [glob -nocomplain -directory $name -type d *] {
       ftw_8 $subdir
    }
 }

For this application, [linsert] is too clumsy because it errors when instructed to insert zero elements; therefore it would have to be wrapped with an [if] (or [catch], hehehe).

I [time]d the above procedures (sans [puts]) on a certain directory tree. Here are the results:

 % foreach p [info procs ftw_*] {puts "$p: [time $p 10]"}
 ftw_1: 519323.9 microseconds per iteration
 ftw_2: 512807.2 microseconds per iteration
 ftw_3: 665287.1 microseconds per iteration
 ftw_4: 518121.0 microseconds per iteration
 ftw_5: 515800.6 microseconds per iteration
 ftw_6: 515826.2 microseconds per iteration
 ftw_7: 595750.0 microseconds per iteration
 ftw_8: 515477.5 microseconds per iteration

And a bit of analysis:

• The fastest two do the least amount of list and variable manipulation. By no means does recursion make ftw_8 slow.
• The slowest two are the ones using [concat]. Yay {*}!
• The fastest implementation is ftw_2, but breadth-first is an unconventional directory traversal.
• The fastest depth-first implementation is ftw_8, since recursion apparently is quite fast.
• I don't know why ftw_3 and ftw_7 have different execution times, but in repeated trials the difference is consistent.

---

See Matthias Hoffmann - Tcl-Code-Snippets - misc - globx

---

[ Category File ]