Tree Find

The find sub-command in Tree (and TreeView) is powerful and useful for returning lists of nodes. Many tree commands can work on node lists, eg.

 set ids [$t find -name Kallie -key first]
 $t set $ids income 0

Nested Finds

Normally, find is used to do a search-traverse of an entire subtree. However, the -nodes option can be used with a tag or list of nodes to support nested searches:

 set ids [$t find -name Kallie -key first]
 $t find -name Ingram -key last -nodes $ids

Find Exec Performance

The following example compares performance of find -exec/-command and compares it to with:

set t [tree create]
set n 0
while {[incr n]<10000} {
    $t insert end -data [list A 1 B $n]
}

set m 0
puts [time { $t find -notop -exec {
    set a [$t get %# A]
    set b [$t get %# B]
    if {($a > $b && $b>50) || ($b == $a) || ($b == -$a)} {
        incr m [expr {$a+$b}]
    } else {
        incr m [expr {$a-$b}]
    }
    incr m -$a
    incr m -$b
} }]
puts "M(-exec):\t$m"
#################

set m 0
puts [time { $t find -notop -var id -exec {
    set a [$t get $id A]
    set b [$t get $id B]
    if {($a > $b && $b>50) || ($b == $a) || ($b == -$a)} {
        incr m [expr {$a+$b}]
    } else {
        incr m [expr {$a-$b}]
    }
    incr m -$a
    incr m -$b
} }]
puts "M(-exec/-var):\t$m"
#################

proc foo {t id} {
    variable m
    set a [$t get $id A]
    set b [$t get $id B]
    if {($a > $b && $b>50) || ($b == $a) || ($b == -$a)} {
        incr m [expr {$a+$b}]
    } else {
        incr m [expr {$a-$b}]
    }
    incr m -$a
    incr m -$b
}

foo $t 1

set m 0
puts [time { $t find -notop -command [list foo $t]}]
puts "M(-command):\t$m"
#################

set m 0
puts [time { $t with x [$t children 0] {
    set a $x(A)
    set b $x(B)
    if {($a > $b && $b>50) || ($b == $a) || ($b == -$a)} {
        incr m [expr {$a+$b}]
    } else {
        incr m [expr {$a-$b}]
    }
    incr m -$a
    incr m -$b
} }]
puts "M(with):\t$m"
#################

and outputs

1461012 microseconds per iteration
M(-exec):       -99989998
293238 microseconds per iteration
M(-exec/-var):  -99989998
219079 microseconds per iteration
M(-command):    -99989998
313220 microseconds per iteration
M(with):        -99989998

It is evident -exec without -var is by far the slowest.

© 2008 Peter MacDonald