DSkipList
#What is a skiplist? A skiplist is similar to a linked list, where every node holds the next node. In a skiplist, some of the nodes are connected to more distant nodes. This allows you to jump quickly through ordered nodes, acheiving O(log (n)) or better performance for any operation.
Warning: This software is alpha. If you find a bug, please file the issue on github. Master contains incremental changes and may be broken, but the gem is usably stable.
This is a ruby skiplist much faster than the ruby skiplist gem here https://github.com/metanest/ruby-skiplist Benchmarks below
Installation
Add this line to your application's Gemfile:
gem 'dskiplist'
And then execute:
$ bundle
Or install it yourself as:
$ gem install dskiplist
Usage
require 'dskiplist'
list = DSkipList.new
#anything comparable is a valid key, just keep the type consistent. Any value is valid
list[1] = 'dog'
list[2] = 'cat'
#or
list.insert_hash Hash[3 => 'fish']
list[1]
=> 'dog'
list.to_a
=> ['dog', 'cat', 'fish']
list.to_h
=> {1=>"dog", 2=>"cat", 3=>"fish"}
list.each {|e| puts e.reverse}
=> god
=> tac
=> shif
list.count
=> 3
list.clear
=> empty list
Benchmarks
Other list: https://github.com/metanest/ruby-skiplist
this list insert 10000 elements time:
0.150000
other skip list insert 10000 elements time:
3.540000
this list search 10000 elements time
0.080000
other list search 10000 elements time
2.480000But slower than Ruby's hash
user system total real
List insert million elements: 23.680000 0.150000 23.830000 ( 25.223663)
Hash insert million elements: 2.740000 0.060000 2.800000 ( 2.949170)
List search 10000 elements 0.140000 0.000000 0.140000 ( 0.169945)
Hash search 10000 elements 0.050000 0.000000 0.050000 ( 0.104777)
Ok, so why use this instead of hash? Order
>> list[1] = "duck"
>> list [2] = "goose"
>> list[3] = "quail"
>> list[4] = "pidgin"
>> list.smallest
=> "duck"
>> list.largest
=> "pidgin"
#get your elements in order
>> list.to_a
=> ["duck", "goose", "quail", "pidgin"]
#or in a range
>> from = 1
>> through = 3
#0 is the base layer of the list. It contains all elements. default 0
>> layer = 0
#limit return size if desired
>> limit = nil
>> list.to_a(from, through, limit, layer)
=> ["goose", "quail"]
#note that "duck" was omitted. The range does not include the first element.
#You can also use nonexistent node keys like 1.5
#with a start point, no endpoint, and a limit:
>> list.to_a(2, nil, 2)
=> ["quail", "pidgin"]
>> list.to_a(nil, 3, nil)
=> ["duck", "goose", "quail"]
#or count the elements between two values (+1 because endpoint is counted) from 1 to 3
>> list.count(from, through)
=> 2
Contributing
- Fork it ( http://github.com//dskiplist/fork )
- Create your feature branch (
git checkout -b my-new-feature) - Commit your changes (
git commit -am 'Add some feature') - Push to the branch (
git push origin my-new-feature) - Create new Pull Request
ToDo:
- Jruby multithreading and locking with mutexes for multi-core support.
- Lazy operations. For now you can just do them yourself by using find_node to get your start point and calling forward[0] to get the following nodes in O(1) time
- considering making count O(1) instead of O(log n) by just keeping track of the size
