Picking random elements

[Luc Hogie]

Dear Fastutil author,

Would it be possible to add in sets an efficient pickRandomElement(Random) method?

Thanks,
Luc.

[Sebastiano Vigna]

> On 23 Nov 2017, at 11:40, Luc Hogie <luc....@gmail.com> wrote:
>
> Dear Fastutil author,
>
> Would it be possible to add in sets an efficient pickRandomElement(Random) method?
>

Well, you can subclass the set you're interested in. Just jump randomly in the middle of the backing array and look for a nonzero (in a circular way). If you have also zeros in the set you have to handle that case separately by tossing a 1/size-biased coin (if it turns head, you return 0).

I'm assuming you're talking about hash-based sets. I see no easy way to do it on trees, and it's totally trivial in array-based sets.

Ciao,

seba

[Luc Hogie]

Thank you Seba. If the backing array is visible to the subclasses, your solution is workable.

[Alex Fiennes]

--
You received this message because you are subscribed to the Google Groups "fastutil" group.
To unsubscribe from this group and stop receiving emails from it, send an email to fastutil+unsubscribe@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.