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

71–80 of 82 posts

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

#71

Post by dllthomas »

chas wrote: post #69
dllthomas wrote: post #60

Earlier quoted context omitted.

"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 i…

I agree; my "aka" wasn't meant as criticism. It's easy to get lost in the longer definitions, so I was just restating it directly in the hopes that one or the other - or the combination - will be clear to most people.

Though I'm not sure "abstract algebra jargon storm" properly describes use of "associative" and "identity" - I remember learning about the "associative property of multiplication" and such in elementary school and my wife confirms she had similar experience.

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

#72

Post by dllthomas »

serge2k wrote: post #26

It's mentioned in the link, but circular/ring buffers. I've been grappling with decoding/playing back an audio stream and wouldn't have gotten it working if I hadn't found out about boosts lockfree ring buffer.

Recently I learned that if you're using a ring buffer for message passing, the clflush opcode (after sending and after receiving) can dramatically reduce cache misses.

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

#73

Post by statusgraph »

WWKong wrote: post #27

Me and my friend were pretty serious about creating a new data structure called "drum". A drum is a one way store. You write to it but can't read from it. We put it off till we figured a practical use.

An append only log? The value of writing data is that you can read it, otherwise your structure is semantically equivalent to not writing at all.

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

#74

Post by LinaLauneBaer »

insteadof wrote: post #70
Udo wrote: post #68

Earlier quoted context omitted.

> 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.

No matter why some users do this: It sucks. I mean I am the one giving the answer - I am the expert. It should be the expert who decides which term/sentence should be emphasised and which don't. I have nothing against correcting my bad english but when it comes to the content or formatting I don't want to be messed with it unless you want me to leave.

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

#75

Post by pointernil »

ot wrote: post #40
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…

> 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…

Seriously, speaking about interesting data structures, Burrows-Wheeler Transform and its reverse are borderline "magic". Definitively worth understanding them in detail.

Speaking of which: What are efficient ways to insert data into BWT structures without reconstructing the whole thingy or to merge two BWT structures? Any hints?

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

#76

Post by oneeyedpigeon »

oneeyedpigeon wrote: post #45
joelthelion wrote: post #35

Earlier quoted context omitted.

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

Yahoo answers.

I was shooting for 'brevity is the soul of wit' but fear I might have hit 'sarcasm is the lowest form of humour' and completely failed to get my point across, to wit, stackoverflow is designed for productive, informative, objective q&a, and alternatives that are less prescriptive, such as Yahoo answers, often end up as a source of unending crap.

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

#77

Post by dllthomas »

statusgraph wrote: post #73
WWKong wrote: post #27

Me and my friend were pretty serious about creating a new data structure called "drum". A drum is a one way store. You write to it but can't read from it. We put it off till we figured a practical use.

An append only log? The value of writing data is that you can read it, otherwise your structure is semantically equivalent to not writing at all.

Or reading some information computed from it, I suppose. Something needs to read it, ever, for that of course, but it doesn't necessarily need to be exposed in the interface.

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

#78

Post by dllthomas »

teddyh wrote: post #53

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 con…

The FIFO equivalent can also be useful.

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

#79

Post by teddyh »

dllthomas wrote: post #78
teddyh wrote: post #53

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 con…

The FIFO equivalent can also be useful.

I’m not sure what you are referring to, do you have a link?
Post reply on HN