Fast indexing - more than linear indexing

Question

Matteo Cacciola 2012-6-23

0
链接

此问题的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/41886-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

2 个评论
显示无隐藏无

the cyclist 2012-6-23

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 2012-6-24

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 2012-6-24

1
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/41886-fast-indexing-more-than-linear-indexing#answer_51646

在 MATLAB Online 中打开

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 个评论
显示 -1更早的评论隐藏 -1更早的评论

Matteo Cacciola 2012-6-24

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

请先登录，再进行评论。

Answer 2

per isakson 2012-6-23

0
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/41886-fast-indexing-more-than-linear-indexing#answer_51582

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 个评论
显示 -1更早的评论隐藏 -1更早的评论

Matteo Cacciola 2012-6-24

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

请先登录，再进行评论。