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$
3
  • $\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, 2019 at 0:53
  • $\begingroup$ @kickert RandomInteger does not produce the same results as RandomSample. $\endgroup$ Jul 16, 2019 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, 2019 at 11:16

2 Answers 2

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$
3
  • $\begingroup$ Interesting. The Spanform has been available since 10.3, and I've never noticed it. $\endgroup$
    – rcollyer
    Jul 16, 2019 at 1:16
  • $\begingroup$ Thank you very much. Became very helpful !! $\endgroup$
    – Milk
    Jul 16, 2019 at 1:47
  • $\begingroup$ @user21427 You're welcome! $\endgroup$ Jul 16, 2019 at 2:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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