Take the 2-minute tour ×
Mathematica Stack Exchange is a question and answer site for users of Mathematica. It's 100% free, no registration required.

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.

share|improve this question
    
A simple A[[i, j]] = f[x] wouldn't suffice? –  J. M. 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
add comment

2 Answers

up vote 7 down vote accepted

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.

share|improve this answer
    
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
add comment

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.

share|improve this answer
    
Thanks, neat example. –  Vitaliy Kaurov Jan 27 '12 at 4:36
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.