lreverse

Difference between version 12 and 13 - Previous - Next
    :   '''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
[wdb] Improvement proposal: add option -stride such that one can revert a list of coords {x0 y0 x1 y1 …} or {x0 y0 z0 x1 y1 z1 …}

Example:

======
proc myReverse {args} {
  set li [lindex $args end]
  set option [dict create -stride 1 {*}[lrange $args 0 end-1]]
  for {set i 0} {$i < [dict get $option -stride]} {incr i} {
    lappend argL arg$i
  }
  set cmd list
  foreach arg $argL {
    append cmd " \$$arg"
  }
  lappend lmapBody lmap $argL $li $cmd
  concat {*}[lreverse [eval $lmapBody]]
}
======

How it works:

======
% myReverse {a b c d e f}
f e d c b a
% myReverse -stride 2 {a b c d e f}
e f c d a b
% myReverse -stride 3 {a b c d e f}
d e f a b c
% 
======


<<discussion>> Downward compatibility with Tcl 8.4 and earlier

Implemented in the [changes in Tcl/Tk 8.5] as part of [TIP] #272[http://tip.tcl.tk/272.html].

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
}
======

----
<<discussion>> 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]
    }
}
======

[AMG]: The above code loops forever when given with an empty list.

[LEG]: 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
}
======

----
<<discussion>> 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
======


<<categories>> Command | Performance