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