On Fri, 3 Apr 2009, Frank Barknecht wrote:
The last paragraph explains sparse matrices or rather, why you often don't need to treat them specially in Lua.
Well, you better treat them specially in Lua, else you'd implement a nonspecial matrix product using three for-loops as usual, and then the result of two sparse matrices will be a nonsparse matrix. What do you do with that? No, you need to treat them specially, because assigning a bunch of zeroes in a lua table will take RAM. Furthermore, I just tried Lua, and you do need to treat every nil value specially, because you can't perform arithmetic on nil (which is quite normal). This is fixed by defining a method for the __index selector (using [] sends a __index message to the table).
And then their triangle matrix gimmick... the very fact that those tables are actually hashtables instead of anything like pd float tables, make them take usually twice RAM or more (perhaps 3 or 4 depending on their implementation) if you just use all slots, so if you only use half of the slots then you're not saving any RAM at all compared to pd's float tables.
That page is not outright lying, but it's definitely not telling the truth.
Hashtables of pairs are one way to represent sparse matrices, but if you ever need to lookup complete rows or columns, then you need a hashtable of hashtables for rows, columns, or both (twice the same data transposed).
Depending on how sparse the nonzero data is supposed to be and how clustered the nonzero data is supposed to be and how you need to be accessing/transforming the data, some other representations may be more attractive than the hash or the hash-of-hashes. For example:
* matrix-of-matrix: a 400x400 matrix could be cut into 20x20 pieces put into a 20x20 matrix and so every 20x20 piece that is completely filled with 0 is not allocated and instead replaced by a nil or zero. You can tune the size of the pieces depending on what goes well with the data set. * quadtree: make a 2x2 matrix of 2x2 matrices of 2x2 matrices of 2x2 matrices of 2x2 matrices of 2x2 matrices of ... and just don't allocate any piece that only contains zeroes.Here I suppose that this is using "ordinary arrays" as you can find in Python, Ruby, C/C++, Tcl, etc., and apparently not Lua (?). But you could do quite similar things with Lua anyway. In any case, each of those representations needs algorithms customised for them, unless you can figure out a generic design that is efficient with several representations, perhaps using a "foreachnonzero" loop operation as the central concept.
_ _ __ ___ _____ ________ _____________ _____________________ ... | Mathieu Bouchard - tél:+1.514.383.3801, Montréal, Québec
_______________________________________________ Pd-list@iem.at mailing list UNSUBSCRIBE and account-management -> http://lists.puredata.info/listinfo/pd-list
