[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_by_list:    [time {rev_by_list     $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...
----

[JMN] The following two solutions show that a list-based approach is not necessarily slow as suggested by the above timings.
These two appear to be ever so slightly faster than the append solution for medium & large lists.

 proc rev_by_lset {str} {
    set len [string length $str]
    foreach c [set str [split $str ""]] {
        lset str [incr len -1] $c
    }
    return [join $str ""]
 }
 proc rev_by_lappend {str} {
    set len [llength [set str [split $str ""]]]
    while {$len} {
        lappend res [lindex $str [incr len -1]]
    }
    return [join $res ""]
 }


[[
[Category Algorithm] |
[Category Performance]
]]