[Perl.sig] Perl-tip: Ordering hashes
Litss Coordinator
litss.coord at anu.edu.au
Wed Jun 29 16:24:52 EST 2005
>From Jacinta Richardson:
==== Object Oriented Perl course ====
Sydney: 21st - 22nd July.
When working on large projects, or writing reusable components, or
breaking a problem into manageable sections, an Object Oriented
approach
can be invaluable. Perl Training Australia is running it's Object
Oriented Perl course in Sydney, on the 21st and 22nd July.
Most modern CPAN modules are written using Perl's Object Oriented
features, and sub-classing and extending them represents a huge saving
in development, testing, and maintenance. Our Object Oriented Perl
course will be covering this, as well as the theory of Object Oriented
design, inheritance and multiple inheritance, operator overloading, and
plenty of practical exercises.
Book now to secure your place at
http://perltraining.com.au/bookings/Sydney.html
==== The Australian System Administrators Conference (Western Australia)
====
http://www.sage-au.org.au/conf/sage-au2005/
Perl Training Australia is presenting its very popular *Introduction to
Perl* course at the up-coming SAGE-AU conference as a one-day tutorial.
Come along to the tutorial and the conference for only $726.75 (plus
SAGE-AU membership if required). This represents a big saving on Perl
Training Australia's usual course costs, and includes the conference's
two-day technical programme.
The conference runs from the 5th - 9th September at the Rendezvous
Observation Hotel in Perth.
==== Ordered hashes ====
At Perl Training Australia we're always happy to answer simple Perl
questions. One question we're frequently asked involves hashes, and
goes
something like this:
I've created a hash to map the months of the year to the number
of
days they each have. I know that I'm putting the values in to
the
hash in the correct order but when I iterate over the keys,
they
come out differently. How can I get them to come out in month
order?
Perl hashes have no internal order. Under the hood, a hash consists of
a
number of "buckets". When a record is inserted into the hash, the key
is
transformed, using a "hash function", into a bucket number. The details
of the hash function itself are not important, but a good hash function
ensures that even very similar keys are mapped to different buckets. If
too many keys map to the same bucket, then Perl has to spend a lot of
time searching through that bucket for the corresponding value.
The important thing is not *how* Perl puts the key into the hash table
but what the table gives us. To find if a value is in a hash, Perl
takes
the key name supplied, applies the same transformation and checks to
see
whether the key is in that position. This is much faster than searching
through an ordered list.
However, while we often appreciate the speed in which hashes work,
sometimes we want to maintain key order as well. A common solution is
to
create both our hash and an array. The array stores the keys in sorted
order and we can then iterate through our has as required:
my @months = qw(January February ... );
my %days_in = ( January => 31, February => 28, ... );
foreach my $month ( @months ) {
print "$month has $days_in{$month} days\n";
}
If @months and %days_in are created in one place in our program and
then
never changed (such as could be expected for a list of months of the
year) then this is a very good solution. However if our hash is likely
to grow over time then we can encounter problems. What happens if a key
is added to one structure but not the other?
Fortunately there are better solutions.
== Tie::InsertOrderHash ==
This module is available from the Comprehensive Perl Archive Network
(CPAN) http://search.cpan.org.
If you wish to preserve the insert-order of your elements in your hash
then ``Tie::InsertOrderHash'' may be the tool for you. It's usage is
very simple:
use Tie::InsertOrderHash;
tie my %days_in => 'Tie::InsertOrderHash',
January => 31,
February => 28,
March => 31,
April => 30,
May => 31,
June => 30,
July => 31,
August => 31,
September => 30,
October => 31,
November => 30,
December => 31;
print join(" ", keys %days_in), "\n";
# prints: January February March April May June July August
# September October November December
In the above example, we're setting the hash at creation time. This is
not required. We can add our values to our hash whenever we desire,
just
like a normal hash, further, our values can be any kind of value we can
normally use in a hash.
tie my %friends => 'Tie::InsertOrderHash',
Paul => 'likes scuba diving';
$friends{Daniel} => 'travels around the world';
tie my %restaurant_rating => 'Tie::InsertOrderHash';
$restaurant_rating{'Enlightened Cuisine'} = 9;
Note that these hashes only preserve insert-order. Thus if we later
change February in our our ``days_in'' hash to have 29 days because of
a
leap year, February will be moved to the end of the list.
== Hash::IxHash; ==
This module is available from the Comprehensive Perl Archive Network
(CPAN) http://search.cpan.org.
``Tie::InsertOrderHash'' does not allow you to change values in your
hash and keep the original ordering. Thus, as mentioned above, updating
the days in February will cause February to now appear after December
when listing the keys.
If you want to be able to change values without changing the ordering
then ``Tie::IxHash'' may be a better option.
use Tie::IxHash;
tie my %days_in => 'Tie::IxHash',
January => 31,
February => 28,
March => 31,
April => 30,
May => 31,
June => 30,
July => 31,
August => 31,
September => 30,
October => 31,
November => 30,
December => 31;
# And later
$days_in{February} = 29;
print join(" ", keys %days_in), "\n";
# prints: January February March April May June July August
# September October November December
There is also ``Tie::Hash::Indexed'' which provides less features than
``Tie::IxHash'', but is considerably faster.
To get a similar behaviour to ``Tie::InsertOrderHash'' you can
``delete'' a key-value pair from your hash before providing the new
value. Thus if we were to write:
delete($days_in{June});
$days_in{June} = 3;
then June would be considered to have been inserted last.
==== Upcoming Courses in Canberra ====
http://perltraining.com.au/bookings/Canberra.html
Introduction to Perl: 1st - 2nd November
Intermediate Perl: 3rd - 4th November
==== Upcoming Courses in Melbourne ==== ====
http://perltraining.com.au/bookings/Melbourne.html
Introduction to Perl: 11th - 12th August
Intermediate Perl: 18th - 19th August
Perl Best Practices: 14th - 15th November
Understanding Regular Expressions: 22nd November
==== Upcoming Courses in Sydney ====
http://perltraining.com.au/bookings/Sydney.html
Object Oriented Perl: 21st - 22nd July
Introduction to Perl: 20th - 21st September
Intermediate Perl: 22nd - 23rd September
==== Corporate Courses ====
http://perltraining.com.au/corporate.html
Do you have a large group, or the need for training at a particular
time? Perl Training Australia is happy to arrange a course in the time
and place that best suits you. For more information read our page on
Corporate Courses at http://perltraining.com.au/corporate.html or call
us on +61-3-9354-6001.
_______________________________________________
This Perl tooltip and associated text is Copyright Perl Training Australia.
You may freely distribute this text so long as it is distributed in full
with this Copyright noticed attached.
If you have any questions please don't hesitate to contact us:
Email: contact at perltraining.com.au
Phone: 03 9354 6001
Perl-tips mailing list
To change your subscription details visit:
http://perltraining.com.au/cgi-bin/mailman/listinfo/perl-tips
More information about the Perl.sig
mailing list