Re: random array elements and speed

"JJ" == Jacob JKW <jacobcdf@xxxxxxxxx> writes:

JJ> Uri Guttman wrote:
>> >>>>> "JJ" == Jacob JKW <jacobcdf@xxxxxxxxx> writes:
>>
JJ> Hmm, I suppose the fact that both you and Uri gave rather similar
JJ> responses should suggest that the two of you are likely on to
JJ> something. I'm just uncomfortable using a method that is so
JJ> incredibly sensitive to the size of the desired array. I know I
JJ> specically mentioned that said array would be small in relation to
JJ> the master array, but I just hate to thionk that speed would decay
JJ> exponentially if on a few particular iterations that condition
JJ> breaks down. My fault.
>> so do what someone else said, track the omitted entries. and you can do
>> other things to make it more deterministic. try handling 'collisions'
>> the same way some hash method do it, scan sequentially from the
>> collision spot until you find a unique index.
JJ> An interesting notion but I don't think that that would work. Remember
JJ> that each element is supposed to be randomly selected. If I were to
JJ> simply scan sequentially from the point of collision, then obviously my
JJ> results would be biased towards those elements immediately succeeding
JJ> earlier picks.

you can come up with another collision mechanism then. some combination
of retries and scanning may work.

JJ> I honestly don't think I could sleep at night if I used the random
JJ> slots method. The way at look at it is that if at some point my data
JJ> changes and I'm picking a larger percentage of the initial elements
JJ> then yeah the splice method might well be two or three or four times as
JJ> slow as fisher-yates. But the random selection method could be a
JJ> thousand times slower. And yes, I freely admit that's rather neurotic.

so go with the swap of last and picked elements and pop. splice is never
the way to go as it will have to move half the list on average for each
pick. swapping and pop will blow that away for large lists.

JJ> I think I've come up with a solution. It might not be the best solution
JJ> but it's certainly much faster than my original copy and splice. Even
JJ> more importantly it's going to let me sleep at night. Anyway, here's
JJ> what how I've changed it:

JJ> my $array_ra = [(qw(1 2 3 4 5 6 7 8 9 10 11 12 13)) x 16];
JJ> my $discards_ra = [];

JJ> for (1 .. 100_000) {
JJ> for (1 .. 10) {
JJ> # select 10 random elements from the array
JJ> # in reality all that is known anoout the actual number of
JJ> # elemnts is that
JJ> # the number is small relative to the size of the array
JJ> &get_ele( $array_ra );

JJ> # do stuff -- possibly break out of the loop, possibly even run
JJ> &get_ele a few more time
JJ> }
JJ> push @$array_ra, @$discards_ra;
JJ> @$discards_ra = [];

that line doesn't do what you think it does.

JJ> }

JJ> sub get_ele {
JJ> my $ar = shift;

JJ> # get generate random element from array and modify array in place
JJ> my $ele = splice @{$ar}, rand( @{$ar} ), 1 ; # thank you Uri

JJ> # save element for later
JJ> push @$DISCARDS_ar, $ele;

JJ> # return selected element
JJ> return $ele;
JJ> }

that is not going to be much faster than your original code. you still
call the inner sub too often (you can pass in a count and then call it
more if you want).

case matters $DISCARDS_ar vs $discards_ra

and swap/pop should be faster than splice as i said. i am not sure why
you think it is not. can you show a benchmark proving that?

as for sleeping, take some ambien!

uri

--
Uri Guttman ------ uri@xxxxxxxxxxxxxxx -------- http://www.stemsystems.com
--Perl Consulting, Stem Development, Systems Architecture, Design and Coding-
Search or Offer Perl Jobs ---------------------------- http://jobs.perl.org
.

Relevant Pages

  • Re: popping, shifting or splicing an array???
    ... > I am trying to figure out, which operator to use; pop, shift or splice. ... > shift elements off and repopulate array ... but by removing the first element. ...
    (perl.beginners)
  • Re: popping, shifting or splicing an array???
    ... > I am trying to figure out, which operator to use; pop, shift or splice. ... > shift elements off (those selected from user input) and repopulate ... "If any part of LIST is an array, foreach will get very confused if ...
    (perl.beginners)
  • Re: Insert Multiple Lines after a Specified Line -- Please Help!
    ... ap> I am new to PERL I am trying to automate ... ap> some file manipulation techniques. ... splice in new lines with perl's normal array stuff. ...
    (comp.lang.perl.misc)
  • Re: random array elements and speed
    ... JJ> then yeah the splice method might well be two or three or four times as ... JJ> sub get_ele { ... JJ> # get generate random element from array and modify array in place ... can you show a benchmark proving that? ...
    (comp.lang.perl.misc)
  • Re: random numbers
    ... don't want to check after each grab whether I've previously pulled the ... I'll store the numbers in an array. ... that's not really a random selection; ...
    (microsoft.public.access.modulesdaovba)