is there an alternative to nchoosek which is too slow?
4 次查看(过去 30 天)
显示 更早的评论
Try cnk = nchoosek(1:40, 10) and you'll see how slow it is. Is there an alternative?
Thanks
0 个评论
采纳的回答
dpb
2018-7-29
编辑:dpb
2018-7-29
Well, you're asking for 40!/(10! 30!) elements -->
>> N=prod(31:40)/factorial(10)
N =
847660528
>>
elements so it's not terribly surprising it might just take a while for the scribes to write 'em all down...
It boils down in the end to
function P = combs(v,m)
n=length(v);
P = [];
if m < n && m > 1
for k = 1:n-m+1
Q = combs(v(k+1:n),m-1);
P = [P; [v(ones(size(Q,1),1),k) Q]]; %#ok
end
end
end
which has a big problem in time in that P isn't preallocated.
ADDENDUM
Unfortunately, combnk has the same flaw using almost identically the same code.
Whether somebody has supplied mex file or other solution on FEX I didn't research.
7 个评论
Walter Roberson
2024-1-2
The internal code of nchoosek() does not use a recursive function -- and the internal code of nchoosek() does pre-allocate
John D'Errico
2024-1-2
编辑:John D'Errico
2024-1-2
It does not matter how fast you make nchoosek, if you were able to magically make nchoosek faster, perhaps using parfor, etc., then @Andy would want to generate
cnk = nchoosek(1:40, 11)
or something bigger yet.
Anyway, note that MOST people do not have access to the parallel computing toolbox. So TMW will not be allocating much programmer time to make the code faster for the few people who could make use of an acceleration tool. There are lots of things they want to allocate person-hours to than something that few can benefit from, especially since if they did, it would only give a benefit on a few rare cases.
John's rule of computing is something I have stated many times on Answers and previous forums. That is:
"Problems always expand to just a bit bigger than you can feasibly solve using any current computing hardware or algorithms."
The logic is simple, in that if you can solve it easily, then someone already has, and you need to solve a bigger, harder problem than anyone else, one that is not easy.
My response is always that if you are trying to use nchoosek like this, then you are trying to solve the problem the wrong way. You need to be using mathematics intelligently, not brute force. At the very least, you will need to use tools like optimization. Reformulate your problem so that it is solvable. Don't just bemoan the fact that the software is not fast enough to solve all problems using brute force.
更多回答(0 个)
另请参阅
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!