please help optimize sub

Hello,

Are there ways to have this execute faster using hashes or map functions?
Any ideas on optimizing the following subroutine would be greatly appreciated.

Thanks
============================================================ ============
sub optimizeMePlease
{
my $input = $_[0];
my $return;
my @array = (
1.6931595338935, 5.07947860168049, 8.46579766946749,
11.8521167372545, 15.2384358050415, 18.6247548728285,
22.0110739406155, 25.3973930084025, 28.7837120761895,
32.1700311439765, 35.5563502117635, 38.9426692795505,
42.3289883473375, 45.7153074151245, 49.1016264829115,
52.4879455506985, 55.8742646184855, 59.2605836862725,
62.6469027540595, 66.0332218218465, 69.4195408896335,
72.8058599574205, 76.1921790252075, 79.5784980929945,
82.9648171607815, 86.3511362285685, 89.7374552963554,
93.1237743641424, 96.5100934319294, 100,
);

if ($input <= $array[0]) {
$return = 29;
}
else {
my $from = 1;
foreach my $to (10, 20, 29) {
if ($input <= $array[$to]) {
foreach my $index ($from..$to) {
if ($input <= $array[$index]) {
$return = $index;
last;
}
}
last;
}
$from += 10;
}
}
unless ($return) {
warn "Invalid input value: [$input]\nUsing default!$!";
$return = 29;
}
return ($return);
}

Re: please help optimize sub

QoS@domain.invalid wrote in news:T9yRi.15082$fm1.8984@trnddc01:

