Fast indexing - more than linear indexing

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]

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]

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

Answer 1

[Walter Roberson]

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.

[Matteo Cacciola]

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

Answer 2

[per isakson]

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.

[Matteo Cacciola]

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