Jup, that's me. (The avatar is kind of a give-away. ;))
@Lembik Well, that's not an answer, now is it? (Which is troublesome for your question as per site rules.)
The obvious things to check are more precise analyses. Do skip-lists maybe have only 0.8 the expected comparisons for searches? Are they easier to maintain? Do the need fewer random bits (which are expensive)?
For instance, treaps need a uniform random number in [0,1] of arbitrary precision element. Skip lists make do with two random bits per element (in expectation). That alone may be a bit selling point for practical applications, both in terms of "where do I get a suitable random source" and "how long does that take".
But that's impossible to determine without fixing the "implementations" at least.
@Lembik No, I mean when elements are inserted/deleted. IIRC, you only repointer skip list towers (in expection two pointers). In treaps, you have to re-heapify (at most two rotations upwards in expectation -- may involve more than two pointers, though!).
@Lembik Interesting. You should definitely cite those in your question!
@Lembik Answers that just list things that may be relevant would be bad answers. Since your question admits only such in its current form, it's a bad question (for the platform; it's a good question to ask, definitely).
@Raphael If you will allow me to slightly critical, I feel that you are trying to find reasons why my question is no good rather than trying to find helpful ways to answer it
I feel very confident that there are lots of useful answers one could give
@Lembik I'm trying to help you improve the question and make it answerable on this platform. Only then can we think about answers.
@Lembik Maybe. But that's not how the platform Stack Exchange works. Brainstorming is for chat or whiteboards. (Note that I did give you several answers above!)
As a moderator, though, it's my job to make sure the site works. And it does not work with brainstorming-type questions.
@Lembik How many hours have you spent on the site? Is your impression that it does not work well? (Note that I have not taken any moderative action; I have only commented.)
@Lembik ad edit: I maybe misspoke. I mean references as in scientific studies/articles. These resources are basically programmers making bold claims.
(That said, disclaimer: if you take issue with how the site is being run -- in the sense that you think we violate SE policy -- you should start a discussion Computer Science Meta.)
Larry Wasserman has a recent post where he talks about the "p-value police". He makes an interesting point (all emphasis mine) (the premise in italics that I added, and his response below it):
The most common complaint is that physicists and journalists explain
the meaning of a p-value inco...
@Lembik I agree. Keep in mind that they don't have to deal with lots of offtopic and homework questions the way we do -- they can be more lax across the board.
The purpose of this post is to aggregate several templates for comments useful for the daily moderating of the CS site, e.g., informing the user (usually, new user) when their question is off-topic / un-clear / etc, suggesting wht they should do next.
One should be able to copy-paste a comment f...
After "obviously unsuited", we enter the category of "d'uh, but if you insist...". The latter typically get questions as response. Vampires don't find that useful, of course, but others usually do. At least that's my impression.
What is Stack Overflow's long-term solution for the Help Vampire problem?
Quote from article follows:
Identifying Help Vampires can be tricky, because they look like any ordinary person (or Internet user, whichever is lesser). But by closely observing an individual's behavior using this hand...
@Lembik, I think Raphael has some valid points. I think his comments are constructive. He is suggesting alternative questions you would ask that would be a good fit for this site format, and would contribute to your eventual goal. For instance, you could ask a question like "Skip lists take O(log n) time for operations X,Y,Z. What are the constants in that running time?" (after doing research on this question and showing your research in the question)
Sometimes if you want to learn about some broad topic X, the best way to use this site is not to ask a broad question about X, but to ask a series of focused questions that will each contribute to your understanding of X.
I also agree with Raphael that it might be helpful to edit your question to include what research you've done.
@Raphael, I'm not sure it's true that random bits are super-expensive. Some PRNGs are pretty fast. I realize I'm being hand-wavy and not quantitative. Getting a random byte is slower than doing a single addition or table lookup, but maybe not vastly so -- for instance, I expect it's possible to get random numbers at close to memory bandwidth, using techniques like built-in AES-NI instructions or by using lower-quality PRNGs like LCPRNGs.
That's probably good enough for the needs of randomized data structures: most of them probably don't require super-high-quality randomness.
@D.W. True; a little bias should result in also a little inbalance, intuitively.
I think we need a list of questions that seem incredibly deep to people without CS intuition/education, but are incredibly shallow with such. Recent example:
I am looking for a better explanation (research level, papers) to answer:
Why translating a program from one high-level programming language directly into another is difficult?
Note: When I say difficult I don't mean "hard" - i.e. I am not taking about computational complexity here simply beca...
We have had quite a few of these, and I think they highlight beautifully why formal CS education adds a non-trivial set of competences over mere software development skill.
(Though, granted, these questions are often shallow because they are not posed right; they often hide deeper questions.)
Larry Wasserman has a recent post where he talks about the "p-value police". He makes an interesting point (all emphasis mine) (the premise in italics that I added, and his response below it):
The most common complaint is that physicists and journalists explain
the meaning of a p-value inco...
What is Stack Overflow's long-term solution for the Help Vampire problem?
Quote from article follows:
Identifying Help Vampires can be tricky, because they look like any ordinary person (or Internet user, whichever is lesser). But by closely observing an individual's behavior using this hand...
I am looking for a better explanation (research level, papers) to answer:
Why translating a program from one high-level programming language directly into another is difficult?
Note: When I say difficult I don't mean "hard" - i.e. I am not taking about computational complexity here simply beca...