> sub optimizeMePlease
> {
> my $input = $_[0];
> my $return;
> my @array = (
> 1.6931595338935, 5.07947860168049, 8.46579766946749,
> 11.8521167372545, 15.2384358050415, 18.6247548728285,
> 22.0110739406155, 25.3973930084025, 28.7837120761895,
> 32.1700311439765, 35.5563502117635, 38.9426692795505,
> 42.3289883473375, 45.7153074151245, 49.1016264829115,
> 52.4879455506985, 55.8742646184855, 59.2605836862725,
> 62.6469027540595, 66.0332218218465, 69.4195408896335,
> 72.8058599574205, 76.1921790252075, 79.5784980929945,
> 82.9648171607815, 86.3511362285685, 89.7374552963554,
> 93.1237743641424, 96.5100934319294, 100,
> );

....

I first moved the definition of @array outside of the subroutine. That
resulted in a speed-up of about 55% on my system.

Sinan

--
A. Sinan Unur <1usa@llenroc.ude.invalid>
(remove .invalid and reverse each component for email address)
clpmisc guidelines:

Re: please help optimize sub

QoS@domain.invalid writes:

> Are there ways to have this execute faster using hashes or map functions?
> Any ideas on optimizing the following subroutine would be greatly appreciated.

Somehow, this has the reek of homework ...

> ============================================================ ============
> sub optimizeMePlease
> {
> my $input = $_[0];
> my $return;
> my @array = (
> 1.6931595338935, 5.07947860168049, 8.46579766946749,
> 11.8521167372545, 15.2384358050415, 18.6247548728285,
> 22.0110739406155, 25.3973930084025, 28.7837120761895,
> 32.1700311439765, 35.5563502117635, 38.9426692795505,
> 42.3289883473375, 45.7153074151245, 49.1016264829115,
> 52.4879455506985, 55.8742646184855, 59.2605836862725,
> 62.6469027540595, 66.0332218218465, 69.4195408896335,
> 72.8058599574205, 76.1921790252075, 79.5784980929945,
> 82.9648171607815, 86.3511362285685, 89.7374552963554,
> 93.1237743641424, 96.5100934319294, 100,
> );
>
> if ($input <= $array[0]) {
> $return = 29;
> }
> else {
> my $from = 1;
> foreach my $to (10, 20, 29) {
> if ($input <= $array[$to]) {
> foreach my $index ($from..$to) {
> if ($input <= $array[$index]) {
> $return = $index;
> last;
> }
> }
> last;
> }
> $from += 10;
> }
> }
> unless ($return) {
> warn "Invalid input value: [$input]\nUsing default!$!";
> $return = 29;
> }
> return ($return);
> }

This is not 100% exact, and you will need to check the special cases
( < $array[0], > $array[29]), but from the data I would assume that

int (($input - 1,6931595338935) / 3,38631906778700)

is what you are actually looking for ...

Regards,
Jan

Re: please help optimize sub

Jan Pluntke wrote in message-id:

>
> QoS@domain.invalid writes:
>
> > Are there ways to have this execute faster using hashes or map functions?
> > Any ideas on optimizing the following subroutine would be greatly appreciated.
>
> Somehow, this has the reek of homework ...

Not homework, just trying to update a old script; the entire program can be
found on CPAN here:
http://www.cpan.org/authors/id/Q/QO/QOS/Accessories/LPCal_v1 _1.plx

The sub is called 'assign image'.

>
> > ============================================================ ===========> sub optimizeMePlease
> > {
> > my $input = $_[0];
> > my $return;
> > my @array = (
> > 1.6931595338935, 5.07947860168049, 8.46579766946749,
> > 11.8521167372545, 15.2384358050415, 18.6247548728285,
> > 22.0110739406155, 25.3973930084025, 28.7837120761895,
> > 32.1700311439765, 35.5563502117635, 38.9426692795505,
> > 42.3289883473375, 45.7153074151245, 49.1016264829115,
> > 52.4879455506985, 55.8742646184855, 59.2605836862725,
> > 62.6469027540595, 66.0332218218465, 69.4195408896335,
> > 72.8058599574205, 76.1921790252075, 79.5784980929945,
> > 82.9648171607815, 86.3511362285685, 89.7374552963554,
> > 93.1237743641424, 96.5100934319294, 100,
> > );
> >
> > if ($input <= $array[0]) {
> > $return = 29;
> > }
> > else {
> > my $from = 1;
> > foreach my $to (10, 20, 29) {
> > if ($input <= $array[$to]) {
> > foreach my $index ($from..$to) {
> > if ($input <= $array[$index]) {
> > $return = $index;
> > last;
> > }
> > }
> > last;
> > }
> > $from += 10;
> > }
> > }
> > unless ($return) {
> > warn "Invalid input value: [$input]\nUsing default!$!";
> > $return = 29;
> > }
> > return ($return);
> > }
>
> This is not 100% exact, and you will need to check the special cases
> ( < $array[0], > $array[29]), but from the data I would assume that
>
> int (($input - 1,6931595338935) / 3,38631906778700)

Hmm interesting, I will test this.

>
> is what you are actually looking for ...
>
> Regards,
> Jan

Thank you very much for your attention.

Re: please help optimize sub

"A. Sinan Unur" <1usa@llenroc.ude.invalid> wrote in message-id:

>
> QoS@domain.invalid wrote in news:T9yRi.15082$fm1.8984@trnddc01:
>
> > sub optimizeMePlease
> > {
> > my $input = $_[0];
> > my $return;
> > my @array = (
> > 1.6931595338935, 5.07947860168049, 8.46579766946749,
> > 11.8521167372545, 15.2384358050415, 18.6247548728285,
> > 22.0110739406155, 25.3973930084025, 28.7837120761895,
> > 32.1700311439765, 35.5563502117635, 38.9426692795505,
> > 42.3289883473375, 45.7153074151245, 49.1016264829115,
> > 52.4879455506985, 55.8742646184855, 59.2605836862725,
> > 62.6469027540595, 66.0332218218465, 69.4195408896335,
> > 72.8058599574205, 76.1921790252075, 79.5784980929945,
> > 82.9648171607815, 86.3511362285685, 89.7374552963554,
> > 93.1237743641424, 96.5100934319294, 100,
> > );
>
> ...
>
> I first moved the definition of @array outside of the subroutine. That
> resulted in a speed-up of about 55% on my system.
>
> Sinan
>
> --
> A. Sinan Unur <1usa@llenroc.ude.invalid>
> (remove .invalid and reverse each component for email address)
> clpmisc guidelines:

Ah yes of course, the loading of the array must be alot of work, a tradoff
then.. memory for speed. Thank you for your attention.

Re: please help optimize sub

QoS@domain.invalid wrote:
> "A. Sinan Unur" <1usa@llenroc.ude.invalid> wrote in message-id:
>
>
> >
> > QoS@domain.invalid wrote in news:T9yRi.15082$fm1.8984@trnddc01:
> >
> > > sub optimizeMePlease
> > > {
> > > my $input = $_[0];
> > > my $return;
> > > my @array = (
> > > 1.6931595338935, 5.07947860168049, 8.46579766946749,
> > > 11.8521167372545, 15.2384358050415, 18.6247548728285,
> > > 22.0110739406155, 25.3973930084025, 28.7837120761895,
> > > 32.1700311439765, 35.5563502117635, 38.9426692795505,
> > > 42.3289883473375, 45.7153074151245, 49.1016264829115,
> > > 52.4879455506985, 55.8742646184855, 59.2605836862725,
> > > 62.6469027540595, 66.0332218218465, 69.4195408896335,
> > > 72.8058599574205, 76.1921790252075, 79.5784980929945,
> > > 82.9648171607815, 86.3511362285685, 89.7374552963554,
> > > 93.1237743641424, 96.5100934319294, 100,
> > > );
> >
> > ...
> >
> > I first moved the definition of @array outside of the subroutine. That
> > resulted in a speed-up of about 55% on my system.
> >
> > Sinan
> >
>
> Ah yes of course, the loading of the array must be alot of work, a
> tradoff then.. memory for speed. Thank you for your attention.

Not even that. Not only is it faster, but it should use less memory, too
(Although it is hard to see that that could matter). With it in the sub,
the data has to be stored someplace as a static data, and then has to be
copied someplace else at each run, to that is two copies of it.

Xho

--
-------------------- http://NewsReader.Com/ --------------------
The costs of publication of this article were defrayed in part by the
payment of page charges. This article must therefore be hereby marked
advertisement in accordance with 18 U.S.C. Section 1734 solely to indicate
this fact.

Re: please help optimize sub

QoS@domain.invalid wrote:
> Hello,
>
> Are there ways to have this execute faster using hashes or map functions?
> Any ideas on optimizing the following subroutine would be greatly
> appreciated.

As has been said already, move the array assignment out of the sub.

After that, the obvious optimization would be a binary search, but
with only 30 things to search through I wouldn't expect much of an
improvement.

Xho

--
-------------------- http://NewsReader.Com/ --------------------
The costs of publication of this article were defrayed in part by the
payment of page charges. This article must therefore be hereby marked
advertisement in accordance with 18 U.S.C. Section 1734 solely to indicate
this fact.

Re: please help optimize sub

Jan Pluntke wrote in
news:u8x6097jj.fsf@ID-18539.user.dfncis.de:

> QoS@domain.invalid writes:
>
>> Are there ways to have this execute faster using hashes or map
>> functions? Any ideas on optimizing the following subroutine would be
>> greatly appreciated.
>
> Somehow, this has the reek of homework ...
>
>> ============================================================ ==========
>> == sub optimizeMePlease
>> {
>> my $input = $_[0];
>> my $return;
>> my @array = (
>> 1.6931595338935, 5.07947860168049, 8.46579766946749,
>> 11.8521167372545, 15.2384358050415, 18.6247548728285,
>> 22.0110739406155, 25.3973930084025, 28.7837120761895,
>> 32.1700311439765, 35.5563502117635, 38.9426692795505,
>> 42.3289883473375, 45.7153074151245, 49.1016264829115,
>> 52.4879455506985, 55.8742646184855, 59.2605836862725,
>> 62.6469027540595, 66.0332218218465, 69.4195408896335,
>> 72.8058599574205, 76.1921790252075, 79.5784980929945,
>> 82.9648171607815, 86.3511362285685, 89.7374552963554,
>> 93.1237743641424, 96.5100934319294, 100,
>> );
....

> This is not 100% exact, and you will need to check the special cases
> ( < $array[0], > $array[29]), but from the data I would assume that
>
> int (($input - 1,6931595338935) / 3,38631906778700)
>
> is what you are actually looking for ...

In my testing, there were issues with truncation. So, I tried the
following:

#!/usr/bin/perl

use strict;
use warnings;

use File::Slurp;
use constant REPS => 1_000_000;

my @results;
$results[ REPS - 1 ] = 0;

my @array = (
1.6931595338935, 5.07947860168049, 8.46579766946749,
11.8521167372545, 15.2384358050415, 18.6247548728285,
22.0110739406155, 25.3973930084025, 28.7837120761895,
32.1700311439765, 35.5563502117635, 38.9426692795505,
42.3289883473375, 45.7153074151245, 49.1016264829115,
52.4879455506985, 55.8742646184855, 59.2605836862725,
62.6469027540595, 66.0332218218465, 69.4195408896335,
72.8058599574205, 76.1921790252075, 79.5784980929945,
82.9648171607815, 86.3511362285685, 89.7374552963554,
93.1237743641424, 96.5100934319294, 100,
);

srand( 0xdeadbeef );

for my $t ( 0 .. REPS - 1 ) {
$results[$t] = optimizeMePlease( rand 100 );
}

write_file( oo3_results => [ map { "$_\n" } @results ] );

sub optimizeMePlease {
my $input = $_[0];

return 29 if $input <= $array[0];

if ( $input <= $array[-1] ) {
my $i = int( ($input - 1.6931595338935) / 3.38631906778700 );
my $j = ($i < 29 ? $i + 1 : $i );
return $j if $input <= $array[$j];
return $i;
}
else {
warn "Invalid input value: [$input]. Using default!";
return 29;
}
}

__END__

Running times were 20.2 seconds for the original version versus 11.7
seconds for the version above.

The version with just the array moved out of the sub ran in 14.2 seconds.

After replacing the sub with

sub optimizeMePlease { return 1 }

as a control, the script ran in 9 seconds.

I guess one could thus say the version above represents a speed-up of about
75%.

This is on Windows XP SP2, AS Perl 5.8.8.822, Intel Dual Core.

Before someone tells me, yes, I know, I should have used Benchmark (and the
OP should to assess the results on his platform).

Sinan

--
A. Sinan Unur <1usa@llenroc.ude.invalid>
(remove .invalid and reverse each component for email address)
clpmisc guidelines:

Re: please help optimize sub

"A. Sinan Unur" <1usa@llenroc.ude.invalid> wrote:
....
>
> Running times were 20.2 seconds for the original version versus 11.7
> seconds for the version above.
>
> The version with just the array moved out of the sub ran in 14.2 seconds.
>
> After replacing the sub with
>
> sub optimizeMePlease { return 1 }
>
> as a control, the script ran in 9 seconds.
>
> I guess one could thus say the version above represents a speed-up of
> about 75%.
>
> This is on Windows XP SP2, AS Perl 5.8.8.822, Intel Dual Core.
>
> Before someone tells me, yes, I know, I should have used Benchmark

I disagree. You should have done just what you did do. Using Benchmark
doesn't make it easy (and indeed makes it hard) to verify that the various
things being tested actually produce the correct (or at least mutually
the same) answer. It seems like half the time I see people using
Benchmark, at least one of the implementations benchmarked doesn't give the
right answer but they never test for that. And I trust the times given by
the OS tools like "time" at least as much as I do the Benchmark ones,
anyway. About the only times I use Benchmark are when I'm tinkering with
someone else's code which is already all harnessed up with it, or when the
thing I want to test the timing requires a lot of set-up which set-up takes
more time than the thing to be tested does.

Xho

--
-------------------- http://NewsReader.Com/ --------------------
The costs of publication of this article were defrayed in part by the
payment of page charges. This article must therefore be hereby marked
advertisement in accordance with 18 U.S.C. Section 1734 solely to indicate
this fact.

Re: please help optimize sub

xhoster@gmail.com wrote in news:20071018224003.622$XX@newsreader.com:

> "A. Sinan Unur" <1usa@llenroc.ude.invalid> wrote:
> ...
....

>>
>> Before someone tells me, yes, I know, I should have used Benchmark
>
> I disagree. You should have done just what you did do. Using
> Benchmark doesn't make it easy (and indeed makes it hard) to verify
> that the various things being tested actually produce the correct (or
> at least mutually the same) answer. It seems like half the time I see
> people using Benchmark, at least one of the implementations
> benchmarked doesn't give the right answer but they never test for
> that. And I trust the times given by the OS tools like "time" at
> least as much as I do the Benchmark ones, anyway.

Well, I am glad that you read between the lines and deduced why I set up
separate scripts. Now that I am reasonably certain the optimized routine
returns the same results as the original, it might be worthwhile to set
up a script using Benchmark to be able to compare speeds on different
platforms as it becomes necessary but I am going to leave that to the
OP.

Sinan


--
A. Sinan Unur <1usa@llenroc.ude.invalid>
(remove .invalid and reverse each component for email address)
clpmisc guidelines:

Re: please help optimize sub

"A. Sinan Unur" <1usa@llenroc.ude.invalid> wrote in message-id:

>
> xhoster@gmail.com wrote in news:20071018224003.622$XX@newsreader.com:
>
> > "A. Sinan Unur" <1usa@llenroc.ude.invalid> wrote:
> > ...
> ...
>
> >>
> >> Before someone tells me, yes, I know, I should have used Benchmark
> >
> > I disagree. You should have done just what you did do. Using
> > Benchmark doesn't make it easy (and indeed makes it hard) to verify
> > that the various things being tested actually produce the correct (or
> > at least mutually the same) answer. It seems like half the time I see
> > people using Benchmark, at least one of the implementations
> > benchmarked doesn't give the right answer but they never test for
> > that. And I trust the times given by the OS tools like "time" at
> > least as much as I do the Benchmark ones, anyway.
>
> Well, I am glad that you read between the lines and deduced why I set up
> separate scripts. Now that I am reasonably certain the optimized routine
> returns the same results as the original, it might be worthwhile to set
> up a script using Benchmark to be able to compare speeds on different
> platforms as it becomes necessary but I am going to leave that to the
> OP.
>
> Sinan
>
>
> --
> A. Sinan Unur <1usa@llenroc.ude.invalid>
> (remove .invalid and reverse each component for email address)
> clpmisc guidelines:

Thanks for helping with this, the early return is a good idea. I enjoyed
reading all of your comments and suggestions, and am excited to implement
some of the suggestions this weekend.

Re: please help optimize sub

On 19 Oct 2007 02:40:00 GMT, xhoster@gmail.com wrote:

>the same) answer. It seems like half the time I see people using
>Benchmark, at least one of the implementations benchmarked doesn't give the
>right answer but they never test for that. And I trust the times given by

You're right. I know I've committed the sin myself. Actually when I'm
doing Benchmarks now I will also try to include tests, as in
.

>the OS tools like "time" at least as much as I do the Benchmark ones,
>anyway. About the only times I use Benchmark are when I'm tinkering with

But then the benchmark may just be as flawed with the time shell
command as it is with Benchmark.pm!


Michele
--
{$_=pack'B8'x25,unpack'A8'x32,$a^=sub{pop^pop}->(map substr
(($a||=join'',map--$|x$_,(unpack'w',unpack'u','G^ ..'KYU;*EVH[.FHF2W+#"\Z*5TI/ER 256),7,249);s/[^\w,]/ /g;$ \=/^J/?$/:"\r";print,redo}#JAPH,

Re: please help optimize sub

On Fri, 19 Oct 2007 12:51:19 +0200, Michele Dondi
wrote:

>You're right. I know I've committed the sin myself. Actually when I'm
>doing Benchmarks now I will also try to include tests, as in
>.

Err, well, except that that didn't do any benchmark. :)


Michele
--
{$_=pack'B8'x25,unpack'A8'x32,$a^=sub{pop^pop}->(map substr
(($a||=join'',map--$|x$_,(unpack'w',unpack'u','G^ ..'KYU;*EVH[.FHF2W+#"\Z*5TI/ER 256),7,249);s/[^\w,]/ /g;$ \=/^J/?$/:"\r";print,redo}#JAPH,

Re: please help optimize sub

QoS@domain.invalid wrote in news:7w%Ri.11666$2o1.11629@trnddc03:

>
> "A. Sinan Unur" <1usa@llenroc.ude.invalid> wrote in message-id:
>

....

>> up separate scripts. Now that I am reasonably certain the optimized
>> routine returns the same results as the original, it might be
>> worthwhile to set up a script using Benchmark to be able to compare
>> speeds on different platforms as it becomes necessary but I am going
>> to leave that to the OP.
....

> Thanks for helping with this, the early return is a good idea. I
> enjoyed reading all of your comments and suggestions, and am excited
> to implement some of the suggestions this weekend.

You are welcome and good luck.


>> --
>> A. Sinan Unur <1usa@llenroc.ude.invalid>

Note that quoting signatures is frowned upon in general. You newsreader
might have an option to automatically snip sigs that use the proper sig
separator.

Sinan

--
A. Sinan Unur <1usa@llenroc.ude.invalid>
(remove .invalid and reverse each component for email address)
clpmisc guidelines:

Re: please help optimize sub

"A. Sinan Unur" <1usa@llenroc.ude.invalid> wrote in message-id:

>
> QoS@domain.invalid wrote in news:7w%Ri.11666$2o1.11629@trnddc03:
>
> >
> > "A. Sinan Unur" <1usa@llenroc.ude.invalid> wrote in message-id:
> >
>
> ...
>
> >> up separate scripts. Now that I am reasonably certain the optimized
> >> routine returns the same results as the original, it might be
> >> worthwhile to set up a script using Benchmark to be able to compare
> >> speeds on different platforms as it becomes necessary but I am going
> >> to leave that to the OP.
> ...
>
> > Thanks for helping with this, the early return is a good idea. I
> > enjoyed reading all of your comments and suggestions, and am excited
> > to implement some of the suggestions this weekend.
>
> You are welcome and good luck.
>
>
> >> --
> >> A. Sinan Unur <1usa@llenroc.ude.invalid>
>
> Note that quoting signatures is frowned upon in general. You newsreader
> might have an option to automatically snip sigs that use the proper sig
> separator.
>
> Sinan
>

Good idea, I will add this option to NewsSurfer soon. Thanks for helping
with the development of my newsreader, it has been a tricky program to
write; and any suggestions for improving it are extreamly valuable to me.

Best Regards,
Jason

[OT] Re: please help optimize sub

On Fri, 19 Oct 2007 21:06:17 +0000, QoS wrote:

> Good idea, I will add this option to NewsSurfer soon. Thanks for helping
> with the development of my newsreader, it has been a tricky program to
> write; and any suggestions for improving it are extreamly valuable to
> me.

Have a look at http://www.xs4all.nl/~js/gnksa/.

M4

[OT] Re: please help optimize sub

Martijn Lievaart wrote in message-id:

>
> On Fri, 19 Oct 2007 21:06:17 +0000, QoS wrote:
>
> > Good idea, I will add this option to NewsSurfer soon. Thanks for helping
> > with the development of my newsreader, it has been a tricky program to
> > write; and any suggestions for improving it are extreamly valuable to
> > me.
>
> Have a look at http://www.xs4all.nl/~js/gnksa/.
>
> M4

Pure gold.. Thanks so much!