| Robert Rothenberg 2004-06-03, 7:08 pm |
| Version 0.63 of List::SkipList has been uploaded to PAUSE, and should
soon appear on a CPAN mirror near you.
NAME
List::SkipList - Perl implementation of skip lists
REQUIREMENTS
Perl 5.6.1 is required.
The following non-standard modules are required:
enum
Carp::Assert is no longer required. However, the assertions can
be uncommented for debugging.
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.(*)
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.60:
0.63 Fri May 28 2004
- The default value of P is now 0.25, which appears to yield
better results in tests.
* renamed _random_level to _new_node_level
- SIZE_THRESHOLD/SIZE_LEVEL now decrease with deletions
- additional minor optimizations and code cleanup
- optimizations of Header and Null node types
- updated tests
- Benchmark: re-commented-out delete test for Tree::RedBlack
(which was accidentally uncommented in v0.62)
0.62 Tue May 18 2004
- fixed typo in (commented-out) assertion
- additional minor optimizations and code cleanup
- updated tests
- corrected README
0.61 Mon May 17 2004
* find no longer returns a finger in array context
* header is now a special subclass of List::SkipList::Node
- added special Null subclass of Header
- added null() method to return global null node
- a lot of minor code optimizations
- added comments
- maximum level of new nodes changed so that it is based on size
of list
- updated Benchmark.txt file
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.
|