Slow code to improve. Thanks!

[gamo]

#!/usr/bin/perl -w

use strict;

# Digamos que tenemos 30 proyectos de inversión con VAN positivo (VAN = NPV)

my $limit = 30;

my ($inversion, $npv, @INV, @VAN);

for (0..$limit-1){
$inversion = sprintf ("%.02f", -1000 * rand);
$npv = 1500 * rand;
$INV[$_] = abs ($inversion);
$VAN[$_] = $npv;
}

# Digamos que tenemos un presupuesto de 10_000 (BUDGET)
my $PPTO = 10_000;

# Enumeremos todas las posibilidades y escogemos la cartera (PORTFOLIO)
# de proyectos cuya suma da un mayor VAN de la cartera

my $antes = time();

my @a = (0) x $limit;
my $count = 0;

my $MAXNPV = 0;
my $NPROYECTOS = 0;
my @b;

my ($van, $ppto, $c, @pn);

while ($count < $limit) {
# print reverse @a, "\n"; # reverse @a for avoid
antinature
$van = $ppto = $c = 0;
for (0..$limit-1){
$van += $a[$_] * $VAN[$_];
$ppto += $a[$_] * $INV[$_];
++$c if ($a[$_] == 1);
}
if ($ppto <= $PPTO && $van >= $MAXNPV){
@b = @a;
@pn=();
for (0..$limit-1){
push (@pn, $_+1) if $a[$_] == 1;
}
$MAXNPV = $van;
$NPROYECTOS = $c;
print "El vector ",@b," produce $MAXNPV con una inversión de $ppto ($c
proyectos)\n";
}

@a = enum(@a); # next number or
combination
}
print "Lista de proyectos: @pn\n";

my $despues = time();
print "\nElapsed time ", ($despues-$antes)/60," min.\n";

exit 0;



sub enum {
my @l = @_;
my $i = 0;
zz:
if ($l[$i] == 0) {
$l[$i]=1;
return @l;
}else{
$l[$i]=0;
if (++$i > $count){
$l[++$count]=1;
return @l;
}else{
goto zz;
}
}
}


__END__


This short code last for hours.
Make suggestions to speed up.
Thank you.


--
http://gamo.sdf-eu.org/
"What happens in EuroVegas it remains in EuroVegas"

[gamo]

El 20/11/20 a las 16:20, gamo escribió:

>
> This short code last for hours.
> Make suggestions to speed up.
> Thank you.

Yes, I know that this happens to be like a
knapsack problem which can be solved with
glpk. But that's too boring.

TIA

[Eric Pozharski]

with <rp8mrm$38d$1...@gioia.aioe.org> gamo wrote:

*SKIP*

> __END__
>
> This short code last for hours. Make suggestions to speed up. Thank
> you.

First, I presume you understand you're churning through 2**30 (1.07e+09)
combinations here -- it will take time. Anyway, I've been reassured
(again) that: Less Perl makes it slow; Less Perl More Clever Perl
makes it even slower; Less Perl More Clever Perl More Implicit List
Contexts brings it to stall. However, checkout this beauty:


--- foo.cRPn0x.pl 2020-11-22 17:19:19.629862529 +0200
+++ foo.l0Fble.pl 2020-11-22 23:11:23.056820382 +0200
@@ -23,35 +23,32 @@

my $antes = time();

-my @a = (0) x $limit;
-my $count = 0;
-

my $MAXNPV = 0;
my $NPROYECTOS = 0;

-my @b;

my ($van, $ppto, $c, @pn);

+my( $oepa, $wabt ) = ( 0 );

