in reply to calculate average from range of hash values (optimize)

Hmm, rolling averages. You can convert that from N**2 to linear, if you can assume you're moving through the numbers in sequence. Also, converting your hash to an array would be better. Try something like this: 
#!/usr/bin/perl
use strict;
use warnings;

## setup
my ($gap, $elements, $first, $i) = (10000, 20000, 10000, 0);
my @data = map { rand } (1 .. $elements);

## compute initial sum
my $sum = 0;
$sum += $_ for @data[0 .. $gap];

## go through @data serially computing averages
while (1) { 
  printf("average of %d to %d: %d",
         $i + $first, $i + $first + $gap, $sum / $gap);

  $sum -= $data[$i];                # subtract old 1st element
  last if ++$i + $gap > $elements;  # stop when done
  $sum += $data[$i + $gap];         # add new last element
}

[download]
HTH

Replies are listed 'Best First'.
Re: Re: calculate average from range of hash values (optimize)
by revdiablo (Prior) on Jul 27, 2003 at 02:31 UTC

    Thanks for the reply, cleverett, but there are a few reasons it is not exactly applicable to my situation. One, which I specifically mentioned in my post, is I would like to avoid using an array. The keys are Quite Large Numbers (for example '1059159920'), and trying to add even one array entry with an index that high runs out of memory. Another reason that I didn't mention, or even think about when I first made my post, is the keys are relatively sparse. I can't simply roll through the range in sequence; I have to make sure the keys exist.

    That said, your post does give me some food for thought, and I might just steal some of your ideas. :)

[reply]
      Perhaps keep an index to the original data hash, thusly: 
      use strict;

## simulate original %data hash
my %data = map { (int(rand(10**10) + 10**9) => rand } (0 .. 2*10**5);

my ($keys, $values) = ([], []);   ## remember what goes where
foreach (sort keys %data) {
  push @$keys, $_;
  push @$values, $data{$_};
}

## now obtain rolling averages

      [download]
[reply]
[d/l]

In Section Seekers of Perl Wisdom