Talk:Skip list

From Wikipedia, the free encyclopedia

Contents 1 Adversarial User 2 Adversarial User Revisited 3 Style 4 ICS 23 5 Skip Lists with two pointers 6 Removed a reference that disputes the quote in the History section

[edit] Adversarial User

Why is the author concerned about 'adversarial users' messing with his data structures? Security through obscurity is not very secure anyway. Doesn't this discussion of security of data structures belong in a separate article?

The "adversarial user" is a hypothetic user (think, evil demon), that knows exactly the order in which to execute operations on a data structure that would incur the worst possible run time of the execution of those operations. It is a common technique in algorithm analysis to think of your algorithm working against such an adversarial user. Sancho McCann 22:00, 10 February 2007 (UTC)

See Adversary_(online_algorithm) and Competitive_analysis_(online_algorithm). Sancho McCann 01:53, 11 February 2007 (UTC)

[edit] Adversarial User Revisited

NO! The author is not discussing data security here and has made no mention of data security. The author is discussing the possibility that a user might, accidentally or otherwise, create a worst-case scenario for the data structure's performance. The "adversarial user" is a mnemonic mechanism for the programmer to keep in mind as he programs or designs an algorithm. This is a performance issue and not a security issue as you have misconstrued. Note "worst possible run-time" in the article text.

The above links didn't really help understand why randomizing the indexing would have any beneficial effects. As far as I can see, the randomization only serves to eliminate predictable performance, instead of affecting worst-case complexity. That is to say, the point of the randomization seems to be to vary the worst-case use case such that this data structure is not always inferior to a competing one given that use case, at the cost of also varying best-case use case performance. Did I misunderstand something, or is the point really to just flatten the performance variance probabilistically? 82.203.161.17 (talk) 15:11, 4 October 2007 (UTC)

Having now read the original article, it seems that that is indeed the case. However, the original motivation for random assignment of the level j nodes is avoiding a costly "rebalancing" step, and the fact that no set input sequence consistently produces worst-case behavior is just a byproduct. 82.203.161.17 (talk) 12:27, 6 February 2008 (UTC)

[edit] Style

Wikipedia's manual of style has a section on writing in mathematics articles that I think applies here (see Wikipedia:Manual_of_Style_(mathematics)#Writing_style_in_mathematics). If we could remove the conversational style and have the article read more like an encyclopedia rather than a textbook, it would be an improvement to this article. Sancho McCann 22:02, 10 February 2007 (UTC)

I attempted to remove the conversational tone from the article 192.17.161.202 23:38, 17 October 2007 (UTC)

[edit] ICS 23

The part about Jacobson could use a rewrite.

[edit] Skip Lists with two pointers

I wonder if it's possible to implement these cute Skip Lists using only TWO fields to navigate in it, i.e. "below" and "next", instead of the usually suggested FOUR including "above" and "before"...? However, I'm not sure how to handle the tower construction if one can't get levels up and nodes before a particular node. How about removing a node? Again, all the tower nodes need to be isolated, isn't that so? How do we do this, using only a "next" and a "below" fields? Could any expert comment on this?

Epsilon1 20:34, 1 April 2007 (UTC)

Read the original paper; N pointers are required for each node, all pointing "forward" different amounts in the list. No "backward" or "up" pointers are used or needed. If for some reason one wanted to traverse backwards in the list, "backward" pointers would solve that problem. However, since this behavior is not usually needed, it's a lot of storage to use on something that won't be used a lot.

[edit] Removed a reference that disputes the quote in the History section

I removed the linked page because it is based on a bad implementation and bad information. Nowhere does it say what the skip average was and why it would use a height of 24 nodes or how these were allocated. A height of 24 for 6 million entries is ridiculous. For that many items, a height of 8 is more than sufficient. Depending on the allocation scheme, this will greatly reduce the extra memory and reduce the amount of comparisons done. I've actually tested skip lists extensively and can tell you that in C++ at least, skip lists are exactly on par and occasionally faster with the map template for speed and use about the same amount of memory. Skip lists memory usage and speed can be tweaked according to your need and can reproduce a map quite easily. -- V —Preceding unsigned comment added by 74.106.242.11 (talk) 01:17, 27 September 2007 (UTC)