If you want to save memory, build your own hash. Here's an example - you should probably replace the _hashit() function with something good. It's a pity Perl doesn't give us access to it's own hash function, a little XS trickery might solve that though.
The point of this example is that it stores the both the key and the value as a reference, that way the memory for the strings is shared between the 2 internal hash thingys. It'll obviously be slower than a real Perl hash but should be much faster than a database. It's also missing things like delete, exists, update. These are easy enough to add if you need them.
I think the memory savings should be pretty good, unless your strings are very short in which case the overhead of the references will undo any benefit.
A short example of how to use it
my $h = TwoWayHash->new(100); # 100 is the "size", ignore for now
$h->insert("mam", "dad");
print $h->retrieveOneWay("L2R", "mam") # Left 2 Right
# dad
print $h->retrieveOneWay("R2L", "dad") # Right 2 Left
# mam
If you wanted to make this look like a genuine Perl hash you will have to write another class to handle the tie interface and then tie 2 hashes like this
tie %r2l, $twowayhash, "R2L"; # right to left
tie %l2r, $twowayhash, "L2R"; # left to right
This will slow it down even further.
use strict;
use warnings;
package TwoWayHash;
sub new
{
my $pkg = shift;
my $size = shift;
my $self = bless {Size => $size}, $pkg;
# preextend the buckets
$self->{R2L} = [];
$#{$self->{R2L}} = $size - 1;
$self->{L2R} = [];
$#{$self->{L2R}} = $size - 1;
return $self;
}
sub insert
{
my $self = shift;
my ($v1, $v2) = @_;
$self->insertOneWay("L2R", \$v1, \$v2);
$self->insertOneWay("R2L", \$v2, \$v1);
}
sub insertOneWay
{
my $self = shift;
my $which = shift;
my $key = shift; # these are refs to the strings
my $value = shift;
my $h = _hashit($key) % $self->{Size}; # turn the key into somethi
+ng much smaller and hopefully unique
my $buckets = $self->{$which};
# find the already existing bucket or create a
# new one then put the key/value into the bucket
my $bucket = $buckets->[$h] ||= [];
push(@$bucket, $key, $value);
}
sub _hashit
{
# a terrible hash function! It just takes the first 2 characters of th
+e string
# and turns them into a number between 0 and 65535
# You'll need something better for real life
my $rstr = shift;
return unpack("S", substr($$rstr, 0, 2));
}
sub retrieveOneWay
{
my $self = shift;
my $which = shift;
my $key = shift; # not a ref this time
my $h = _hashit(\$key) % $self->{Size};
my $buckets = $self->{$which};
if (defined(my $list = $buckets->[$h]))
{
# go through the list of pairs of key/values and see if any ar
+e the ones
# we want
my $i = 0;
while ($i < $#$list)
{
if ($key eq ${$list->[$i]})
{
return ${$list->[$i + 1]};
}
$i += 2;
}
}
# if we get here then we didn't find anything nice
return undef;
}
1;
some code to test it
use strict;
use warnings;
use Test::More 'no_plan';
use Test::NoWarnings; # comment out if you don't have this installed
use TwoWayHash;
my $h = TwoWayHash->new(100);
my @tests = (
["abcd123", "efgh123"],
["wxyz456", "lmno456"],
["abcd456", "efgh456"],
);
foreach my $test (@tests)
{
my ($v1, $v2) = @$test;
$h->insert($v1, $v2);
}
use Data::Dumper;
#print Dumper(\$h);
foreach my $test (@tests)
{
my ($v1, $v2) = @$test;
is($h->retrieveOneWay("L2R", $v1), $v2, "L2R retrieve '$v1'");
is($h->retrieveOneWay("L2R", $v2), undef, "L2R don't retrieve '$v2
+'");
is($h->retrieveOneWay("R2L", $v2), $v1, "R2L retrieve '$v2'");
is($h->retrieveOneWay("R2L", $v1), undef, "R2L don't retrieve '$v1
+'");
}
is($h->retrieveOneWay("L2R", "abcd234"), undef, "L2R don't retrieve");
Creating a new TwoWayHash requires 1 argument, the size. This is the number of buckets to allocate. In a hash, too few buckets means that each bucket will have many elements in it and so when it comes time to retrieve an element from that bucket, you might need to search through lots of other elements in the bucket.
The number of buckets is fixed, the right size depends on your dataset. Perl's hashes are smarter, they can increase the number of buckets when it's necessary. |