[Charlotte.PM] Help me tune this for speed

[Steven Bush]

Hi Drew,
  I've found one point that I think will help speed your process up. 
When you loop through all found unique edges from smallest to largest 
and again through all previously found edges in order, you build an 
array ref each time ($points_ref). When you are populating this array 
with data, the first two things you put into it do not use any 
information that is generated by the second loop. So you are basically 
preforming a pair of calculations 90300 times that only needs to be 
calculated 1778 times. I've re-written the associated area of code 
(lines 84-87, 94 in my code) to fix this problem, and it is included 
below. I have not yet tried to run this code, so I'm not sure how much 
help it will be, but I think it should help some.

~Steven

#!/usr/bin/perl

######################################################################
# CPAN modules
######################################################################

use YAML qw(Dump Load);
use Carp;
use Benchmark;
use Math::Geometry::Planar;

use strict;


######################################################################
# A few globals
######################################################################

my $points; # hash ref holding the raw data {'1' => [X,Y], '2' => [X,Y], ...}
my @edges; # Array to keep refrences to all edges [edge, X1, Y1, X2, Y2] ...
my $neighborEdges; # hash ref to hold sorted neighbor edges {'1' => edge1, '2' => edge2, ...}

######################################################################
#
#       MAIN
#
######################################################################

# Read in the X,Y coordinates from supplied data
{
  local $/;
  open(my $fh, "dump_301.dat") or die "Unable to open file: $!\n";
  $points = Load( <$fh> );
  croak($@) if $@;
  close($fh);
}

# Find all the unique edges

eval {
  my $start_distance = Benchmark->new;
  my $found = {};

  # p1 is starting or anchor point of the line segment
  foreach my $p1 (@{$points}) {
    # p1 is end point of the line segment
    foreach my $p2 (@{$points}) {
      # We don't need to caculate if anchor and end are the same
      # or we have already seen these two pairs [reversed] before    
      unless ( ($p1 == $p2) || $found->{$p2}->{$p1} ) {

        # Compute the edge
        my $edge = sqrt(
          ($p1->[0] - $p2->[0])**2 +
          ($p1->[1] - $p2->[1])**2
        );

        # Push a ref of the whole thing on a stack
        push (@edges, [ $edge, $p1->[0], $p1->[1], $p2->[0], $p2->[1] ]);
      
        # Keep track of the edges we've already computed (no need to do so twice)
        $found->{$p2}->{$p1} = 1;

      }
    }
  }

  print "Found unique Edges = ", scalar(@edges), "\n";
  print timestr(timediff(Benchmark->new, $start_distance)), "\n";
};

croak($@) if ($@);

# Compute the neighboors
my $start_intersect = Benchmark->new;

# Need an integer to keep our sort order
my $neighboorCNT = 1;

# Loop trough all found unique edges from smallest to largest
foreach my $aref ( sort {$a->[0] <=> $b->[0] } @edges) {

  my $neighbor = 1; # default true
  my $line_1_ref = [];

  push (@{$line_1_ref}, [$aref->[1],$aref->[2]]); # line 1 point A X,Y
  push (@{$line_1_ref}, [$aref->[3],$aref->[4]]); # line 1 point B X,Y

  # Loop through all previously found edges in order
  for (my $n=1;$n<=$neighboorCNT;$n++) {
    if ($neighborEdges->{$n}) {

      my $points_ref = []; # Data structure to pass to SegmentIntersection
      push (@{$points_ref}, @{$line_1_ref}); # line 1 points
      push (@{$points_ref}, [$neighborEdges->{$n}->[1],$neighborEdges->{$n}->[2]]); # line 2 point A X,Y
      push (@{$points_ref}, [$neighborEdges->{$n}->[3],$neighborEdges->{$n}->[4]]); # line 2 point B X,Y

      my @p = SegmentIntersection($points_ref);

      # If a intersect is found, set false and quit checking
      if (SegmentIntersection($points_ref)) { 
        $neighbor = 0;
        last;
      }

    }
  }

  if ($neighbor) { 
    $neighborEdges->{$neighboorCNT} = $aref;
    $neighboorCNT++;
  }
  
}

print "Unintersected edges ", scalar(keys %{$neighborEdges}), "\n";

print timestr(timediff(Benchmark->new, $start_intersect)), "\n";