Add Skip Lists #60

New issue

Closed

opened 2017-07-16 20:45:28 +00:00 by sean-public · 4 comments

sean-public commented

2017-07-16 20:45:28 +00:00

(Migrated from github.com)

I think it would be useful to have skip lists included in the GoDS collection.

I previously studied the publicly available Go skip list implementations and found some issues with each. I then created a very fast, threadsafe skip list of my own (under MIT license). I believe it is one of the best foundations to work from for this data structure and can easily be integrated into GoDS.

If you like, I can work on a pull request to include my skip list implementation with the appropriate interface. First, I wanted to make sure this would be useful and to ask what specific details I should watch for / include to ensure smooth compatibility.

I think it would be useful to have skip lists included in the GoDS collection. I [previously studied the publicly available Go skip list implementations](https://github.com/sean-public/skiplist-survey) and found some issues with each. I then created [a very fast, threadsafe skip list of my own](https://github.com/sean-public/fast-skiplist) (under MIT license). I believe it is one of the best foundations to work from for this data structure and can easily be integrated into GoDS. If you like, I can work on a pull request to include my skip list implementation with the appropriate interface. First, I wanted to make sure this would be useful and to ask what specific details I should watch for / include to ensure smooth compatibility.

👍 7

emirpasic commented

2018-09-20 17:00:22 +00:00

(Migrated from github.com)

Any new data structure is a good addition to GoDS, so I might use parts of your code as inspiration to create SkipLists.

Regarding thread-safety, GoDS tries to keep its hands clean from that problem and that should be handled on another abstaction level with mutex or whichever... repeat #68 #84 (also noted in the documentation and comments)

Any new data structure is a good addition to GoDS, so I might use parts of your code as inspiration to create SkipLists. Regarding thread-safety, GoDS tries to keep its hands clean from that problem and that should be handled on another abstaction level with mutex or whichever... repeat #68 #84 (also noted in the documentation and comments)

emirpasic commented

2018-09-24 16:52:56 +00:00

(Migrated from github.com)

@sean-public i took a brief look at your implementation and testing various implementations. i think you have done a good job and would like to move from there.

however, two things i would change due to nature of GoDS which despite trying to stay un-opinionated, things took a path.

i would remove the locking mechanisms as pointed in the documentation and frequently answered questions, it is something i believe that should be easily handled on a higher level with rw/mutexes.
it is under the MIT license. although MIT and BSD are somewhat compatible, would it be possible to convert your MIT to BSD. i am honestly really not dogmatic about any of the two, but would not like to confuse others with having two licences in GoDS. note that i am also not a legal expert on the issue. in that case i would simply attach your BSD licence to https://github.com/emirpasic/gods/blob/master/LICENSE as done with the AVL tree implementation.

do these two suggestions sound reasonable?

@sean-public i took a brief look at your implementation and testing various implementations. i think you have done a good job and would like to move from there. however, two things i would change due to nature of GoDS which despite trying to stay un-opinionated, things took a path. 1. i would remove the locking mechanisms as pointed in the documentation and frequently answered questions, it is something i believe that should be easily handled on a higher level with rw/mutexes. 2. it is under the MIT license. although MIT and BSD are somewhat compatible, would it be possible to convert your MIT to BSD. i am honestly really not dogmatic about any of the two, but would not like to confuse others with having two licences in GoDS. note that i am also not a legal expert on the issue. in that case i would simply attach your BSD licence to https://github.com/emirpasic/gods/blob/master/LICENSE as done with the AVL tree implementation. do these two suggestions sound reasonable?

👍 2

tooooolong commented

2020-02-29 08:23:38 +00:00

(Migrated from github.com)