| Robert Rothenberg 2004-03-30, 6:31 am |
|
List::SkipList has been released and should appear on a CPAN mirror
near you within 24 hours. http://search.cpan.org/~rrwo/List-SkipList/
NAME
List::SkipList - Perl implementation of skip lists
REQUIREMENTS
Perl 5.6.1 is required.
"Carp::Assert" is used for validation and debugging. (The assertions can
be commented out if the module cannot be installed.) Otherwise standard
modules are used.
SYNOPSIS
my $list = new List::SkipList();
$list->insert( 'key1', 'value' );
$list->insert( 'key2', 'another value' );
$value = $list->find('key2');
$list->delete('key1');
DESCRIPTION
This is an implementation of skip lists in Perl. What are "skip
lists"?
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 particular implementation may not necessarily be faster or
use less space, but in superficial testing, it does appear to be a
reasonably faster substitute for some tree modules. See the
included Benchmark.txt file for comparisons with other Perl
modules.
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
A search would start at the top level: if the link to the right
exceeds the target key, then it descends a level.
More information is available in the module documentation.
(*) Bill Pugh, inventor of skip lists. Quoted from WikiPedia
<http://en.wikipedia.org/wiki/Skip_list>
REVISION HISTORY
Changes since v0.42:
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
- various optimizations to List::SkipList and *::Node
- added comparison to Tree::RedBlack in Benchmark.pl
- minor changes to _search method
- added Benchmark.pl script for generating benchmarks in distro
- redesigned benchmarking script
A detailed revision history is in the Changes file included with
this distribution.
CAVEATS
Skip lists are non-deterministic. Because of this, bugs in programs
that use this module may be subtle and difficult to reproduce without
many repeated attempts.
AUTHOR
Robert Rothenberg <rrwo at cpan.org>
LICENSE
Copyright (c) 2003-2004 Robert Rothenberg. All rights reserved. This
program is free software; you can redistribute it and/or modify it
under the same terms as Perl itself.
|