Multidimensional slicing

[bearophile]

Joseph Rushton Wakeling:

> Suppose I have some data in an 2-dimensional associative array 
> (it could be larger dimension, but let's limit it to 2d for 
> now).  I'm using an associative array because the underlying 
> data is sparse, i.e. for any given index pair (i, j) there's 
> most likely not an entry.

In Python people that want to use a associative arrays to store a 
sparse 2D array usually use just one associative array, where the 
keys are (r,c) pairs. But you can't "slice" this.

In low level languages for sparse 2D arrays often people use 
something different. One popular choice is to use just a (dense) 
array for the first coordinate, and to put just index-value pairs 
(with ordered indexes) into such arrays. It's a simple solution, 
but it's often good enough. If the rows contain many items (more 
than 50-100) it's better to chunk each row in some way.

If you want to slice on both coordinates consider using two data 
structures, where the second contains pointers to the first, and 
if you want to add/remove items then maybe each value needs a 
pointer to the start of the array.

See also:
http://en.wikipedia.org/wiki/Sparse_matrix


> It's trivial to take a slice of this data using the first 
> dimension, i.e. if a[i][j] gives the value for the key pair (i, 
> j), a[i] will give the array of values for all values of j, and 
> a[i].keys will give me all the values of j that are "connected" 
> to i.
>
> ... however, I can't do this the opposite way, i.e. to slice it 
> a[][j] -- I get an error message, e.g.:
>
>     Error: ulong[ulong][ulong] cannot be sliced with []
>
> and similarly there is no way to identify a[][j].keys i.e. all 
> the i indexes associated with j.

Maybe you are able to create a wrapper, that wraps the 2D 
associative array, and uses a little "most recently used" cache 
stored in a little array to memoize some of the last lookups on 
the first coordinate. But first it's better to try simpler 
solutions.

Bye,
bearophile