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. Installation Installation can be done using the traditional Makefile.PL or the newer Build.PL methods. Using Makefile.PL: perl Makefile.PL make make test make install (On Windows platforms you should use nmake instead.) Using Build.PL (if you have Module::Build installed): perl Build.PL perl Build perl Build test perl Build install 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"? From WikiPedia : 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.) 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. REVISION HISTORY Changes since v0.31: 0.40 Wed Mar 17 2004 - added Benchmark file to distribution * key_cmp now ignores when key is undefined - _insert returns the value of $node->key_cmp($key) - broke up test cases into separate files - added finger caching to speed up sequential inserts - fixed bugs with values, keys, copy, merge, first_key and next_key methods related to use of search fingers - fixed bug with append method - fixed bug with search fingers: they were not being used - _debug now prints to STDERR * reset method is not called when a new node is added or deleted (which is in accord with documentation) - stub for next method added - List::SkipList::Node ignores invalid and extra arguments - minor optimizations in List::SkipList and List::SkipList::Node - improved speed of _random_level - disabled assertions (for 50% speed improvement!) - inserted corrected comment in README about actual performance in comparison to trees 0.33 Tue Mar 16 2004 - fixed typos in test cases that caused Makefile tests to fail - removed causes of warnings in 01-SkipList.t - replaced explicit package names with __PACKAGE__ placeholder 0.32 Mon Mar 15 2004 - renamed test.pl to t/01-SkipList.t - added Build.PL to distribution - updated README - corrected and updated POD Versions 0.32 and 0.33 were removed from CPAN because of problems found after uploading the modules. 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 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. SEE ALSO See the article "A Skip List Cookbook" (William Pugh, 1989), or similar ones by the author at http://www.cs.umd.edu/~pugh/ which discuss skip lists.