
Laurent_R
Veteran
/ Moderator
Aug 30, 2016, 5:54 AM
Post #4 of 18
(15161 views)
|
Re: [bulrush] How to speed up search on array?
[In reply to]
|
Can't Post
|
|
When you read your file, split the data between the key and prices. Store each price in an array ref within an hash entry with that key. Then, when looking up, find the hash entry for the key, and just look into the array ref stored there. Example. Suppose you have this input data:
key1 price1 key1 price2 key2 price1 key2 price3 key2 price4 For this small dataset, you would construct a hash with two entries, for key1 and key2, and the hash values would be the price lists:
( key1 => (price1, price2), key2 => (price1, price3, price4) ) Then, when you are doing the lookup, if you have key1, you need to grep among an arrayref containing only two values; if you have key2, you grep among three values. You're no longer parsing the entire dataset each time (because access to a hash is almost immediate). Note that you could also possibly use a hash of hashes, that would be even quicker, but whether you can do it depends on the details of your data. Some quick untested pseudo-code for constructing the hash of arrays (making some simple assumptions about your data, you'll have to adjust to their format):
my %hash; while (my $line = <$IN>) { chomp $line; my ($key, $val) = split / /, $line; push @{$hash{$key}}, $val; } This should give you an hash of arrays essentially looking like what I described above. Then, some also untested code for retrieving the data from the hash:
while (my $line = <$IN>) { chomp $line; my ($key, $val) = split / /, $line; if (defined $hash{$key}) { my @result = grep /$val/, @{$hash{$key}}; print "Found it!: @result \n" if @result; } }
|