Re: randomly choose some uniq elements of an array

<xhoster@xxxxxxxxx> wrote in comp.lang.perl.misc:
> Gunnar Hjalmarsson <noreply@xxxxxxxxx> wrote:
> > usenet@xxxxxxxxxxxxxxx wrote:
> >
> > Why do you think it makes sense to shuffle the whole array in order to
> > pick three elements?
>
> Probably for the same reason that you think it makes sense to splice the
> whole array (i.e. do a length-changing splice) in order to pick three
> elements.
>
> Both shuffle and length-changing splice are linear in the size of the
> array, although admittedly the multiplier for splice is lower than for
> shuffle. On the other hand, the shuffle only needs to be done once, while
> splice is done once for each element chosen.
>
> If one is really concerned about efficiency, then the below would be a good
> way to go. It uses a length-preserving splice, which is very fast compared
> to a length-changing splice:
>
> for (1..$k) {
> push @selected, splice(@files, rand @files, 1, $files[-1]);
> pop @files;
> }
>
> If one isn't really concerned about efficiency, then who cares that we are
> shuffling the entire array just to pick 3 elements?

True, arrays must be huge to make a difference.

However, your loop works just as well with a swapping technique, without
splice:

for ( 1 .. $k ) {
@files[ $_, -1] = @files[ -1, $_] for rand @files;
push @selected, pop @files;
}

It generates a different sequence, even with a seeded random generator,
but the sequence is just as random.

Anno
--
If you want to post a followup via groups.google.com, don't use
the broken "Reply" link at the bottom of the article. Click on
"show options" at the top of the article, then click on the
"Reply" at the bottom of the article headers.
.

Relevant Pages

  • Re: randomly choose some uniq elements of an array
    ... > Why do you think it makes sense to shuffle the whole array in order to ... Both shuffle and length-changing splice are linear in the size of the ... If one is really concerned about efficiency, then the below would be a good ...
    (comp.lang.perl.misc)
  • Re: "how to split a string in a random way"
    ... I created an integer array and I pass it along with a ... number to Factorize(). ... This time I send array1 through the Shuffle() method just prior to sending ... Dim array3 As Integer= Utility.GenArray ...
    (microsoft.public.dotnet.languages.vb)
  • Re: round-robin an arraylist
    ... Of all of them the work on the Array is the fastest. ... RemoveAt(), Addparadigm to do the shuffle is only slightly slower than the ... public class RoundRobin { ...
    (microsoft.public.dotnet.languages.csharp)
  • Re: Card dealing and random repetition
    ... inspiring for an 'elegant' way to simulate a shuffle. ... The dealer divide the deck in two parts, array ... left-half-deck (here there is a slight probability of 2 card staying ...
    (comp.programming)
  • Re: Best code for randomizing set of numbers
    ... that looks like a typical "shuffle" array. ... Dim pLoop As Integer, Maxx As Integer ...
    (comp.lang.basic.visual.misc)