Re: random array elements and speed

"Jacob JKW" <jacobcdf@xxxxxxxxx> wrote:
Uri Guttman wrote:

so the lower sub could look like this (untested):

sub get_unique_rand_elements {

my( $aref, $count ) = @_ ;

my %seen ;
my @indices ;

# get the size here so we don't deref in the loop

my $asize = @{$aref} ;

while( $count > 0 ) {

# need int here since we are checking for dups and floats won't work

my $ind = int rand $asize ;

next if $seen{ $ind } ;

$seen{ $ind } = 1 ;
push @indices, $ind ;

$count-- ;
}

return @{$aref}{@indices} ;
}

i would be very surprised if that isn't much faster than your
version. no copying, no splicing, fewer calls, etc.
No doubt it would be.

However, I would actually need to maintain %seen outside the array, in
case I were to need more elements than those in the returned array.

Doesn't it return the number of elements you asked for? If so, why would
you ask for a number that is less than the number you need?

Also, I'm a little uncomfortable with the concept of running a process
that could theoretiocally never terminate.

There is only one reality, but the nice thing about theories is that
you can pick and choose them. So pick a theory that includes things like
gamma rays from space randomly flipping a register somewhere throwing your
program execution into complete chaos. Now, *every* processes can
theoretically never terminate. So get over that hang up, and then get on
with life :)

I know I initially posited
the problem by saying that I'd only need a small number of elemnts from
the original array, but small's a relative term and the expected speed
degredation I believe would be exponential as the number of required
elemnts increased.

I'm pretty sure it wouldn't be exponential. But in any case, if the number
desired is more than the half of the original size, then select elements
to be omitted rather than to be kept.

Xho

--
-------------------- http://NewsReader.Com/ --------------------
Usenet Newsgroup Service $9.95/Month 30GB
.

Relevant Pages

  • Re: an implementation of insertion sort, insert without move element
    ... The process of sort is the process of building array next. ... we assume that the element type is int. ... and then use that array to rewrite the original array. ...
    (comp.lang.c)
  • Re: can this code be improved
    ... // the original array of 6 numbers picked ... // the new array containing unique numbers only ... int[] newList) { ...
    (comp.lang.java.programmer)
  • (patch for Bash) regex case statement
    ... Following up on my previous patch for regex conditional tests, ... /* Return an array of strings; ... int dollarflag, zeropad, compareflag; ... SHELL_VAR *var; ...
    (comp.unix.shell)
  • Re: Strategy or Iterator?
    ... It would be possible to write a class that returns the variations ... GNU General Public License for more details. ... protected CombinatoricOperator(Telements, int r) { ... An integer array backing up the original one to keep track of the ...
    (comp.lang.java.programmer)
  • (patch for Bash) regex conditional tests
    ... 'regex' are returned in array variable SUBMATCH. ... Skipping of positional parameters, array elements, string ... int dollarflag, zeropad, compareflag; ... SHELL_VAR *var; ...
    (comp.unix.shell)