I'd like to put in a pitch for RFC 124 in Perl 6. Balanced binary
trees (such as AVL or red-black trees) allow O(log2 n) insertion, searching,
outputting ranges of keys & deletion. I wouldn't want to touch existing Perl
hashes, but it would be very useful to be able to associate a sort routine
with certain hashes & have those hashes maintained as balanced binary trees.
The speed advantage would be in not having to sort keys every time the hash
is changed.
Perl scripts which do fast graphics would be much easier to write. For
example, a simple & very fast Perl sub which displays all points in a
rectangular area (a window) could easily be written as follows:
sub show_points
{
my ($xmin,$ymin,$xmax,$ymax)=@_;
foreach $x (keys %xhash{$xmin..$xmax}) {
foreach $y (keys %{$xhash{$x}}{$ymin..$ymax})
{ &display_point($x,$y); }
}
}
(I'm not sure about the syntax of the hash-of-hashes used for the Y variable
above, but I think the idea is clear. And I'm not sure if the '..' syntax
in the hash index context is taken -- I thought that it was just in the array
index context, but I might be wrong.)
Implementing RFC 124 well could speed a number of areas other than
graphics. For example, in a CGI routine for an auction web site, it would be
fast & easy to find all bids in a certain range. A unary '..' syntax would
also be useful, i.e. 'keys %bids{$min..}' would quickly return any bid(s)
above $min for a motivated seller who wants to avoid shipping & and 'keys
%bids{..$max}' could be used to send a 'sorry' email to bidders after a
minimum bid moves upwards.
Finally, AVL & red-black tree tested ANSI C code with a GNU license
already exists (it's called 'libavl'), reducing the work involved somewhat
(the AVL or red-black routines would still need to be interfaced & installed
with Perl). My tests show that libavl's ordinary AVL & red-black routines
are about equal in speed (the red-black is about 4% faster on my HP-UX
machine, but 4% is well within the margin of error). I'm guessing that the
threaded AVL routine would be the most appropriate one for quickly returning
ranges of keys, and the package doesn't include a threaded red-black tree.
libavl is available from a number of sites, see:
http://www.leo.org/pub/comp/os/unix/gnu/avl/
or use your favorite search engine to look up the string 'avl-1.4.0'.
Thanks,
Carl Wuebker * HP Roseville * [EMAIL PROTECTED] * (916) 785-4296
"Representing myself, not HP"
