# Random

Discussion in 'Perl Misc' started by Jacob JKW, Apr 12, 2006.

1. ### Jacob JKWGuest

find where.

Let's say I have a sorted array of real numbers between 0 and 1. What
do you think would be the fastest way of determining between which two
indexes a randomly generated number lay?

Specifically, what would be a faster way to do this:

#!perl

my \$cmf_ra = [0, 0.25, 0.33, 0.625, 0.9, 0.95];
my \$rand = rand();

foreach my \$i (0 .. \$#\$cmf_ra) {
(print \$i and last) if \$rand <= \$cmf_ra->[\$i];
}

Thanks,
Jacob

Jacob JKW, Apr 12, 2006

Jacob JKW wrote:
> find where.
>
> Let's say I have a sorted array of real numbers between 0 and 1. What
> do you think would be the fastest way of determining between which two
> indexes a randomly generated number lay?
>
> Specifically, what would be a faster way to do this:
>
> #!perl
>
> my \$cmf_ra = [0, 0.25, 0.33, 0.625, 0.9, 0.95];
> my \$rand = rand();
>
> foreach my \$i (0 .. \$#\$cmf_ra) {
> (print \$i and last) if \$rand <= \$cmf_ra->[\$i];
> }

binary search.

3. ### Guest

"Jacob JKW" <> wrote:
> find where.
>
> Let's say I have a sorted array of real numbers between 0 and 1. What
> do you think would be the fastest way of determining between which two
> indexes a randomly generated number lay?

The fastest way would be to do it in C. Don't forget to turn on the -O3
flag, it makes a huge difference in these cases. Also, put a sentinel
value at the end of the list so that you don't need to test two conditions
on each iteration.

>
> Specifically, what would be a faster way to do this:
>
> #!perl
>
> my \$cmf_ra = [0, 0.25, 0.33, 0.625, 0.9, 0.95];
> my \$rand = rand();
>
> foreach my \$i (0 .. \$#\$cmf_ra) {
> (print \$i and last) if \$rand <= \$cmf_ra->[\$i];
> }

Do you really have only 6 things in the search list?
I think a linear search would be faster than a binary search when you
only have 6 things in the search list.

Implement it both ways and see.

Xho

--
Usenet Newsgroup Service \$9.95/Month 30GB

, Apr 12, 2006
4. ### robic0Guest

On 12 Apr 2006 00:24:42 GMT, wrote:

>"Jacob JKW" <> wrote:
>> find where.
>>
>> Let's say I have a sorted array of real numbers between 0 and 1. What
>> do you think would be the fastest way of determining between which two
>> indexes a randomly generated number lay?

>
>The fastest way would be to do it in C. Don't forget to turn on the -O3
>flag, it makes a huge difference in these cases. Also, put a sentinel
>value at the end of the list so that you don't need to test two conditions
>on each iteration.
>
>>
>> Specifically, what would be a faster way to do this:
>>
>> #!perl
>>
>> my \$cmf_ra = [0, 0.25, 0.33, 0.625, 0.9, 0.95];
>> my \$rand = rand();
>>
>> foreach my \$i (0 .. \$#\$cmf_ra) {
>> (print \$i and last) if \$rand <= \$cmf_ra->[\$i];
>> }

>
>Do you really have only 6 things in the search list?
>I think a linear search would be faster than a binary search when you
>only have 6 things in the search list.
>

Yes you are right fag head, IF AND ONLY IF, the number of elements are
less than 5. Statististacalcallyy, this wins.
Yes binary search fag head. Look for my posts on binary search routine
optimizations.

robic0, Apr 12, 2006
5. ### robic0Guest

On 11 Apr 2006 17:00:26 -0700, "it_says_BALLS_on_your_forehead" <> wrote:

>
>Jacob JKW wrote:
>> find where.
>>
>> Let's say I have a sorted array of real numbers between 0 and 1. What
>> do you think would be the fastest way of determining between which two
>> indexes a randomly generated number lay?
>>
>> Specifically, what would be a faster way to do this:
>>
>> #!perl
>>
>> my \$cmf_ra = [0, 0.25, 0.33, 0.625, 0.9, 0.95];
>> my \$rand = rand();
>>
>> foreach my \$i (0 .. \$#\$cmf_ra) {
>> (print \$i and last) if \$rand <= \$cmf_ra->[\$i];
>> }

>
>binary search.

robic0, Apr 12, 2006
6. ### Jacob JKWGuest

wrote:
> "Jacob JKW" <> wrote:
> > find where.
> >
> > Let's say I have a sorted array of real numbers between 0 and 1. What
> > do you think would be the fastest way of determining between which two
> > indexes a randomly generated number lay?

