What is the use case of RandomCover?

Ivan Kazmenko gassa at mail.ru
Tue Feb 19 13:52:44 PST 2013


Joseph Rushton Wakeling wrote:
> It's probably worth investigating the algorithms out there for 
> this kind of functionality, because I doubt the algorithm 
> that's given is optimal.

Given that the lazy version will hardly be possible without 
allocating O(n) additional memory anyway, the simple solution is:

- build a random permutation of iota(n) at start using 
randomShuffle (instead of maintaining the private bool[] _chosen 
array),
- lazily iterate the range according to the permutation.

It is n ints of memory instead of n bools which is comparable, 
but O(n) initialization and O(1) per step which is definitely 
better than now.


More information about the Digitalmars-d-learn mailing list