2d matrix command

alove 13 Oct 2004 - What I'm presenting here is essentially a new TCL command that allows you to very easily create a two dimensional matrix and then add or delete data from it.

Currently there is no elegant way to do this in TCL. You either have to create a list-within-a-list using lindex and lreplace/lrange, or else use a combination of arrays and lists, which is equally awkward. Just figuring out how to create a two dimensional matrix is quite a task!

It would be so much nicer if you could just define a matrix and then set or get variables, like so:

  defx mymatrix 50 50
  setx mymatrix 3 4 'hello world"
  set a [getx mymatrix 3 4]

So I created a set of five commands that would do that, as seen below. RS gave me some very helpful hints for using upvar, string repeat and other coding tips. Then ak pointed out that the tcllib package struct::matrix is designed to create a 2d matrix just like my commands. So I compared the two approaches using time to see which was fastest. the results are summarized below:

 defx                      struct::matrix 
 --------------------------------------------------------------------------------------
 Test setx = 4424 ms       Test set cell = 321170 ms               defx  7260% faster
 Test addx = 7041 ms       Test add rows = 182172 ms               addx  2587% faster
 Test defx = 11358 ms      Test def matrix = 11003083 ms           defx 96875% faster

These results are pretty dramatic. Please see the source programs below to verify the results.

I've always felt that Tcl desperately needs 2D matrix commands as part of its core. They have so many uses: for 2D graphics in games, for databases, for plotting points in graphs, basically anything that requires two dimensions. I am proposing that we include only five new commands - defx, setx and getx are general purpose; addx and delx can be used to add and delete rows, and all the rows below are adjusted, as if you had a list stack in a database.

The advantage of these commands is that they create a standard Tcl list variable that you can manipulate, unlike the struct::matrix package. And they are much faster. If compiled into the Tcl core, they would be fast enoughto use in serious real-time games and simulation programs, thus broadening the appeal of Tcl.


Lars H: Please elaborate how matrices are useful "for 2D graphics in games, for databases, for plotting points in graphs". I don't see how the five operations you suggest would be of much help for any of those (with the possible exception of addx and delx for databases, but for databases there already are such things as mk4tcl to compete with).

alove Let me put it this way: struct::matrix is ALREADY included in the ActiveTCL batteries-included install package, so there's obviously a real demand for it. And these five procs are THOUSANDS of times faster than struct::matrix, in terms of performance. So that says something. ^_^

Lars H: That doesn't quite hold water. struct::matrix is mainly included because it is already a part of struct, and struct is mainly included because it is a part of tcllib. The demand for the total functionality provided by tcllib is far greater than the demand for any little piece of it.

The speed difference works as an argument for including these in tcllib (which may well be a good idea -- the struct module is far too OOP for my taste), but not as an argument for inclusion in the core.

Larry Smith I also have to point out that matrix support is of little use unless a full suite of matrix operations are also supported. To use this stuff for games you need matrix add, multiply, various transpose operations and so on. In short, you'd need exprx.


Lars H: Have you considered a Critcl-powered package as an alternative to a core modification? It's probably very nearly as fast, and much easier to get accepted.

alove 17 Oct - Alright, I'm reading the documentation for Critcl. I'll give it a shot...


RS Matrix access (for lists-of-lists, with lindex and lset) and from 8.5 initialization (with lrepeat) are part of the C-coded Tcl core, and as shown they are pretty fast. So where's the problem?

alove The problem is, it's not obvious to newer programmers that they can create matrices. When they look at the documentation, all they see are list commands. I program with Tcl on Windows and a lot more people would too, very much like BASIC was used in the 80's, if it was more user-friendly. I had no idea that lset and lindex could be used to make matrices, and why would anyone think that? Nowhere in the documentation does it say, "to make a matrix, use these list commands". And you shouldn't have to use list commands to create a matrix, in the same way that you don't have to create a list by saying "set [list a b c]" - we have a special lset command for that.

Besides, there are other features of a matrix that aren't duplicated without code, like adding and deleting specific rows.

