Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

What are the lesser known but useful data structures?

stackoverflow.com

Post reply on HN
Print view View original

11–20 of 82 posts

Re: What are the lesser known but useful data structures?

#11

Post by siganakis »

tikhonj wrote: post #6

There's a whole set of interesting data structures that are not very well known: succinct data structures[1]. The idea is simple: we want to store data in a compressed form, but also perform certain operations quickly without uncompressing. These can be very useful for certain applications. The article on "Cramming 80,000 Words into a JavaScript File"[2] is a nice example. It shows you how you can store a compressed…

The problem with succinct data structures (and wavelet trees especially, but also rank-select dictionaries) is that while they have excellent performance characteristics when you look at them from a theoretical perspective, they tend to perform relatively poorly in practice.

This seems to be due to how much memory is accessed when checking a single bit, and the difficulty in predicting branches.

Of course it could just be that all my implementations have sucked, but even in playing around with libcds[1] didn't yield the kind of performance expected.

If anyone knows of a fast implementation of Wavelet Trees, I'd love to see it.

[1] https://github.com/fclaude/libcds

Re: What are the lesser known but useful data structures?

#12

Post by bazzargh »

It's not highlighting one thing, but Chris Okasaki's book on Purely Functional Data Structures, and this brilliant top answer to a question about functional data structures published since the book will keep you in reading material for a while: http://cstheory.stackexchange.com/a/1550

(it was all 'lesser known' to me when I started using haskell not so long ago)

Re: What are the lesser known but useful data structures?

#13

Post by YZF »

kintamanimatt wrote: post #10

> This question exists because it has historical significance, but it is not considered a good, on-topic question for this site , so please do not use it as evidence that you can ask similar questions here. Yet it's one of the best questions on SO. Something's very wrong with SO if this isn't considered a good, on-topic question for a programming Q&A site.

How is that one of the best questions on SO? There is always someone who wants SO to be what they want it to be. I'm not saying everything is perfect in SO but I think the standard answer is that if you want a site that is about subjective discussions related to programming you should make one...

Re: What are the lesser known but useful data structures?

#15

Post by kintamanimatt »

YZF wrote: post #13
kintamanimatt wrote: post #10

> This question exists because it has historical significance, but it is not considered a good, on-topic question for this site , so please do not use it as evidence that you can ask similar questions here. Yet it's one of the best questions on SO. Something's very wrong with SO if this isn't considered a good, on-topic question for a programming Q&A site.

How is that one of the best questions on SO? There is always someone who wants SO to be what they want it to be. I'm not saying everything is perfect in SO but I think the standard answer is that if you want a site that is about subjective discussions related to programming you should make one...

How is it not one of the better questions on SO? It's educational, it's on-topic, it's more cerebral than the usual questions about jQuery, it has high quality answers, the question itself is as clear as day, it's interesting, and it's very popular in terms of views and upvotes.

There's a degree of opinion in most answers anyway especially as there's often multiple ways to do the same thing and every answerer will have a preference of some kind. I don't necessarily see this one as a particularly subjective discussion anyway, or why you think I'm trying to make SO be something it's not. In any event, why are marginally subjective discussions are a horrible thing anyway in a Q&A site?

Re: What are the lesser known but useful data structures?

#18

Post by bd_at_rivenhill »

YZF wrote: post #13
kintamanimatt wrote: post #10

> This question exists because it has historical significance, but it is not considered a good, on-topic question for this site , so please do not use it as evidence that you can ask similar questions here. Yet it's one of the best questions on SO. Something's very wrong with SO if this isn't considered a good, on-topic question for a programming Q&A site.

How is that one of the best questions on SO? There is always someone who wants SO to be what they want it to be. I'm not saying everything is perfect in SO but I think the standard answer is that if you want a site that is about subjective discussions related to programming you should make one...

SO has critical mass which would be difficult to replicate in a new site; remember that it was started by Jeff Atwood and Joel Spolsky, who were already established bloggers. "Make your own SO for subjective discussions" would be a good suggestion for someone who already has a large online following, but not for a general programmer.

I have yet to see a good argument why these types of questions detract from the main site and asked on a separate site (http://programmers.stackexchange.com/). If the problem is cluttering up search results with opinions, then they could be marked as "subjective" and people could be given the option to avoid these results.

Re: What are the lesser known but useful data structures?

#19

Post by alanctgardner2 »

kintamanimatt wrote: post #15
YZF wrote: post #13

Earlier quoted context omitted.

How is that one of the best questions on SO? There is always someone who wants SO to be what they want it to be. I'm not saying everything is perfect in SO but I think the standard answer is that if you want a site that is about subjective discussions related to programming you should make one...

How is it not one of the better questions on SO? It's educational, it's on-topic, it's more cerebral than the usual questions about jQuery, it has high quality answers, the question itself is as clear as day, it's interesting, and it's very popular in terms of views and upvotes. There's a degree of opinion in most answers anyway especially as there's often multiple ways to do the same thing and every answerer will ha…

The problem is that SO is not for entertainment. It's not even really for education. They (the site's operators) want it to be an injective mapping of google queries to solutions. You don't need to become a better programmer. You need to keep coming back to SO to ask more questions. On the other side they need to supply a steady stream of middling difficulty questions, because everyone isn't John Skeet.

Nobody is going to be working on a project and say "My client requires the use of obscure data structures, better Google some!". You can bash the multitude of jQuery questions, but having worked in a variety of settings, some people need things spelled out for them. You need a lot of simple questions with alternate wordings, different permutations of libraries, etc. Even though you can generalize these answers, they're hard to find from Google, and a lot of people will read "Undefined variable foo? Nonsense, my undefined variable is baz. Better open a new ticket".

Re: What are the lesser known but useful data structures?

#20

Post by krisgee »

I was going to say Trie but it was the first response to the SO thread so I guess it wasn't as little known as I thought.

I implemented it because I was making a game that had scrabble elements in it and needed to check ahead to see if the player had a word that could still take letters (a prefix) or if they'd hit a dead end. Fit the whole SOWPODS into a remarkably tiny space with millisecond lookups. Probably my favourite part of the project.

Post reply on HN