CODEWITHSUNDEEP
arraysperl
Tito Candelli
Tito Candelli

Reputation: 237

most efficient way to obtain all the elements between two values in a Perl array

I have a list of integer values; each of these integer values in associated to a real value.

to give you an idea, they might be represented like this:

1    0.48
5    0.56
6    0.12
20   1.65
25   1.50

not all integers are represented in the list, only those who have a value associated with them.

given a range of integer values i have to perform some operation on the real values associated to any integer between the extremes of the range. for example:

given the range 5-20 i would need to extract the real values associated with the integers 5, 6, and 20 and then perform some operation on them.

right now the best i could come up with was to use the integer values as keys to a hash and loop over all the sorted integer values and check that the each value was between the range; like so:

foreach (sort key %hash) 
{
  if ($_ >= $rangemin && $_ <= $rangemax)
  {
    push @somearray, $hash{$_}
  }
  last if $_ >= $rangemax;
}

The real list i'm dealing with, however, is much longer and this implementation takes a lot of time to execute.

is there a faster/more efficient way to obtain a list of values lying between two arbitrary values in an array?

Upvotes: 2

Views: 934

Answers (3)

ysth
ysth

Reputation: 98398

Don't sort, there's no need to.

This may be slightly faster:

@somearray = @hash{ grep $_ >= $rangemin && $_ <= $rangemax, keys %hash };

(building up a list of desired indexes by using grep to filter all the keys, then using a hash slice to get all the values at once).

You would have to benchmark it to know for certain.

The other alternative is to loop from $rangemin to $rangemax:

for ($rangemin..$rangemax) {
    push @somearray, $hash{$_} if exists $hash{$_};
}

or

for ($rangemin..$rangemax) {
    push @somearray, $hash{$_} // ();
}

or

@somearray = @hash{ grep exists $hash{$_}, $rangemin..$rangemax };

Which is fastest will depend on greatly on the sparseness of your data and the size of range and the percentage of hash values you are including.

Upvotes: 3

amphibient
amphibient

Reputation: 31230

You don't need to do a full collection scan, you should just iterate 5-20 and get the value associated with that key from the collection, if it exists (is not undef or defined).

Upvotes: 1

TLP
TLP

Reputation: 67900

Whether its faster or not probably depends on your data, but you can simply loop over the numbers, and check if they exist:

for my $num ($rangemin .. $rangemax) {
    if (defined $hash{$num}) {           # number exists
        # do stuff
    }
}

As a variation on that, you can use grep to get a list of indexes:

my @range = grep defined($hash{$_}), $rangemin .. $rangemax;

Upvotes: 2

Related Questions