Version 10 of lreverse

Updated 2014-03-09 13:49:17 by PeterLewerin
lreverse list

Returns a list containing the elements of its argument, list, in reverse order.

http://www.tcl.tk/man/tcl8.5/TclCmd/lreverse.htm

  Downward compatibility with Tcl 8.4 and earlier

Implemented in the changes in Tcl/Tk 8.5 as part of TIP #272[L1 ].

Downward compatible pure-Tcl version:

if {[info command lreverse] == ""} {
    proc lreverse list {
        set res {}
        set i [llength $list]
        while {$i} {
            lappend res [lindex $list [incr i -1]]
        }
        set res
    } ;# RS
}

  Comparing efficiency among different pure-Tcl implementations

LEG: 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 comparison
# default quiet version of : 
proc : args {}
# verbose version of : proc : args {foreach arg $args {puts $arg}}
: Introduction {
    This is a comparison of different Tcl implementations 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 Tcler's
   Wiki http://wiki.tcl.tk/17188
}
proc lreverse1 list {
    set res {}
    set i [llength $list]
    while {$i} {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 loses 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. For all intents and purposes the same as lreverse1.
}
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]

: lreverse9 {
    Lars H: This is not fast, but it avoids index arithmetic. The idea can be
    nice in cases where you want to process the list elements while reversing
    their order.
}
proc lreverse9 {l} {
    set stack {}
    foreach item $l {set stack [list $stack $item]}
    set res {}
    while {[llength $stack]} {
       foreach {stack item} $stack break
       lappend res $item
    }
    return $res
}
puts "testing lreverse9 $l => [lreverse9 $l]"
time {lreverse9 $l} 1
puts [time {lreverse9 $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]
puts "lreverse9"
time {lreverse9 $l} 1
puts [time {lreverse9 $l} 1000]

: {Consolidated timing results} {

    This list was redone 2014-03-09 on a Sony VAIO with an i3 2.40 GHz
    and 4GB RAM (3.67 usable), and ActiveState Tcl 8.6.

small long lreverse               comment
list  list implementation
1.49    5  builtin:   obviously the fastest solution
2.20   91  lreverse1: countdown while loop with lappend
1.62   97  lreverse3: countdown for loop with lappend
2.36  184  lreverse6: foreach with lset (Tcl8.4) <- one []
4.66  597  lreverse9: stack/unstack
3.36 2352  lreverse5: foreach with linsert <- two []
4.07 2639  lreverse2: foreach with concat [list $e] $r <- three []
5.01 4608  lreverse4: simple recursion
4.93 5176  lreverse7: tail recursion with lindex/lrange
5.24 7590 _lreverse8: tail recursion with {*} (Tcl8.5)
5.93 7592  lreverse8: tail recursion wrapper (*) (Tcl8.5)
} {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
}

  Inverting a dictionary

AMG: [lreverse] can be used to invert a dict such that the keys and values exchange places.

This is not very efficient, since the dict has to be converted to a list representation before it can be reversed, then a new dict has to be created; however it is convenient. Often you have the data in a list representation to begin with, so in practice the performance might not be an issue.

Be careful with dicts that have duplicate values, since applying [lreverse] results in duplicate keys. The dict command discards duplicate keys, but normally it keeps the last instance of a duplicate. When using [lreverse] it instead keeps the first instance.

set map {a 1 b 1 c 2}
set inv {1 a 1 b 2 c}
dict get $map b          ;# returns 1
dict get $inv 1          ;# returns b
set inv [lreverse $map]  ;# returns "2 c 1 b 1 a"
dict get $map b          ;# returns 1
dict get $inv 1          ;# returns a