is there an alternative to nchoosek which is too slow?

5 Ansichten (letzte 30 Tage)
Andy
Andy am 29 Jul. 2018
Bearbeitet: John D'Errico am 2 Jan. 2024
Try cnk = nchoosek(1:40, 10) and you'll see how slow it is. Is there an alternative?
Thanks

Akzeptierte Antwort

dpb
dpb am 29 Jul. 2018
Bearbeitet: dpb am 29 Jul. 2018
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 Kommentare
Walter Roberson
Walter Roberson am 2 Jan. 2024
The internal code of nchoosek() does not use a recursive function -- and the internal code of nchoosek() does pre-allocate
John D'Errico
John D'Errico am 2 Jan. 2024
Bearbeitet: John D'Errico am 2 Jan. 2024
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.

Melden Sie sich an, um zu kommentieren.

Weitere Antworten (0)

Kategorien

Mehr zu Programming finden Sie in Help Center und File Exchange

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by