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

51–60 of 82 posts

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

#51

Post by bluecalm »

Shish2k wrote: post #43
VexXtreme wrote: post #34

I love how the question was locked because "it is not considered a good, on-topic question for this site". It's crazy. Unless an extremely specific concrete answer can be given, a question immediately gets killed. SO has turned into such a turd of a website.

> Unless an extremely specific concrete answer can be given, a question immediately gets killed Isn't that pretty much SO's explicit goal from day one? Complaining about SO not being a site for open discussion is like complaining that HN doesn't cover celebrity gossip.

Well it's not like that. If you tried submitting celebrity gossip here you wouldn't get much traction to put it mildly. On the other hand a lot of blocked questions on SO were very popular, people produced very valuable and detailed answers to them and they (and the questions) got a lot of upvotes. It's clearly a policy of blocking content the community is very interested in. Better analogy would be blocking politics at HN.

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

#52

Post by Blahah »

ocfnash wrote: post #47
ot wrote: post #40

Earlier quoted context omitted.

> Instead of parsing data, it might be better to store it as a blob of some sort with a binary index. This is exactly something I did for JSON, I call it semi-indexing: instead of parsing it into a tree of pointers, I create a succinct representation of the parsing tree, which is orders of magnitude smaller than the original JSON. Construction is much faster than parsing because there are basically no memory allocati…

IMHO, the FM-index deserves to be highlighted. That it is possible to store a string in a compressed format which can answer length-P substring queries in O(P) time (with good constant factors) is quite surprising at first sight. I recently wrote a few words about this here: http://ocfnash.wordpress.com/2014/01/03/dna-of-a-password-di... By the time I finished I decided the whole area was exciting and seems not at al…

A nice application for the FM-index: it has massively accelerated alignment of short DNA sequences against large databases.

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

#53

Post by teddyh »

Even though they are included in the GNU C library, most people do not seem to know about Obstacks:

An "obstack" is a pool of memory containing a stack of objects. You can create any number of separate obstacks, and then allocate objects in specified obstacks. Within each obstack, the last object allocated must always be the first one freed, but distinct obstacks are independent of each other.

Aside from this one constraint of order of freeing, obstacks are totally general: an obstack can contain any number of objects of any size. They are implemented with macros, so allocation is usually very fast as long as the objects are usually small. And the only space overhead per object is the padding needed to start each object on a suitable boundary.

https://www.gnu.org/software/libc/manual/html_node/Obstacks....

Sure, they’re not very interesting, but the point is that you get them for free in the GNU C standard library.

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

#54

Post by profquail »

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…

It is a good question, but it would have been better suited for the "CS Theory" StackExchange site. For example, a similar question was asked there:

http://cstheory.stackexchange.com/questions/1539/whats-new-i...

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

#55

Post by sherwin »

jzwinck wrote: post #36
joelthelion wrote: post #35

Earlier quoted context omitted.

Speaking of which, is there a good alternative site for questions that are forbidden on SO?

There are other sites in the StackExchange network like Programmers and Code Review and some others for math and other things. But I'm not sure which site (SE or otherwise) would be the best for this particular topic.

Probably the CS stackexchange (http://cs.stackexchange.com/), or CStheory (http://cs.stackexchange.com/). Unfortunately, neither are anywhere near as popular as StackOverflow, so the chances of getting a good discussion are lower.

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

#56

Post by kintamanimatt »

joelthelion wrote: post #35
VexXtreme wrote: post #34

I love how the question was locked because "it is not considered a good, on-topic question for this site". It's crazy. Unless an extremely specific concrete answer can be given, a question immediately gets killed. SO has turned into such a turd of a website.

Speaking of which, is there a good alternative site for questions that are forbidden on SO?

Perhaps Quora?

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

#57

Post by aaronem »

abcd_f wrote: post #42

XOR linked list: http://en.wikipedia.org/wiki/XOR_linked_list It's a double-linked list with just one link per node. However, to start traversing it you have to know at least two adjacent nodes. PS. May not be useful per se, but interesting nonetheless.

The XOR swap is interesting, too. But I wouldn't want to see one in code someone wrote today, and which wasn't targeted at an embedded platform -- and a heavily constrained embedded platform, at that. (MSP430? Sure. ARM Cortex-M3? You've got enough space to do it properly.)

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

#58

Post by jberryman »

VexXtreme wrote: post #34

I love how the question was locked because "it is not considered a good, on-topic question for this site". It's crazy. Unless an extremely specific concrete answer can be given, a question immediately gets killed. SO has turned into such a turd of a website.

You forget your tag. Its pretty obvious that the success of SO as a Q/A site is thanks to all the mechanisms in place to make it not another shitty forum. And its actual function as a Q/A site has far more value than a handful of cute lists.

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

#59

Post by dllthomas »

bazzargh wrote: post #12

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)

I second the plug for Purely Functional Data Structures - brilliant stuff!

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

#60

Post by dllthomas »

chas wrote: post #31

I'm happy to see finger trees got mentioned. Finger trees[0] are extremely useful and general data structure that can be used to implement persistent sequences, priority queues, search trees and priority search queues. (Haskell's Data.Sequence[1] uses specialized 2-3 finger trees internally) They can form the basis of all sorts of interesting custom structures by supplying the appropriate monoid[3], but this does mak…

"In addition, it must have an element that can combine with any other element and result in the other element."

Aka, an identity element.

Monoids that have inverses (that is, every element has another element that, when combined, produces the identity element) are "groups". Of the examples you gave:

"Strings over composition" does not form a group - there's nothing you can concatenate with a non-empty string to get an empty string.

"Integers over addition" does form a group. The inverse of x is -x.

"Natural numbers over max" is not a group. Once you get above 0 you cannot get back to it just by applying max.

"Booleans over and" is not a group. Once you have false you can't get back to true.

"Functions over composition" is not a group. Many functions have inverses, but some do not. If you restrict the set to "functions with inverses" then you do have a group.

Post reply on HN