please help optimize sub

Q

QoS

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);
}
 
A

A. Sinan Unur

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,
);
Click to expand...

....

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

Sinan
 
J

Jan Pluntke

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

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);
}
Click to expand...

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
 
Q

QoS

Jan Pluntke said:
Somehow, this has the reek of homework ...
Click to expand...

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);
}
Click to expand...

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)
Click to expand...

Hmm interesting, I will test this.
is what you are actually looking for ...

Regards,
Jan
Click to expand...

Thank you very much for your attention.
 
Q

QoS

A. Sinan Unur said:
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,
);
Click to expand...

...

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

Sinan
Click to expand...

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.
 
X

xhoster

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,
);
Click to expand...

...

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

Sinan
Click to expand...

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.
Click to expand...

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.
 
X

xhoster

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.
Click to expand...

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.
 
A

A. Sinan Unur

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

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,
);
Click to expand...
....

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 ...
Click to expand...

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
 
X

xhoster

A. Sinan Unur said:
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
Click to expand...

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.
 
A

A. Sinan Unur

... ....


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.
Click to expand...

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
 
Q

QoS

A. Sinan Unur said:
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
Click to expand...

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.
 
M

Michele Dondi

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
Click to expand...

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
Click to expand...

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


Michele
 
A

A. Sinan Unur

<[email protected]>
....
....

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.
Click to expand...

You are welcome and good luck.


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
 
Q

QoS

A. Sinan Unur said:
<[email protected]>
...
...

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.
Click to expand...

You are welcome and good luck.


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
Click to expand...

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
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Similar Threads

My `warn delete` subcommand is not working as expected, please help me out 0
Trying to return true if a sub array exists at given index 1
Can't solve problems! please Help 0
Help with code plsss 0
Python battle game help 2
Taskcproblem calendar 4
Need help with this script 4
Help with pointers 1

Members online

Total: 34 (members: 2, guests: 32)
Robots: 186

Forum statistics

Threads
473,774
Messages
2,569,596
Members
45,134
Latest member
Lou6777736

Latest Threads

Top