lreverse list
Returns a list containing the elements of its argument, list, in reverse order.
Implemented in the changes in Tcl/Tk 8.5 as part of TIP #272[L1 ].
Downward compatible pure-Tcl version:
proc lreverse list {
set res {}
set i [llength $list]
while {$i > 0} {lappend res [lindex $list [incr i -1]]}
set res
} ;# RSLEG: List reversion is used e.g. in functional programming map and reduce or fold respectively. Therefore execution time and memory requirements are important issues.
In fact the above Tcl version is the fastest implementation. To make backwards compatible code with lreverse you can use the following boilerplate code, which squeezes out some more microseconds by reducing one bracket evaluation in the loop.
if {[info command lreverse] == ""} {
proc lreverse l {
set r {}
set i [llength $l]
while {[incr i -1]} {lappend r [lindex $l $i]}
lappend r [lindex $l 0]
}
}At the moment of this writing there are little references to lreverse in the wiki, which indicates that until now, everybody has reverted his/her list 'by hand'.
The following is an ad nauseam exploration of pure-Tcl lreverse. You can just skip to the section Consolidated timing results for some numbers. There you find all implementations listed in order of execution time for a small list. It is very interesting to see, that the ordering by the second column - reverting a longer list - would be different. Obviously the builtin version wins by magnitudes, on long lists, since no function calls are needed between iterations. The main surprise however is, that the dumb concat/list implementation of lreverse2 scales much better on longer lists than lset and, worse, linsert which are used in lreverse6 and lreverse5 respectively. The big winner, however is the countdown while loop, which given in the above form is even slightly faster.
It would be interesting to time the tail recursive implementations lreverse7 and lreverse8 with Tail call optimization.
The use of the new (as in Tcl8.5) {*} syntax in lreverse8 does not provide better speed, the standard implemention with lindex/lrange in lreverse7 is arguably uglier but faster on long lists.
# LEG20081207: list reverse in comparision
# default quiet version of :
proc : args {}
# verbose version of : proc : args {foreach arg $args {puts $arg}}
: Introduction {
This is a comparision of different Tcl implementation of the
(Tcl 8.5) lreverse command.
Each implementation is tested and timed with the following test
string:
}
set l {1 {2 3} {4 {5 6}} 7}
: $l
: lreverse {First we test the builtin lreverse command}
if {[catch {package require Tcl 8.5}]} {
: {Sorry, lreverse is available from Tcl 8.5 or later only} {
it seems, you are running an earlier version:} $tcl_version
} else {
puts "testing builtin: lreverse $l => [lreverse $l]"
# preclude initial delay of time command
time {lreverse $l} 1
puts [time {lreverse $l} 10000]
}
: lreverse1 {
Is the implementation given by Richard Suchenwirth on the Tcl'ers
Wiki http://wiki.tcl.tk/17188
}
proc lreverse1 list {
set res {}
set i [llength $list]
while {$i > 0} {lappend res [lindex $list [incr i -1]]}
set res
} ;# RS
puts "testing lreverse1 $l => [lreverse1 $l]"
time {lreverse1 $l} 1
puts [time {lreverse1 $l} 10000]
: lreverse2 {
Is a minimal implementation based only on the basic Tcl list
operators. Note: it does not use linsert and such looses time with
an additional function call.
}
proc lreverse2 l {
set r {}; foreach e $l {set r [concat [list $e] $r]}
set r
}
puts "testing lreverse2 $l => [lreverse2 $l]"
time {lreverse2 $l} 1
puts [time {lreverse2 $l} 10000]
: lreverse3 {
Is an implementation using a for loop counting down from the end
of the list.
}
proc lreverse3 l {
for {set i [llength $l]} {$i} {} {
incr i -1; lappend r [lindex $l $i]
}
set r
}
puts "testing lreverse3 $l => [lreverse3 $l]"
time {lreverse3 $l} 1
puts [time {lreverse3 $l} 10000]
: lreverse4 {
Is a recursive version. Especially for larger lists it would
not work well.
}
proc lreverse4 l {
if {[llength $l]==1} {return $l}
concat [lreverse4 [lrange $l 1 end]] [list [lindex $l 0]]
}
puts "testing lreverse4 $l => [lreverse4 $l]"
time {lreverse4 $l} 1
puts [time {lreverse4 $l} 10000]
: lreverse5 {
Uses the linsert command to stuff each element on top of the
result list.
}
proc lreverse5 l {
set r {}
foreach e $l {set r [linsert $r 0 $e]}
set r
}
puts "testing lreverse5 $l => [lreverse5 $l]"
time {lreverse5 $l} 1
puts [time {lreverse5 $l} 10000]
: lreverse6 {
Uses the lset command, which appeared first in Tcl 8.4.
}
if {[catch {package require Tcl 8.4}]} {
: {Sorry, lreverse is available from Tcl 8.4 or later only} {
it seems, you are running an earlier version:} $tcl_version
} else {
proc lreverse6 l {
set i [llength $l]
foreach e $l {incr i -1; lset l $i $e}
set l
}
puts "testing lreverse6 $l => [lreverse6 $l]"
time {lreverse6 $l} 1
puts [time {lreverse6 $l} 10000]
}
: lreverse7 {
Is a tail recursive version, which could gain speed over the
normal recursion by tail call optimization, and work with
arbitrary length lists.
}
proc lreverse7 {l {r {}}} {
if {[llength $l]==1} {
linsert $r 0 $l
} else {
lreverse7 \
[lrange $l 1 end] \
[linsert $r 0 [lindex $l 0]]
}
}
puts "testing lreverse7 $l => [lreverse7 $l]"
time {lreverse7 $l} 1
puts [time {lreverse7 $l} 10000]
proc _lreverse8 {r f args} {
if {[llength $args]} {
_lreverse8 [linsert $r 0 $f] {*}$args
} else {
linsert $r 0 $f
}
}
proc lreverse8 l {_lreverse8 {} {*}$l}
puts "testing lreverse8 $l => [lreverse8 $l]"
time {lreverse8 $l} 1
puts [time {lreverse8 $l} 10000]
puts "testing _lreverse8 {} {*}$l => [_lreverse8 {} {*}$l]"
time {_lreverse8 {} {*}$l} 1
puts [time {_lreverse8 {} {*}$l} 10000]
set l [lrepeat 800 a]; puts "longer list: 800 elements"
puts "lreverse"
time {lreverse $l} 1
puts [time {lreverse $l} 1000]
puts "lreverse1"
time {lreverse1 $l} 1
puts [time {lreverse1 $l} 1000]
puts "lreverse2"
time {lreverse2 $l} 1
puts [time {lreverse2 $l} 1000]
puts "lreverse3"
time {lreverse3 $l} 1
puts [time {lreverse3 $l} 1000]
puts "lreverse4"
time {lreverse4 $l} 1
puts [time {lreverse4 $l} 1000]
puts "lreverse5"
time {lreverse5 $l} 1
puts [time {lreverse5 $l} 1000]
puts "lreverse6"
time {lreverse6 $l} 1
puts [time {lreverse6 $l} 1000]
puts "lreverse7"
time {lreverse7 $l} 1
puts [time {lreverse7 $l} 1000]
puts "lreverse8"
time {lreverse8 $l} 1
puts [time {lreverse8 $l} 1000]
puts "_lreverse8"
time {_lreverse8 {} {*}$l} 1
puts [time {_lreverse8 {} {*}$l} 1000]
: {Consolidated timing results} {
small long lreverse comment
list list implementation
0.59 6 builtin: obviously the fastest solution
1.87 116 lreverse1: countdown while loop with lappend
1.89 118 lreverse3: countdown for loop with lappend
2.57 245 lreverse6: foreach with lset (Tcl8.4) <- one []
3.48 3256 lreverse5: foreach with linsert <- two []
4.58 924 lreverse2: foreach with concat [list $e] $r <- three []
5.63 9084 _lreverse8: tail recursion with {*} (Tcl8.5)
5.98 3862 lreverse4: simple recursion
6.33 9097 lreverse8: tail recursion wrapper (*) (Tcl8.5)
6.34 7188 lreverse7: tail recursion with lindex/lrange
} {Timing results} {
The following is the output of sourcing this file on my laptop, a Dell
Latitude D630 Notebook with intel core duo and 2GB RAM, and Active
State Tcl 8.5
} {
testing builtin: lreverse 1 {2 3} {4 {5 6}} 7 => 7 {4 {5 6}} {2 3} 1
0.5942 microseconds per iteration
testing lreverse1 1 {2 3} {4 {5 6}} 7 => 7 {4 {5 6}} {2 3} 1
1.8672 microseconds per iteration
testing lreverse2 1 {2 3} {4 {5 6}} 7 => 7 {4 {5 6}} {2 3} 1
4.5811 microseconds per iteration
testing lreverse3 1 {2 3} {4 {5 6}} 7 => 7 {4 {5 6}} {2 3} 1
1.8902 microseconds per iteration
testing lreverse4 1 {2 3} {4 {5 6}} 7 => 7 {4 {5 6}} {2 3} 1
5.9768 microseconds per iteration
testing lreverse5 1 {2 3} {4 {5 6}} 7 => 7 {4 {5 6}} {2 3} 1
3.4821 microseconds per iteration
testing lreverse6 1 {2 3} {4 {5 6}} 7 => 7 {4 {5 6}} {2 3} 1
2.5686 microseconds per iteration
testing lreverse7 1 {2 3} {4 {5 6}} 7 => 7 {4 {5 6}} {2 3} 1
6.3424 microseconds per iteration
testing lreverse8 1 {2 3} {4 {5 6}} 7 => 7 {4 {5 6}} {2 3} 1
6.3327 microseconds per iteration
testing _lreverse8 {} {*}1 {2 3} {4 {5 6}} 7 => 7 {4 {5 6}} {2 3} 1
5.629 microseconds per iteration
longer list: 800 elements
lreverse
6.204 microseconds per iteration
lreverse1
116.202 microseconds per iteration
lreverse2
924.386 microseconds per iteration
lreverse3
118.412 microseconds per iteration
lreverse4
3862.613 microseconds per iteration
lreverse5
3255.545 microseconds per iteration
lreverse6
244.969 microseconds per iteration
lreverse7
7187.639 microseconds per iteration
lreverse8
9097.354 microseconds per iteration
_lreverse8
9084.144 microseconds per iteration
}