in reply to fastest way to compare numerical strings?

It's clear that you want to find nearby points in a 2-dimensional space. One effective way is to overlay a grid which groups the data into cells. Then you only have to compare points from adjacent cells. Some pseudo-code: 
my %CellMembers;
for my $i (0..$npoints) {
  my $cellid = int($lat[$i]).",".int($long[$i]);
  push(@{$CellMembers{$cellid}}, $i);
}

# iterate over cells
for my $ci (keys %CellMembers) {
  for my $cj (...cells within distance 1 of $ci...) {
    for my $i (@{$CellMembers{$ci}}) {
      for my $j (@{$CellMembers{$cj}} {
        ...compare points $i and $j...
      }
    }
  }
}

[download]
Lots of nested loops, but probably a big time saver.

Replies are listed 'Best First'.
Re^2: fastest way to compare numerical strings?
by salva (Canon) on Jul 01, 2008 at 07:11 UTC
    that is probably the best solution, so let's see some real (untested) code! 
    use POSIX qw(floor);

my @lat = ...;
my @long = ...;

my $radius = 0.01;
my $radius2 = $radius ** 2;

my @flat = map { floor($_/$radius) } @lat;
my @flong = map { floor($_/$radius) } @long;

my %cell;
for my $i (0..$#lat) {
  push @{$cell{$flat[$i], $flong[$i]}}, $i
}

for my $i (0..$#lat) {
  my @near;
  for my $dflat(-1, 0, 1) {
    my $flat = $flat[$i] + $dflat;
    for my $dflong(-1, 0, 1) {
      my $flong = $flong[$i] + $dflong;
      if (my $cell = $cell{$flat, $flong}) {
        for my $j (@$cell) {
          if ((($lat[$j] - $lat[$i]) ** 2 + ($long[$j] - $long[$i]) **
+ 2) < $radius) {
            push @near, $j
          }
        }
      }
    }
  }
  @near = sort @near;
  print "points near $i: @near\n";
}

    [download]
[reply]
[d/l]

In Section Seekers of Perl Wisdom