6
$\begingroup$

I try to do a big simulation like below.

(However, I do not change the sizes I want to 10 ^ 5, 10 ^ 7, 10 ^ 9.)

n = RandomSample[all = Range[10^7], 2*10^5]; 
r = RandomChoice[all, 10^9];
Total@Table[Count[n, r[[i]]], {i, 1, Length[r]}]

However, the calculation takes too long.

How can I shorten the calculation time effectively?

$\endgroup$
  • $\begingroup$ RandomInteger seems to cut more than 50% of the time off of Range and RandomSample. It can also be used in place of RandomChoice if combined with Table. $\endgroup$ – kickert Jul 16 at 0:53
  • $\begingroup$ @kickert RandomInteger does not produce the same results as RandomSample. $\endgroup$ – Henrik Schumacher Jul 16 at 22:26
  • $\begingroup$ Got ahead of myself, I should have suggested it as a replacement for the RandomChoice on the full range. Thanks. $\endgroup$ – kickert Jul 17 at 11:16
9
$\begingroup$

Instead of building the long list r of random numbers, you could sample directly from the distribution of results: replace the third line of your code with

RandomVariate[BinomialDistribution[Length[r], Length[n]/Length[all]]]

to get a result instantaneously. Or is this cheating?

$\endgroup$
11
$\begingroup$

This should have the same effect and runs in about 7.6 seconds.

AbsoluteTiming[

 m = 10^7;
 l = 4;
 n = RandomSample[1 ;; m, 2 10^5];
 u = Normal[SparseArray[Partition[n, 1] -> 1, {m}]];
 sum = Total@ParallelTable[
    Total[u[[RandomChoice[1 ;; m, 10^l]]]],
    {10^(9 - l)},
    Method -> "CoarsestGrained"
    ]

 ]

The important points are:

  • Using RandomSample[1 ;; m, ...] and RandomChoice[1 ;; m, ...]. This allows us to handle also rather large m.

  • Conversion of the very expensive Count operation (which goes through the whole list n $10^9$ times!) into a simple read operation from the (packed!) array u.

  • Chopping the vector r into small pieces so that it never has to be stored in RAM; if I computed correctly, r would need more than 7 GB of RAM. Since the pseudorandom numbers in the array returned from RandomChoice are pairwise independent, we may just call RandomChoice[1 ;; m, 10^l] multiple times, do the counts and sum then up in the end with Total.

$\endgroup$
  • $\begingroup$ Interesting. The Spanform has been available since 10.3, and I've never noticed it. $\endgroup$ – rcollyer Jul 16 at 1:16
  • $\begingroup$ Thank you very much. Became very helpful !! $\endgroup$ – user21427 Jul 16 at 1:47
  • $\begingroup$ @user21427 You're welcome! $\endgroup$ – Henrik Schumacher Jul 16 at 2:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.