2 ms·
> One thing that bothers me about skiplists is having a static number of levels, which will either be too few or too many for most situations. You should be in
by tsumnia 5y ago
> One thing that bothers me about skiplists is having a static number of levels, which will either be too few or too many for most situations.
You should be inserting a new level whenever you add an element to the highest. I like skiplists, they're fun to teach but I'd say the part that irks me the most is their O(log n) is through "amortization", or sometimes its a long search, sometimes its a short search, so it "averages out in the end".
- lqr 5y agoGeometrically-growing arrays (std::vector) and hash tables also have amortized O(1) insertion complexity. They are some of the most widely-used data structures of all. I agree that amortized guarantees can be a problem in certain applications, but it seems that programmers are happy to accept them most of the time.
- tsumnia 5y agoTrue, I think it's more that skiplists are both amortized and (taught to) expand randomly unless you dig deeper into optimizing the structure. I think with regard to hash tables, the annoyance of hashing is overlooked due to the simplicity of the algorithm. From a purely academic side, its difficult to explain why you'd use one data structure over another. We can say THIS structure has an O() for THIS operation, but its often at the tradeoff of another operation. Then it comes down to ease of implementation, where I'd say skiplists have a harder time explaining vs. hashing.