Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Welcome To Ask or Share your Answers For Others

Categories

0 votes
1.8k views
in Technique[技术] by (71.8m points)

performance - Fastest solution to list all pairs of n integers?

I want to list all possible pairs of the integers [1, n] with a large n. I find myself looking for the fastest option. This is what I've come up with so far.

Matlab's nchoosek and combnk methods recommend n<15 for listing all possible combinations because of the explosive number of combinations. So how fast this is depends on the n.

pair = nchoosek(1:n, 2);

Another option would be to use a nested for loop

kk =1;
pair = zeros(nchoosek(n, 2), 2);
for ii = 1:n
    for jj = ii+1:n
        pair(kk, :) = [ii, jj];
        kk = kk + 1;
    end
end  

This would be relatively slow.

I also thought of using the ind2sub function directly

pair_adjacency = tril(ones(n),  -1);
[x, y] = ind2sub(size(pair_adjacency), find(pair_adjacency==1)); 
pair = [x, y];

Timing these methods in a loop, 10 times each with n=1000, I get fastest to slowest

  1. ind2sub (0.15 sec)
  2. for loop (16.3 sec)
  3. nchoosek (16.8 sec)

It seems like ind2sub is the fastest way to go by a long shot. Just out of curiosity, what are other options that may or may not be faster?

See Question&Answers more detail:os

与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
Welcome To Ask or Share your Answers For Others

1 Reply

0 votes
by (71.8m points)

To replace nchoosek(1:N,2)

With bsxfun -

[Y,X] = find(bsxfun(@gt,[1:N]',[1:N]))
pair = [X, Y];

With tril and find only (without ind2sub) -

[y,x] = find(tril(true(N),-1))
pair = [X, Y];

与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
OGeek|极客中国-欢迎来到极客的世界,一个免费开放的程序员编程交流平台!开放,进步,分享!让技术改变生活,让极客改变未来! Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Click Here to Ask a Question

...