# Fast indexing - more than linear indexing

Asked by Matteo Cacciola on 23 Jun 2012
Latest activity Commented on by Matteo Cacciola on 24 Jun 2012

Hello all I am facing another problem. I have to manage with large arrays. I have a first array which length is 1 billion elements. Since the most part of elements are null, this array has been set as a sparse array. Inside of it, I selected 1 million of odd indices by means of randperm function. Now I have to place random elements belonging to [a, b] range inside of those 1 million elements. Here is a simple code

```large_array = sparse(1e9,1);
inds_array = randperm(odd_indices, 1e6); % odd_indices contain odd indices of large_array
rand_array = a + (b-a)*rand(1e6, 1);
large_array(inds_array) = rand_array;
```

Now, I am experiencing that, for such a kind of situation where large number of elements are involved, the linear indexing is too slow anyway. Do you have any suggestion to speed up the procedure, please?

Thanks Matteo

the cyclist on 23 Jun 2012

I do not understand the comment on the second line, about odd_indices. That input can't be a vector, right?

Is it possible for you to post complete code that we would be able to execute, instead of us guessing what you mean by odd_indices, a, and b?

Matteo Cacciola on 24 Jun 2012

Here I am posting the code. Please, pay attention to inds and num_div variables: in my case inds is a 1-by-1e6 array, while num_div=1001
Here follow the code of my script

len_pos = length(inds);
min_theta = 0; max_theta = 2*pi;
rng('shuffle');
thetas = sparse(num_div^3, 1);
num_half_indices = floor(len_pos/2);
ind_temp = num_half_indices - mod(len_pos, 2);
% thetas = full(thetas);
temp_rand = min_theta + (max_theta - min_theta)*rand(ind_temp, 1);
% I already tested step-by-step the previous code, and it is not slow
% I already tested the code with thetas = full(thetas) before going on, but
% it is still too slow
% so the very slow code is below
thetas(inds(1:ind_temp)) = temp_rand;
thetas(inds(num_half_indices+1:len_pos-2*mod(len_pos,2))) = mod(temp_rand + pi, 2*pi);

Thanks

## Products

No products are associated with this question.

Answer by Walter Roberson on 24 Jun 2012

If the indexing is slow, do fewer indexing operations:

```tinds = [inds(1:ind_temp), inds(num_half_indices+1:len_pos-2*mod(len_pos,2))];
tvals = [temp_rand, mod(temp_rand + pi, 2*pi)];
thetas(tinds) = tvals;
```

And if the two index ranges can overlap, then work that out so that you only do the unique indices.

Once you have it down to a single assignment call, combine creation of the sparse matrix with setting the values

```thetas = sparse(tinds, 1, tvals, num_div^3, 1);
```

I have read that this is much faster than setting the values after the matrix is created.

## 1 Comment

Matteo Cacciola on 24 Jun 2012

Dear Walter, thanks a lot for your answer. My code becomes incredibly faster after applying your suggestions. Thanks again

Answer by per isakson on 23 Jun 2012

Based on the use in RANDPERM, I assume odd_indices is a scalar integer.

PROFILE indicates that "all" time is spent in the last statement. I would say that the performance problem is with SPARSE rather than with linear indexing. The value of "1e6" is critical to the performance.

If memory allows the performance with a full matrix is much better.

--- Cont. ---

Have you analyzed the code with PROFILE?

Yes, it is the assignments of the sparse vector, thetas, that takes all the time.

How much faster execution do you need?

You say that the improvement, which is possible with a full matrix is not enough. I don't think it is possible achieve the performance you need by improvements on this code. One need to use another approach or another language.

## 1 Comment

Matteo Cacciola on 24 Jun 2012

I already tested also with full matrix. But it is still too slow. I added the whole code I have. I hope it should be more clear than my previous explanation