>
> The fastest way would be to do it in C. Don't forget to turn on the -O3
> flag, it makes a huge difference in these cases.

I hear you, but I want to get this done somewhat quickly and I'm
unfortunately not really what you'd call a "strong" C programmer.

> Also, put a sentinel
> value at the end of the list so that you don't need to test two conditions
> on each iteration.

Yeah, I know. I just acciudently left that out of my code sample.

> > Specifically, what would be a faster way to do this:
> >
> > #!perl
> >
> > my \$cmf_ra = [0, 0.25, 0.33, 0.625, 0.9, 0.95];
> > my \$rand = rand();
> >
> > foreach my \$i (0 .. \$#\$cmf_ra) {
> > (print \$i and last) if \$rand <= \$cmf_ra->[\$i];
> > }

>
> Do you really have only 6 things in the search list?
> I think a linear search would be faster than a binary search when you
> only have 6 things in the search list.

I've got 18 items in the list.

I Google'd "binary search" and dound some sample code at
http://staff.washington.edu/jon/dsa-perl/bsearch. I'm to implement and
see how it compares.

Jacob.

Jacob JKW, Apr 12, 2006
7. ### robic0Guest

On 11 Apr 2006 17:51:56 -0700, "Jacob JKW" <> wrote:

> wrote:
>> "Jacob JKW" <> wrote:
>> > find where.
>> >
>> > Let's say I have a sorted array of real numbers between 0 and 1. What
>> > do you think would be the fastest way of determining between which two
>> > indexes a randomly generated number lay?

>>
>> The fastest way would be to do it in C. Don't forget to turn on the -O3
>> flag, it makes a huge difference in these cases.

>I hear you, but I want to get this done somewhat quickly and I'm
>unfortunately not really what you'd call a "strong" C programmer.
>
>> Also, put a sentinel
>> value at the end of the list so that you don't need to test two conditions
>> on each iteration.

>Yeah, I know. I just acciudently left that out of my code sample.
>
>> > Specifically, what would be a faster way to do this:
>> >
>> > #!perl
>> >
>> > my \$cmf_ra = [0, 0.25, 0.33, 0.625, 0.9, 0.95];
>> > my \$rand = rand();
>> >
>> > foreach my \$i (0 .. \$#\$cmf_ra) {
>> > (print \$i and last) if \$rand <= \$cmf_ra->[\$i];
>> > }

>>
>> Do you really have only 6 things in the search list?
>> I think a linear search would be faster than a binary search when you
>> only have 6 things in the search list.

>I've got 18 items in the list.
>
>I Google'd "binary search" and dound some sample code at
>http://staff.washington.edu/jon/dsa-perl/bsearch. I'm to implement and
>see how it compares.
>
>Jacob.

Well, I geuss your off to the races with your new found knowledge.
Good luck, have a nice day!!

robic0, Apr 12, 2006
8. ### Jacob JKWGuest

robic0 wrote:
> On 11 Apr 2006 17:51:56 -0700, "Jacob JKW" <> wrote:
>
> > wrote:
> >> "Jacob JKW" <> wrote:
> >> > find where.
> >> >
> >> > Let's say I have a sorted array of real numbers between 0 and 1. What
> >> > do you think would be the fastest way of determining between which two
> >> > indexes a randomly generated number lay?
> >>
> >> The fastest way would be to do it in C. Don't forget to turn on the -O3
> >> flag, it makes a huge difference in these cases.

> >I hear you, but I want to get this done somewhat quickly and I'm
> >unfortunately not really what you'd call a "strong" C programmer.
> >
> >> Also, put a sentinel
> >> value at the end of the list so that you don't need to test two conditions
> >> on each iteration.

> >Yeah, I know. I just acciudently left that out of my code sample.
> >
> >> > Specifically, what would be a faster way to do this:
> >> >
> >> > #!perl
> >> >
> >> > my \$cmf_ra = [0, 0.25, 0.33, 0.625, 0.9, 0.95];
> >> > my \$rand = rand();
> >> >
> >> > foreach my \$i (0 .. \$#\$cmf_ra) {
> >> > (print \$i and last) if \$rand <= \$cmf_ra->[\$i];
> >> > }
> >>
> >> Do you really have only 6 things in the search list?
> >> I think a linear search would be faster than a binary search when you
> >> only have 6 things in the search list.

> >I've got 18 items in the list.
> >
> >I Google'd "binary search" and dound some sample code at
> >http://staff.washington.edu/jon/dsa-perl/bsearch. I'm to implement and
> >see how it compares.
> >
> >Many thanks for the reply,
> >Jacob.

>
> Well, I geuss your off to the races with your new found knowledge.
> Good luck, have a nice day!!

If you have any constructive advice I'd love to hear it.

Jacob JKW, Apr 12, 2006