Skip List

[markgo]

A skip list in Lua. There was another one in the LOVE wiki, but I've made my own. It's twice as fast as the other one! A benchmark is included which also compares it to binary/skew heap. Performs almost as well as them too! One thing about this skip list is that it can grow so it you don't need to specify a "set size" for better performance.

What can you do with a skip list? Oh a bunch of things... I'm currently trying to use it for handling monster priorities (priority queue) in a turn based game. Enjoy!

https://github.com/markandgo/skip-list

[ncarlson]

Very cool. Thank you.

[mickeyjm]

Could you please explain what a skip list is/does? I tried looking on wikipedia but after the first line I was completely lost.

[Roland_Yonaba]

Could you please explain what a skip list is/does? I tried looking on wikipedia but after the first line I was completely lost.

To put it in a nutshell, skip list is, simply said, a data structure in hich you keep a collection of elements in a specific order.
Let's suppose you want to deal with a table of highscores. You need the higher value to be at the top, and the lowest value at the bottom.

Code: Select all

local scores = {100, 20, 5, 0}

Let' say a new player ends up the game, and come up with a new score of 19. Obviously, he reached the hall of fame. And therefore, you have to register this value.

Code: Select all

local newScore = 19
table.insert(scores, newScore)

Problem is, the score table is no longer ordered.

Code: Select all

for _, score in ipairs(scores) do print(score) end
-- 100
-- 20
-- 5
-- 0
-- 19

So, after adding a new score, you need to sort the table again. Fair enough, you can implement any trivial sorting algorithm, or use Lua's standard table.sort function, which (FYI) uses internally a similaring algorithm (a clever one though).

Code: Select all

table.sort(scores, function(a,b) return a>b end) -- sorts from highest to lowest values
for _, score in ipairs(scores) do print(score) end
-- 100
-- 20
-- 19
-- 5
-- 0

The problem is, even though it works for most cases, sorting those elements is quite costful, especially if you have lots of elements in your collection.
Remember you will need to sort the colection again right after adding a single new element in it.
Moreover, sometimes, you do no necessarily need to keep the whole collection on order, you just need to pop out the highest (or the lowest) element from the collection quickly.

So it implies that if you have a clever way to store those elements in a table (this is where it becomes a real "data structure"), you can figure out, in a minimum number of operations, what is the next highest (or lowest) element in this collection and retrieve it. Or, you can sort the whole collection making a reduced number of elementary permutations.

Skip lists, binary heaps, skew heaps and many others follow these rules, or are meant for similar purposes.

One of the most common use case for skip list is z-ordering.
Here is a couple of interesting notes on both topics for further reading.

• skip list implementation
• Skip list and drawing order (on love2d wiki)
• Z order in top-down 2d games

Hope this helps.

@Markgo:
I do love those kind of little experiments. Awesome.
I might send some pull request later on for more in-depth tests on performance.

[mickeyjm]

-snip-

Thank you, that was a very clear explanation.
Strangely enough I just ran into a performance issue in a project of mine where it needs to sort elements very quickly so this seems ideal.

EDIT: My god these are faster, I went from 20fps to 70fps as soon as I implemented skiplist instead of normal sorting

[Roland_Yonaba]

-snip-

My god these are faster, I went from 20fps to 70fps as soon as I implemented skiplist instead of normal sorting

Well then, you got the whole point.
Side note, while I was working on my pathfinding library (Jumper), I needed to speed-up things at some point when performing the search with Astar.
Internally, Astar keeps a list of all nodes visited during the search, tagging each node with a specific cost.
Therefore, on each step of iteration, the algorithm needs to figure out what node is the best (skimming trough this list) and expand the search from this very node.
For the sake of implementation, I started with a naive approach in which, after updating all nodes cost, I would just sort the whole table. The the best node bubbles at the top. I as just fine, but slow when the seach space was hage. Then, I came accross a paper explaining how Astar could be made faster using binary heaps (a very interesting one, actually). Then I implemented a general pupose binary heap library (for testing), that I included later on in Jumper. And well, the benefit in terms of speed was quite noticeable.

[T-Bone]

What's so nice about skip lists, in comparison to other data structures with similar speeds, is its simplicity. It's very easy to write yet has some very nice properties (like making it easy to balance memory usage vs speed depending on the use case).

[markgo]

Hey all. There was a bug with deleting and finding keys/values. All is fixed now . Good luck.

[markgo]

I've changed the license to zlib. Also updated the code with some new methods since the last post. It doesn't seem like LuaJIT 2.0.2 plays nicely with my skip list (hard crash) so you've been warned!

[Helvecta]

So much for while loops and table.insert!