[PD] complex network
Mathieu Bouchard
matju at artengine.ca
Sat Apr 4 18:35:47 CEST 2009
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
More information about the Pd-list
mailing list