On 7/14/06, [EMAIL PROTECTED] <[EMAIL PROTECTED]> wrote:
The MUMPS language provides a function, called $ORDER, which takes an argument
and returns the next index that exists in the array that would come after the
supplied argument (a 2nd argument can be used to cause the function to return
the previous index instead of the next index). For example, given an array
with the index values given above, if I asked for the next index after 0, I
would get 1; the next index after 50 would return 100; the next index after "Z"
would return "a"; etc.
My question: is there any way to approach similar functionality in Perl? Any
non-numeric arrays in my code are being converted to Perl hashes. I can
retrieve the value of a specific key, and I can use a for loop to go through
every key/value pair but, is there any way of doing something similar to $ORDER
without have to scan the entire hash?
There's no native structure which matches what you need. Hashes are
really close except for the $ORDER thing.
If the hashes tend to be small (say, less than 10,000 keys) or order()
isn't called very often then I'd just go with just implementing
order() using sort. Its surprisingly efficient. Its written in
highly optimized C while anything you write will be written in
not-so-optimized Perl. And its cheap, programming time wise.
sub _mumps_cmp { ...this exercise is left to the reader... }
sub order {
my($hash, $given_key) = @_;
my $next_key;
for my $key (sort _mumps_cmp keys %$hash) {
if( _mumps_cmp($given_key, $key) == -1 ) {
$next_key = $key;
last;
}
}
return $next_key;
}
To most closely match the existing interface you'd create a tied hash
which kept its keys sorted. If you implemented this using a search
tree rather than a linear sort it can be efficient, in the big O
sense. Then order() is just a matter of walking the tree to the right
until you come upon a node greater than your given key. Then you
return the key of the next node on the right. O(logn) while the sort
solution is O(n logn). But this doesn't take into account the
constant.
Unless your hashes are large, say more than 10,000 keys, this is going
to be hideously inefficient in the C (constant) sense. And a simple
tied hash is 10 times slower than a regular hash simply due to method
call and tying overhead. If you used a straight object rather than a
tie it goes down to 3 times slower.
So I'd go with just using a hash and implementing order() with sort.
That gets things working quickly, cheaply and most reliably. Don't do
anything more complicated until you've done some profiling.
Also, is there any defined order in
which a hash is stored?
No. As a matter of fact 5.8.1 made it specificly randomize on each new process.
