# How to handle a sparse array of lists

I have data in the form of a sparse array of lists. For example:

{{76, 17} -> {17803}, {24, 14} -> {18625, 311571, 440371, 818848,
2010244, 2317818}, {64, 99} -> {19421, 269349, 397997, 440343,
503977, 511172, 1600938, 1656131, 1849185, 1849187, 1974513,
2045184, 2065062, 2319929}}


The indices are pairs of integers in the range {0,...,S}^2.

It seems as it is not possible to store this as a sparse array in Mathematica, as I get the error

SparseArray::valnl: "The value specified by the rule {76,17}->{17803} should not be a List. "

How would I create an object which provides:

• quick access to the list corresponding to an entry - for example something like a[[i,j]] (default is the empty list).
• create a (dense) matrix with the largest list element (default 0)
• create a (dense) matrix with the largest list element not bigger than a given constant

Update: Example regarding the last point. If the constant would be 500000, than the entry for {76,17} should be 17803, for {24,14} 440371, for {64,99} 440343 and for all other it should be 0.

-
1) Take a loot at Dispatch it can be really fast. 2)and 3) are not clear to me. –  Kuba Apr 2 '14 at 12:54

Apologies if I've misunderstood your questions. I've never used Dispatch before, as suggested by Kuba in the comments, but it seems to be the right tool for the problem if speed is your concern.

First off, I hope it's clear that accessing the list corresponding to an index pair is as straightforward is applying the rules list for pattern replacement:

rules = {{76, 17} -> {17803}, {24, 14} -> {18625, 311571,
440371, 818848, 2010244, 2317818}, {64, 99} -> {19421, 269349,
397997, 440343, 503977, 511172, 1600938, 1656131, 1849185,
1849187, 1974513, 2045184, 2065062, 2319929}}
drules = Dispatch[rules~Append~(_ -> {})]
(* Note that I've added an additional rule at the end for the "default case" *)
{64, 99} /. drules

(* returns {19421, 269349, 397997, 440343, 503977, 511172, 1600938, 1656131, \
1849185, 1849187, 1974513, 2045184, 2065062, 2319929} *)
{100, 100} /. drules
(* returns {} *)


You can easily write it as a function.

Regarding creating "a (dense) matrix with the largest list element (default 0)" - if I've understood correctly - you could do:

Normal@SparseArray@MapAt[Max, rules, {All, -1}]


And for the "create a (dense) matrix with the largest list element not bigger than a given constant" bit:

With[{c = 500000},
SparseArray@
MapAt[Max@Select[#, Function[x, x <= c]] &,
rules, {All, -1}]];

% // ArrayRules
(* gives {{24, 14} -> 440371, {64, 99} -> 440343, {76, 17} -> 17803, {_, _} ->
0} *)


If your lists are in ascending order (as they are in your example), then you could replace the Select with TakeWhile and the Max with Last. I imagine that might be faster.

-
Thank you for your reply. Dispatch seems a good way. I am not sure if I understand the last bit using Clip correctly and updated my question to make clear what I am looking for. –  Danvil Apr 3 '14 at 22:21
Sorry, I just realized my mistake in understanding your requirement. I'll fix the code in a bit. –  Aky Apr 4 '14 at 13:45
@Danvil fixed it –  Aky Apr 4 '14 at 14:05