Efficient by-element updates to SparseArrays

Question

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.

Answer 1

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.

Answer 2

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.