[Haskell-cafe] Re: generalized shuffle

[Manlio Perillo]

oleg at okmij.org ha scritto:
> Hello!
> 
>>     The reason is that in a project I need to extract random elements
>>     from a list (and I need to extract a lot of them), and using "normal"
>>     methods [1] seems to be rather inefficient.

Note that I have used an incorrect term, sorry.
What I need, in detail, is to:
Given a population of 100480507 elements, extract 17770 random samples, 
where each sample has a size between 1 and 480189.

Yes, it is again my Netflix Prize project; here I'm trying to write a 
program to generate the entire training data set using random data.

>> [1] by normal method I mean: extract a random number, in the range
>>      [0, n] (where n is the length of the sequence), and get the element
>>      indexed by that number.
> 
> BTW, have you tried to use Data.IntMap? That is, put the sequence into
> an IntMap (each element being indexed by its index) and then extract
> elements at random; IntMap seems to be quite efficient...
> 

This should be ok if I need independent random choices from a 
population, but I need random samples, instead, sorry for the confusion.

Do you think that it is possible to further optimize your tree 
structure? Or to use IntMap, instead?

> 	Cheers,
> 	Oleg

Thanks   Manlio