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, including search and selecting ordered ranges.
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)
=> 2Contributing
- 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