# -*- tcl -*-
proc unionA {args} {
switch [llength $args] { 0 { return {} } 1 { return [lindex $args 0] } default { foreach set $args { foreach e $set { set tmp($e) . } } return [array names tmp] } }
}
proc unionB {args} {
switch [llength $args] { 0 { return {} } 1 { return [lindex $args 0] } default { set tmp {} foreach set $args { foreach e $set { lappend tmp $e } } # remove duplicates -- # sort and scan. shortcut in case of empty or # single-element result. if {[llength $tmp] < 2} { return $tmp } set tmp [lsort tmp] set last [lindex $tmp 0] set tmp [lrange $tmp 1 end] set res $last foreach e $tmp { if {[string compare $e $last] != 0} { lappend res $e set last $e } } return $res } }
}
proc unionC {args} {
switch [llength $args] { 0 { return {} } 1 { return [lindex $args 0] } default { set tmp {} foreach set $args { foreach e $set { lappend tmp $e } } # -W- remove duplicates -- # hash out. shortcut in case of empty or # single-element result. if {[llength $tmp] < 2} { return $tmp } foreach e $tmp { set tmpa($e) . } return [array names tmpa] } }
}
# A O(nm)
# B O(nm+nmlognm)
# C O(nm)
foreach {i text a b} {
01 {10/10/0} {1 2 3 4 5 6 7 8 9 0} {a b c d e f g h i j} 02 {05/10/0} {1 2 3 4 5} {a b c d e f g h i j} 03 {10/05/0} {1 2 3 4 5 6 7 8 9 0} {a b c d e} 04 {05/05/0} {1 2 3 4 5} {a b c d e} 05 {15/15/0} {1 2 3 4 5 6 7 8 9 0 p q r s t} {a b c d e f g h i j k l m n o} 06 {15/10/0} {1 2 3 4 5 6 7 8 9 0 p q r s t} {a b c d e f g h i j} 07 {10/15/0} {1 2 3 4 5 6 7 8 9 0} {a b c d e f g h i j k l m n o} 08 {10/10/5} {1 2 3 4 5 6 7 8 9 0} {1 2 3 4 5 f g h i j} 09 {05/10/5} {a b c d e} {a b c d e f g h i j} 10 {10/05/5} {a b c d 5 e 7 8 9 0} {a b c d e} 11 {05/05/5} {1 2 3 4 5} {1 2 3 4 5} 12 {15/15/5} {1 2 3 4 5 6 7 8 9 0 a b c d e} {a b c d e f g h i j k l m n o} 13 {15/10/5} {1 2 3 4 5 6 7 8 9 0 p q r s t} {1 2 3 4 5 f g h i j} 14 {10/15/5} {k l m n o 6 7 8 9 0} {a b c d e f g h i j k l m n o}
} {
puts stderr "-- $i --" ; flush stderr puts stdout "--------------------------------------" puts stdout "$i A $text [time {unionA $a $b} 2000]" puts stdout "$i B $text [time {unionB $a $b} 2000]" puts stdout "$i C $text [time {unionC $a $b} 2000]"
}
puts stdout "--------------------------------------"