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

61–70 of 82 posts

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

#61

Post by dllthomas »

aaronem wrote: post #57
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.)

It's not just "you've got enough space" - it's only relevant if both operands are in registers already. If they're both in memory, then the xors are entirely redundant (first things you'd have to do is read values into two registers, at which point you can just write it back the other way).

I wouldn't object to seeing it in a critical section in high performance code with substantial register pressure, but ideally it could be inserted by the compiler!

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

#62

Post by mseebach »

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.

> SO has turned into such a turd of a website.

Yeah, not imposing any kind of quality on questions definitely gave Quora a distinct unturdlike quality.

"What are some things that make you really sad?" - real world example from this week's Quora Weekly Digest.

http://www.quora.com/Sadness/What-are-some-things-that-make-...

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

#63

Post by yareally »

mseebach wrote: post #62
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.

> SO has turned into such a turd of a website. Yeah, not imposing any kind of quality on questions definitely gave Quora a distinct unturdlike quality. "What are some things that make you really sad?" - real world example from this week's Quora Weekly Digest. http://www.quora.com/Sadness/What-are-some-things-that-make-...

Being required to register an account with Quora to view that makes me sad :(

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

#64

Post by thedufer »

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?

Most times this comes up on HN, the SE team points to http://www.slant.co/

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

#65

Post by brvs »

yareally wrote: post #63
mseebach wrote: post #62

Earlier quoted context omitted.

> SO has turned into such a turd of a website. Yeah, not imposing any kind of quality on questions definitely gave Quora a distinct unturdlike quality. "What are some things that make you really sad?" - real world example from this week's Quora Weekly Digest. http://www.quora.com/Sadness/What-are-some-things-that-make-...

Being required to register an account with Quora to view that makes me sad :(

Add ?share=1 to the end of the URL:

http://www.quora.com/Sadness/What-are-some-things-that-make-...

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

#67

Post by wcarss »

mseebach wrote: post #62
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.

> SO has turned into such a turd of a website. Yeah, not imposing any kind of quality on questions definitely gave Quora a distinct unturdlike quality. "What are some things that make you really sad?" - real world example from this week's Quora Weekly Digest. http://www.quora.com/Sadness/What-are-some-things-that-make-...

Just a note: Quora tailors the digests on a per-user basis. I'm not certain what the algorithms involved are, but I'd be willing to bet that they use information about what you and your friends spend time reading about in constructing it.

For example, my most recent weekly digest does not have "What are some things that make you really sad?", but does have "What are your favourite quotes from Harry Potter?" -- it often seems to include Harry Potter. Maybe not a very great question, but it does fit my social network's reading interests pretty snugly.

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

#68

Post by Udo »

LinaLauneBaer wrote: post #49
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.

Not only that but SO in general is a rather bad source for programming advice - at least for beginners. What you generally see on SO happening: - Statements are being marked as "correct" even though they did not answer the question. It happens all the time that people as a Cocoa/OS X related question and get a iOS/UIKit answer which is then marked as correct. - Wrong answers are marked as correct all the time. - Ther…

> They add emphasis, reformat my code/paragraphs etc.

That's the reason I left SO while still in my noob phase - they'd make really strange changes, such as adding typos or removing paragraph breaks. And it's obvious why, too: yes, they get points for it and their name is now right next to the answer. I also found they had generally insane amounts of karma. Yeah, I really don't get SO, for lots of reasons.

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

#69

Post by chas »

dllthomas wrote: post #60
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 a…

Exactly. I was trying to avoid any mathematical jargon while describing monoids because they are such general and pervasive structures in programming. Further, being able to construct useful new monoids is crucial for making full use of a finger tree and I didn't want to have someone find an interesting structure unapproachable because they had to walk through an abstract algebra jargon storm in order to understand it. I realize I referenced associativity without describing it, so I didn't quite achieve my goal, but hopefully the examples got the idea across to someone who might otherwise have dismissed it due to the perception that it was too academic and unapproachable.

As an aside, trying to remove the jargon from a definition like this is surprisingly hard and really expands the size of the definition. I think it is still worthwhile to try when writing for a general audience because algebraic structure is everywhere and very useful to recognize for people who are interested in rigorously manipulating abstraction, i.e. programmers.

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

#70

Post by insteadof »

Udo wrote: post #68
LinaLauneBaer wrote: post #49

Earlier quoted context omitted.

Not only that but SO in general is a rather bad source for programming advice - at least for beginners. What you generally see on SO happening: - Statements are being marked as "correct" even though they did not answer the question. It happens all the time that people as a Cocoa/OS X related question and get a iOS/UIKit answer which is then marked as correct. - Wrong answers are marked as correct all the time. - Ther…

> They add emphasis, reformat my code/paragraphs etc. That's the reason I left SO while still in my noob phase - they'd make really strange changes, such as adding typos or removing paragraph breaks. And it's obvious why, too: yes, they get points for it and their name is now right next to the answer. I also found they had generally insane amounts of karma. Yeah, I really don't get SO, for lots of reasons.

No, you don't get any points for making edits unless you're under 2000, and even then it has to be robo-approved blindly by three other users.
Post reply on HN