Arjen Markus (13 december 2005) In the chatroom yesterday we discussed (or should I say mused over) the pros and cons of using Tcl for biomathematics. One of the subjects was how to reverse a string. Several possibilities have already been published on the Wiki, but this is a comparison of the performance of several on short and long strings.
I find the results remarkable: the behaviour for short strings is completely different than for moderately long strings ... well, judge for yourself.
# Experiments:
# Reversing a string - several ways
#
proc rev_by_string {str} {
set rev ""
set length [string length $str]
for {set i 0} {$i < $length} {incr i} {
set rev "[string index $str $i]$rev"
}
return $rev
}
proc rev_by_append {str} {
set rev ""
set length [string length $str]
for {set i [expr {$length-1}]} {$i >= 0} {incr i -1} {
append rev [string index $str $i]
}
return $rev
}
proc rev_by_list {str} {
set rev ""
foreach c [split $str ""] {
set rev "$c$rev"
}
return $rev
}
proc rev_recursive {str} {
set rev ""
set length [string length $str]
if { $length <= 4 } {
return "[string index $str 3][string index $str 2][string index $str 1][string index $str 0]"
} elseif { $length % 2 == 0 } {
set half [expr {$length/2}]
set halfp1 [expr {$length/2+1}]
return "[rev_recursive [string range $str $halfp1 end]][rev_recursive [string range $str 0 $half]]"
} else {
set half [expr {$length/2}]
set halfp1 [expr {$length/2+1}]
return "[string index $str end][rev_recursive [string range $str $halfp1 end-1]][rev_recursive [string range $str 0 $half]]"
}
}
# Test the procedures ...
puts [rev_by_string "abcdefg"]
puts [rev_by_append "abcdefg"]
puts [rev_by_list "abcdefg"]
puts [rev_recursive "abcdefg"]
puts [rev_recursive "abcdef"]
# Measure the performance
foreach len {1 10 100 1000 10000} repeat {10000 10000 1000 1000 10} {
set str [string repeat ABCDE $len]
puts "String length: [string length $str]"
puts "rev_by_string: [time {rev_by_string $str} $repeat]"
puts "rev_by_append: [time {rev_by_append $str} $repeat]" puts "rev_recursive: [time {rev_recursive $str} $repeat]"
}Here is the result:
gfedcba gfedcba gfedcba gfedcba fedcba String length: 5 rev_by_string: 7 microseconds per iteration rev_by_append: 8 microseconds per iteration rev_by_list: 11 microseconds per iteration rev_recursive: 15 microseconds per iteration String length: 50 rev_by_string: 58 microseconds per iteration rev_by_append: 44 microseconds per iteration rev_by_list: 48 microseconds per iteration rev_recursive: 152 microseconds per iteration String length: 500 rev_by_string: 707 microseconds per iteration rev_by_append: 403 microseconds per iteration rev_by_list: 480 microseconds per iteration rev_recursive: 1561 microseconds per iteration String length: 5000 rev_by_string: 16722 microseconds per iteration rev_by_append: 3671 microseconds per iteration rev_by_list: 13910 microseconds per iteration rev_recursive: 13971 microseconds per iteration String length: 50000 rev_by_string: 1051731 microseconds per iteration rev_by_append: 37300 microseconds per iteration rev_by_list: 1032877 microseconds per iteration rev_recursive: 137735 microseconds per iteration
The solution with append is the definitive winner, but quite surprisingly the solution with recursion, which is slow for short strings, is a good second for long strings.
RS The canonical recursive solution would be
proc rev_rec2 str {
expr {[string length $str]<2? $str:
"[string index $str end][rev_rec2 [string range $str 0 end-1]]"}
}but that hits the recursion limit when strings get longer than 500 or so...
[ [Category ??] ]