Algorithm-SkipList
view release on metacpan or search on metacpan
- removed if (CACHE_INSERT_FINGERS) tests
- additional optimizations and code cleanup
- added test to search for non-existent keys in Benchmark.pl
0.51 Mon Apr 12 2004
- fixed bug with next_key method called without first_key
- added tests for this bug
- added "heavy" test to distribution
- minor optimizations of delete method
- assertions are no longer required (which leads to ~3% speedup)
and removed section in POD about assertions
- removed commented-out references to forward method
- minor updates to source code comments
0.50 Mon Mar 29 2004
- section about Assertions added to POD
- documented level() method
- clear method now intitializes initial node header
- added various assertions
* removed the forward method from *::Node
- uses enum module
- added test for non-integer keys
- clear method now resets LAST_INSRT cache
- removed use of LEVEL for List::SkipList::Node
* key_cmp method accesses KEY directly rather than uses the key method
* calling convention for List::SkipList::Node is changed
Skip lists are a probabilistic data structure that seem likely
to supplant balanced trees as the implementation method of
choice for many applications. Skip list algorithms have the same
asymptotic expected time bounds as balanced trees and are
simpler, faster and use less space.(*)
This implementation may not be faster or use less space, but in
superficial testing, it does appear to be a reasonably faster
substitute for some pure-Perl tree modules. (However, see the
included Benchmark.txt file for comparisons with similar Perl
modules, as well as the SEE ALSO section below.)
Skip lists are similar to linked lists, except that they have
random links at various levels that allow searches to skip over
sections of the list, like so:
4 +---------------------------> +----------------------> +
| | |
3 +------------> +------------> +-------> +-------> +--> +
| | | | | |
2 +-------> +--> +-------> +--> +--> +--> +-------> +--> +
| | | | | | | | |
1 +--> +--> +--> +--> +--> +--> +--> +--> +--> +--> +--> +
A B C D E F G H I J NIL
lib/Algorithm/SkipList.pm view on Meta::CPAN
sub find {
my ($self, $key, $finger) = @_;
my ($node, $update_ref, $cmp) = $self->_search($key, $finger);
($cmp == 0) ? $node->value : undef;
}
sub _first_node { # actually this is the second node
my $self = shift;
my $list = $self->list;
my $node = $list->header()->[0];
}
sub last_key {
my ($self, $node, $index) = @_;
lib/Algorithm/SkipList.pm view on Meta::CPAN
$value = $list->find('key2');
$list->delete('key1');
=head1 DESCRIPTION
This is an implementation of I<skip lists> in Perl.
Skip lists are similar to linked lists, except that they have random
links at various I<levels> that allow searches to skip over sections
of the list, like so:
4 +---------------------------> +----------------------> +
| | |
3 +------------> +------------> +-------> +-------> +--> +
| | | | | |
2 +-------> +--> +-------> +--> +--> +--> +-------> +--> +
| | | | | | | | |
1 +--> +--> +--> +--> +--> +--> +--> +--> +--> +--> +--> +
A B C D E F G H I J NIL
A search would start at the top level: if the link to the right
exceeds the target key, then it descends a level.
Skip lists generally perform as well as balanced trees for searching
but do not have the overhead with respect to inserting new items. See
the included file C<Benchmark.txt> for a comparison of performance
with other Perl modules.
For more information on skip lists, see the L</"SEE ALSO"> section below.
Only alphanumeric keys are supported "out of the box". To use numeric
or other types of keys, see L</"Customizing the Node Class"> below.
=head2 Methods
A detailed description of the methods used is below.
=over
lib/Algorithm/SkipList.pm view on Meta::CPAN
$list = new Algorithm::SkipList();
Creates a new skip list.
If you need to use a different L<node class|/"Node Methods"> for using
customized L<comparison|/"key_cmp"> routines, you will need to specify a
different class:
$list = new Algorithm::SkipList( node_class => 'MyNodeClass' );
See the L</"Customizing the Node Class"> section below.
Specialized internal parameters may be configured:
$list = new Algorithm::SkipList( max_level => 32 );
Defines a different maximum list level.
The initial list (see the L</"list"> method) will be a
L<random|/"_new_node_level"> number of levels, and will increase over
time if inserted nodes have higher levels, up until L</max_level>
lib/Algorithm/SkipList.pm view on Meta::CPAN
each node by setting the L<P|/"p"> and k values:
$list = new Algorithm::SkipList( p => 0.25, k => 1 );
See L<P|/p> for more information on this parameter.
You can enable duplicate keys by using the following:
$list = new Algorithm::SkipList( duplicates => 1 );
This is an experimental feature. See the L</KNOWN ISSUES> section
below.
=item insert
$list->insert( $key, $value );
Inserts a new node into the list.
You may also use a L<search finger|/"About Search Fingers"> with insert,
provided that the finger is for a key that occurs earlier in the list:
lib/Algorithm/SkipList.pm view on Meta::CPAN
$k = $list->k;
Returns the I<k> value.
$list->k( $k );
Sets the I<k> value.
Higher values will on the average have less pointers per node, but
take longer for searches. See the section on the L<P|/p> value.
=item p
$plevel = $list->p;
Returns the I<P> value.
$list->p( $plevel );
Changes the value of I<P>. Lower values will on the average have less
pointers per node, but will take longer for searches.
The probability that a particular node will have a forward pointer at
level I<i> is: I<p**(i+k-1)>.
For more information, consult the references below in the
L</"SEE ALSO"> section.
=item max_level
$max = $list->max_level;
Returns the maximum level that L</_new_node_level> can generate.
eval {
$list->max_level( $level );
};
lib/Algorithm/SkipList.pm view on Meta::CPAN
Returns the initial node in the list, which is a
C<Algorithm::SkipList::Node> (See L<below|/"Node Methods">.)
The key and value for this node are undefined.
=item _first_node
$node = $list->_first_node;
Returns the first node with a key (the second node) in a list. This
is used by the L</first_key>, L</least>, L</append> and L</merge>
methods.
=item _greatest_node
$node = $list->_greatest_node;
Returns the last node in the list. This is used by the L</append> and
L</greatest> methods.
( run in 0.864 second using v1.01-cache-2.11-cpan-39bf76dae61 )