RS I agree that the man pages aren't too explicit about what all we can do with lists. Maybe I'm too much in the Lisp tradition where everything could of course be done with lists - matrices, trees, any kind of structures... and the same holds fully for Tcl too. Adding or deleting rows is of course easy with linsert or lreplace - just for adding or deleting columns, it takes a trifle more work.


 # defx - test program

 package require Tcl 8.4
 wm title . "Matrix"
 text .text -height 20 -width 50 -font arial -padx 10 -pady 10
 pack .text -expand yes -fill both

 proc K {a b} {set a}
 proc defx {v a b} {
    upvar $v var; set var [string repeat "{[string repeat {{} } $b]} "  $a]
 }
 proc setx {v a b value} {upvar $v var; lset var $a $b $value}
 proc getx {v a b} {upvar $v var; lindex $var $a $b}
 proc delx {v a} {upvar $v var; set var [lreplace [K $var [set list {}]] $a $a]}
 proc addx {v a} {
    upvar $v var; set new [string repeat {{} } [llength [lindex $var 0]]]
    lappend var $new
    if {$a ne "end"} then {
       set a1 [expr {[llength $var] - 1}] 
       for {set x $a1} {$x > $a} {incr x -1} {lset var $x [lindex $var [expr {$x - 1}]]}
       lset var $a $new
    }
 }

 # test the matrix.  Ranges must be positive integers.

 set a 10; set b 5
 defx wow $a $b                ;# define a matrix: rows/columns
 setx wow 4 1 hello        ;# set row 4, col 1 = "hello"
 setx wow 5 2 big        ;# this row is deleted using 'delx' below
 setx wow 6 3 world
 setx wow 9 4 end
 delx wow 5                ;# delete row 5; now there are only nine rows
 addx wow 5                ;# add row 5 back again (empty); now there are 10 rows

 .text insert end "defx Matrix wow ($a rows, $b cols) \n\n"
 .text insert end "Total rows = [llength $wow] \n\n"
 foreach x $wow {
    foreach y $x {
       .text insert end "#$y \t"
    }
    .text insert end "\n"
 }

 proc set_command {} {
 global wow
 for {set x 0} {$x < 1000} {incr x} {setx wow 4 1 hello}
 }        
 set t [time {set_command} 1]
 .text insert end "\nTest setx = $t\n"

 proc add_command {} {
 global wow
 for {set x 0} {$x < 1000} {incr x} {addx wow end}
 }
 set t [time {add_command} 1]
 .text insert end "Test addx = $t\n"

 proc def_command {} {
 defx neo 1000 1000
 }
 set t [time {def_command} 1]
 .text insert end "Test defx = $t\n"

And here is the struct::matrix program that I used for the time trial:

 # struct::matrix - test program

 package require Tcl 8.4
 package require struct::matrix 1.2.1
 wm title . "Matrix"
 text .text -height 20 -width 50 -font arial -padx 10 -pady 10
 pack .text -expand yes -fill both

 # test the matrix.  Ranges must be positive integers.
 set a 10; set b 5

 ::struct::matrix wow
 wow add rows $a
 wow add columns $b

 wow set cell 1 4 hello
 wow set cell 2 5 big
 wow set cell 3 6 world
 wow set cell 4 9 end
 wow delete row 5
 wow add rows 1
 .text insert end "::struct::matrix wow ($a rows, $b cols) \n\n"
 .text insert end "Total rows = [wow rows] \n\n"

 for {set x 0} {$x < [wow rows]} {incr x} {
 for {set y 0} {$y < [wow columns]} {incr y} {        

 .text insert end "#[wow get cell $y $x] \t"
 }
 .text insert end "\n"
 }

 proc x_settimer {} {
 for {set x 0} {$x < 1000} {incr x} {wow set cell 1 4 hello}
 }        
 set t [time {x_settimer} 1]
 .text insert end "\nTest set cell = $t\n"

 proc add_command {} {
 for {set x 0} {$x < 1000} {incr x} {wow add rows 1}
 }
 set t [time {add_command} 1]
 .text insert end "Test add rows = $t\n"

 proc def_command {} {
 ::struct::matrix neo
 wow add rows 1000
 wow add columns 1000
 }
 set t [time {def_command} 1]
 .text insert end "Test def matrix = $t\n"

AM Interesting - I have been contemplating an investigation into the performance of various ways to create and update a matrix with numbers - this in response to Partial Differential Equations