comparison vs map

Question

comparison vs map

jojo05 opened this issue 8 years ago · 3 comments

Hi,

It would be useful to also include a map in the comparison, to understand at what point the skiplist provides faster inserts
Thanks

Answer 1 · 2017-04-14T19:18:54.000Z

Will look into adding more insightful benchmarks to record. For now, you can imagine that the insert timing would look the same at each position as it would in the "worst case inserts" for a list of that size, which I've already recorded.

Answer 2 · 2017-04-15T11:44:55.000Z

Hi,
I apologize for not explaining better. I am interested in using a skip-list as a dictionary (string->int) for fast inserts O(log(n)) vs O(n*log(n)) for map.

Does your skip-list or any other support string keys? If not, what other structure do you suggest. I might also check ART (adaptive radix tr.)

Thanks

Answer 3 · 2017-04-15T20:38:54.000Z

I note the accepted key types in the README. The best of the bunch for ease of use, accepting strings as keys, and reliable speed is https://github.com/huandu/skiplist -- look at the tests to see how to use string->int.