# How can I shorten the calculation time effectively?

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?

• 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. Jul 16, 2019 at 0:53
• @kickert RandomInteger does not produce the same results as RandomSample. Jul 16, 2019 at 22:26
• Got ahead of myself, I should have suggested it as a replacement for the RandomChoice on the full range. Thanks. Jul 17, 2019 at 11:16

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?

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.

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