# Efficient by-element updates to SparseArrays

I have a very large SparseArray called A. What is the most efficient way to update say element {i,j} with value x to the value f[x] ? I worry about memory usage and code speed if I need to make a very large number of updates. I've seen Leonid's comment here about a similar problem. But there is a lot of info scattered over old SO site and I am looking for function and a syntax something like f[A_, {i_,j_}, f_] that will do the job. I think it is a very essential question for recursive by-element updates to SparseArrays' and would love to see a complete solution here.

-
A simple A[[i, j]] = f[x] wouldn't suffice? –  Guess who it is. Jan 26 '12 at 21:05
@J.M. Yes, unless I am falling into the 2nd case described by Leonid, which I am. Thanks for the comment though. –  Vitaliy Kaurov Jan 27 '12 at 4:56

If you need a batch update, then the answer is in my comment you linked. If you need element-by-element, then there are two cases:

• Most of values you update are non-zero (or, generally, not equal to default element). In this case, I believe the answer of @Mr. Wizard is optimal, and you should expect update of a single element to be constant time.
• Most (or at least a sizable fraction) of these elements are initially zero (or, default element). Then, you are out of luck. I gave a brief answer to a similar request in this thread. Basically, SparseArray object keeps lists of non-zero elements and their positions in packed arrays. Therefore, a transition from zero to non-zero for an element requires insertion in the middle of them, which is O(n) operation, where n is the current number of non-zero elements. So, this is the same situation as building a list with Append, and it will lead to a quadratic complexity.

This tidbit is not well-known, so I'd like to emphasize it again: element-by-element update for the SparseArray generally has complexity ~ updates * nzero, where updates is the number of updates, and nzero is the final non-zero elements.

If you can organize your elements into batches which can be updated at the same time, you win big. Then, I suggest that you use the function I described in the cited answer. A main obstacle in a batch approach would be if you need the current state of your array to be used for something, say matrix multiplication, in between single element updates. If this is not the case, I think you should be able to use the batch update method.

-
Most of zeros is exactly my situation - so, thanks, very useful tip. –  Vitaliy Kaurov Jan 27 '12 at 4:26
@Vitaliy Glad I could help. I've figured this out quite recently b.t.w., when having some similar problem. One probably could build a version of SparseArrays where binary search trees or hash tables would be used to store no-zero positions and elements, which would be better in this case. It would, however, be a lot of work tointegrate those as well into Mathematica as the current SparseArray-s are. –  Leonid Shifrin Jan 27 '12 at 9:09

I believe that Part works quite well.

sa = SparseArray[RandomInteger[{1, 10000}, {5000, 2}] -> 1];

new = RandomInteger[{1, 7000}, {5000, 3}];

(sa[[#, #2]] = #3) & @@@ new; // Timing

{0.078, Null}


Notice that this is being done one element at a time with @@@` and it is still very fast.

-
Thanks, neat example. –  Vitaliy Kaurov Jan 27 '12 at 4:36