-while ($count < $limit) {
+while ( $oepa < 2**30 ) {

# print reverse @a, "\n"; # reverse @a for avoid antinature
$van = $ppto = $c = 0;
for (0..$limit-1){

- $van += $a[$_] * $VAN[$_];
- $ppto += $a[$_] * $INV[$_];
- ++$c if ($a[$_] == 1);
+ $oepa & 2**$_ or next;
+ $van += $VAN[$_];
+ $ppto += $INV[$_];
+ ++$c

}
if ($ppto <= $PPTO && $van >= $MAXNPV){

- @b = @a;
@pn=();
for (0..$limit-1){
- push (@pn, $_+1) if $a[$_] == 1;
+ push (@pn, $_+1) if $oepa & 2**$_

}
$MAXNPV = $van;
$NPROYECTOS = $c;

- print "El vector ",@b," produce $MAXNPV con una inversión de $ppto ($c proyectos)\n";
+ $wabt = reverse( sprintf q|%*b|, $limit, $oepa ) =~ tr{ }{0}r;
+ print "El vector $wabt produce $MAXNPV con una inversión de $ppto ($c proyectos)",sprintf( " %7.0f",$oepa/(time-$antes+1)),"\n";
}
-
- @a = enum(@a); # next number or combination
+ $oepa++

}
print "Lista de proyectos: @pn\n";

@@ -60,23 +57,3 @@

exit 0;

-
-
-sub enum {
- my @l = @_;
- my $i = 0;
-zz:
- if ($l[$i] == 0) {
- $l[$i]=1;
- return @l;
- }else{
- $l[$i]=0;
- if (++$i > $count){
- $l[++$count]=1;
- return @l;
- }else{
- goto zz;
- }
- }
-}
-

Please excuse me avoiding mimicking yours Style Guidelines -- I can't
figure out what they are. Second, due to random data being used
measuring performance is kinda dubious. Anyway -- whooping three times
faster!

Now, about suggestions. First thing that springs is PDL. Couple of
times I was motivated but never have had time to find out how it works.
One suggestion, if you find yourself moving data to-and-fro PDL, then
abort -- it won't yield anything. Upload datas once, then read results
*once*.

The other thing would be gradient descent. I have no slightest idea how
to apply it here though.

--
Torvalds' goal for Linux is very simple: World Domination
Stallman's goal for GNU is even simpler: Freedom

[gamo]

El 23/11/20 a las 10:25, Eric Pozharski escribió:

> Please excuse me avoiding mimicking yours Style Guidelines -- I can't
> figure out what they are. Second, due to random data being used
> measuring performance is kinda dubious. Anyway -- whooping three times
> faster!
>

No problem. The style is personal. Anyway I find a lot opaque to use
bitwise operator to produce the 2^30 combinations.

I was thinking in a simple $counter++ and a unpack and a split i.e.

> Now, about suggestions. First thing that springs is PDL. Couple of
> times I was motivated but never have had time to find out how it works.
> One suggestion, if you find yourself moving data to-and-fro PDL, then
> abort -- it won't yield anything. Upload datas once, then read results
> *once*.

PDL is out of my simple scope. I could do it all in C (no hashes, no
regex) but I like too much Perl.

>
> The other thing would be gradient descent. I have no slightest idea how
> to apply it here though.

That thing could help, as any heuristic, if I do not want the full brute
force attack to reach the best combination.

Thank you very much for your ideas.
Best regards.

[gamo]

El 23/11/20 a las 10:25, Eric Pozharski escribió:

> Anyway -- whooping three times
> faster!

Genial! it tooks 74 minutes insstead of 190.
I'll publish both versions in the web with your credit,
if you don't worry about.
Thanks.

[Eric Pozharski]

with <rphk63$1frt$1...@gioia.aioe.org> gamo wrote:
> El 23/11/20 a las 10:25, Eric Pozharski escribió:

>> Anyway -- whooping three times faster!
> Genial! it tooks 74 minutes insstead of 190. I'll publish both
> versions in the web with your credit, if you don't worry about.

Web? That's scary. Anyway, CC-BY then, if, of course, it's compatible.

> Thanks.

clpm (or should I say -- C.L.P.M.?) rulez!

[Eric Pozharski]

with <rpgi4d$1enm$1...@gioia.aioe.org> gamo wrote:
> El 23/11/20 a las 10:25, Eric Pozharski escribió:

>> Second, due to random data being used measuring performance is kinda
>> dubious. Anyway -- whooping three times faster!

*SKIP*

> Anyway I find a lot opaque to use bitwise operator to produce the 2^30
> combinations. I was thinking in a simple $counter++ and a unpack and
> a split i.e.

Wrong! That's the problem here. With each implicit list and/or
explicit array you pay the price -- memory allocation. I went through
multiple iterations, and when I moved enum()'s code into the loop only
then it became (almost) as fast as initial. It was frustrating.

>> Now, about suggestions. First thing that springs is PDL.

*SKIP*

> PDL is out of my simple scope. I could do it all in C (no hashes, no
> regex) but I like too much Perl.

Well, feels like I'll add PDL-junkie to my attributes one day.

*CUT*

[gamo]

El 24/11/20 a las 15:58, Eric Pozharski escribió:

> with <rphk63$1frt$1...@gioia.aioe.org> gamo wrote:
>> El 23/11/20 a las 10:25, Eric Pozharski escribió:
>
>>> Anyway -- whooping three times faster!
>> Genial! it tooks 74 minutes insstead of 190. I'll publish both
>> versions in the web with your credit, if you don't worry about.
>
> Web? That's scary. Anyway, CC-BY then, if, of course, it's compatible.
>
>> Thanks.
>
> clpm (or should I say -- C.L.P.M.?) rulez!
>

I have to mention that finally try a version 3
with using the 'glpsol' util (real bad asses in gnu)
and get a result in 0 minutes. In my web.

Best regards. c.l.p.m rulez!