Lookup-scheme for potentially large n choose k matrices

조회 수: 3 (최근 30일)
Ulrik William Nash
Ulrik William Nash 2019년 12월 10일
댓글: Rik 2019년 12월 10일
I am writing a simulation that includes the variables n and k. These variable serves a part in numerous "n choose k" calculations. Since these caluclations are often identical in my simulation, and since n and k can be large (sometimes n > 20), I want to implement a scheme whereby the "n choose k" calculations are pre-computed and stored for lookup.
More specifically, k is not constant throughout my simulation. Within a simulation it can, for example, change from 5 to 4, to 6, to another number. Now, I want to avoid adding IF conditions for every value if n and k but I am unsure about the best-practice for creating a look-up scheme in my situation. To be sure, what must be looked-up are the "n choose k" matrixes, and not simply the binomial coefficients.
How might the described scheme be implemented?

답변 (1개)

Rik
Rik 2019년 12월 10일
편집: Rik 2019년 12월 10일
If the citeria below are satisfied, you can use memoize:
  • Performance is important.
  • The function is time consuming.
  • The function has return values that are determined entirely by the input values, and has no side effects.
  • System memory is adequate to store unique input and output combinations.
The last requirement is probably not true in your case, so you need to find a way to store the matrices on disk.
You could store it in a mat file that you would load partially, but I think a cleaner solution would be to use a preference group, so getpref and setpref. Note that this is a slow method for smaller sizes of n and k, because it loads data from the disk. You can probably improve on this by determining values where it is faster to memoize or generate on the fly, and values where loading from disk may be faster.
function mat=load_nchoosek(n,k)
%load nchoosek matrix
%n must be a scalar, which is expanded to 1:n
prefname=sprintf('n_%d_k_%d',n,k);
if ispref('load_nchoosek',prefname)
%load matrix
mat=getpref('load_nchoosek',prefname);
else
%create and store to disk
mat=nchoosek(1:n,k);
setpref('load_nchoosek',prefname,mat)
end
end
If you no longer have any use for this function (or if disk space becomes an issue), you can remove the entire preference group all at once:
rmpref('load_nchoosek')
  댓글 수: 2
Walter Roberson
Walter Roberson 2019년 12월 10일
20!6 is only 38760 entries, so storing it in memory is probably feasible, especially if you can manage to fit the entries into uint8.
Rik
Rik 2019년 12월 10일
I did some further testing, and it turns out I was trying to be cleverer than Mathworks. When I try n=30;k=20; I get the following warning (R2019b,Windows10):
Warning: Variable 'Preferences' was not saved. For variables larger than 2GB use MAT-file version 7.3 or later.
I was unable to find this limitation in the documentation (nor is there any reference in the release notes).

댓글을 달려면 로그인하십시오.

카테고리

Help CenterFile Exchange에서 Performance and Memory에 대해 자세히 알아보기

Community Treasure Hunt

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

Start Hunting!

Translated by