bowsayge said:
Pea said to us:
Thank you, Brian. I used your suggestion and modification and it
worked well, except when there were two numbers in a row missing.
[...]
As a learning experience, Bowsayge created a program that seems
to be able to list the missing numbers from a range:
#!/usr/bin/perl
use strict;
use warnings;
chomp (my @numbers = <DATA>);
s/\D+//g for (@numbers);
Ignoring non-digits is an extra feature. It may be useful, but maybe not.
There is no good reason to bring it in here.
@numbers = sort { $a <=> $b } @numbers;
You are sorting the numbers only to get their minimum and maximum (the
rest of the algorithm doesn't need them sorted). In general, that is
wasteful, especially when the lists are long. The standard module
List::Util has functions that find the minimum and maximum in linear
time. For this example you could dodge the issue and simply assume
the numbers come sorted.
my ($min, $max) = ($numbers[0], $numbers[$#numbers]);
$numbers[$#numbers] can be written as $numbers[-1].
my %hash = map +($_, 1), @numbers;
my @missing = grep !defined($hash{$_}), ($min..$max);
You have taken care to set the hash values to 1, so defined() is not
necessary.
printf "%-20s %s\n", 'numbers', 'missing';
printf "%-20s %s\n", "@numbers", "@missing";
[snip data]
Your code shows a very plausible use of a hash. In general, a hash
is the structure of choice when the problem can be expressed in terms
of sets. The set elements get to be the hash keys (or the keys a hash
gets probed for). The values are of little importance in this application
of hashes. Your code is a good example.
The sets in this case are the integers in a range, and some (explicitly
given) subset thereof. The problem is to find the set difference.
With sets of integers it can be of advantage to use arrays for the
representation instead of hashes, especially if the integers are small.
Arrays use substantially less storage and are a little faster than
hashes. You may find it instructive to re-write your code to use
an array. You will have to change very little, except for the "map"
line.
Going a step farther in storage conservation, a bit vector could be
used. It is the most compact way to store a set of small integers.
With @numbers, $min and $max being set:
my $set = '';
vec( $set, $_, 1) = 1 for @numbers;
my @missing = grep !vec( $set, $_, 1), $min .. $max;
Again, there isn't much change from your code to this variant.
Anno