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

Interesting but lesser known data structures

stackoverflow.com

Post reply on HN
Print view View original

11–20 of 25 posts

Re: Interesting but lesser known data structures

#11

Post by Trey-Jackson »

ominous_prime wrote: post #8

I feel like there isn't a good excuse for programmers to not know about a lot of these structures. Yes, some of the examples are somewhat unknown (I didn't know about the 2008 paper on "Left-Leaning Red-Black Trees" for example), but many of these are something that would be at least mentioned in basic college algorithms or data-structures courses. (I have a feeling the voting is skewing my perception, and people are…

IMO, 99.9% of the time you don't need the more obscure data structures. And I speak from experience working in companies on software requiring high performance (runs taking 6 hours to two days are not uncommon).

That said, I was disappointed nobody had added the corner stitched data structure - I found that to be a very intriguing idea (and in my world, it turned out to be very useful).

Re: Interesting but lesser known data structures

#12

Post by joshcrews »

ominous_prime wrote: post #8

I feel like there isn't a good excuse for programmers to not know about a lot of these structures. Yes, some of the examples are somewhat unknown (I didn't know about the 2008 paper on "Left-Leaning Red-Black Trees" for example), but many of these are something that would be at least mentioned in basic college algorithms or data-structures courses. (I have a feeling the voting is skewing my perception, and people are…

On the absence of qualifications, licensing and certification for programmers--I think it doesnt exist because its not yet an effective indicator.

People who can pass the tests can easily add no value (or negative value) to a project

People who've never bothered with the tests can quickly build great things, rescue projects, and fix the bad code/designs/patterns of test-passers.

If certifications/licensing/qualifications becomes and indicator of value in the future, I'm sure it will be adopted in the market then.

Re: Interesting but lesser known data structures

#13

Post by ominous_prime »

Trey-Jackson wrote: post #11
ominous_prime wrote: post #8

I feel like there isn't a good excuse for programmers to not know about a lot of these structures. Yes, some of the examples are somewhat unknown (I didn't know about the 2008 paper on "Left-Leaning Red-Black Trees" for example), but many of these are something that would be at least mentioned in basic college algorithms or data-structures courses. (I have a feeling the voting is skewing my perception, and people are…

IMO, 99.9% of the time you don't need the more obscure data structures. And I speak from experience working in companies on software requiring high performance (runs taking 6 hours to two days are not uncommon). That said, I was disappointed nobody had added the corner stitched data structure - I found that to be a very intriguing idea (and in my world, it turned out to be very useful).

> IMO, 99.9% of the time you don't need the more obscure data structures

Absolutely, and familiarity with these data structures is what's required to prevent these mistakes. I think a good understanding of these is more likely to prevent one from using them, or in some cases, "inventing" them.

Re: Interesting but lesser known data structures

#14

Post by ominous_prime »

joshcrews wrote: post #12
ominous_prime wrote: post #8

I feel like there isn't a good excuse for programmers to not know about a lot of these structures. Yes, some of the examples are somewhat unknown (I didn't know about the 2008 paper on "Left-Leaning Red-Black Trees" for example), but many of these are something that would be at least mentioned in basic college algorithms or data-structures courses. (I have a feeling the voting is skewing my perception, and people are…

On the absence of qualifications, licensing and certification for programmers--I think it doesnt exist because its not yet an effective indicator. People who can pass the tests can easily add no value (or negative value) to a project People who've never bothered with the tests can quickly build great things, rescue projects, and fix the bad code/designs/patterns of test-passers. If certifications/licensing/qualificat…

I agree. I was thinking about trying to compare it to a profession like structural engineer, pilot, doctor, etc., but each of those has rigorous training and certification.

Re: Interesting but lesser known data structures

#15

Post by ominous_prime »

SeanDav wrote: post #7
SeanDav wrote: post #2

Not sure one could call it a data structure but who remembers the so-called Sneaker Network or Tackie Network, which consisted of someone copying information onto a disk and physically walking to the other machine to copy the information. Networks were so slow/buggy that it was often quicker to transmit information using this "data structure"

Yes the Floppy disk is the Data Structure, which is interesting in itself, but in order for this data structure to work it must be both loosely and tightly coupled to the transport layer.... edit: To the downvoters - is a sense of humour not allowed on HN?

Then I don't get the joke - it just sounds like you don't know what a data structure is. (I don't have downvote-superpowers, just offering an explanation)

Re: Interesting but lesser known data structures

#16

Post by earino »

ominous_prime wrote: post #13
Trey-Jackson wrote: post #11

Earlier quoted context omitted.

IMO, 99.9% of the time you don't need the more obscure data structures. And I speak from experience working in companies on software requiring high performance (runs taking 6 hours to two days are not uncommon). That said, I was disappointed nobody had added the corner stitched data structure - I found that to be a very intriguing idea (and in my world, it turned out to be very useful).

> IMO, 99.9% of the time you don't need the more obscure data structures Absolutely, and familiarity with these data structures is what's required to prevent these mistakes. I think a good understanding of these is more likely to prevent one from using them, or in some cases, "inventing" them.

huge point. Nothing like seeing someone hand-implement (poorly) a balanced tree.. and usually be very proud of it.

Re: Interesting but lesser known data structures

#17

Post by spenrose »

ominous_prime wrote: post #14
joshcrews wrote: post #12

Earlier quoted context omitted.

On the absence of qualifications, licensing and certification for programmers--I think it doesnt exist because its not yet an effective indicator. People who can pass the tests can easily add no value (or negative value) to a project People who've never bothered with the tests can quickly build great things, rescue projects, and fix the bad code/designs/patterns of test-passers. If certifications/licensing/qualificat…

I agree. I was thinking about trying to compare it to a profession like structural engineer, pilot, doctor, etc., but each of those has rigorous training and certification.

Those professions are characterized by the value of replicating previous work. The "problem space" involved in removing an appendix or flying a Cessna on a specific route is just much, much smaller and simpler than the problem spaces software developers are expected to navigate. When you have larger problem spaces -- Boston's "Big Dig", experimental surgery, etc., that certification and rigor becomes less relevant, and the results less predictable, just like in software.

Re: Interesting but lesser known data structures

#18

Post by Trey-Jackson »

ominous_prime wrote: post #13
Trey-Jackson wrote: post #11

Earlier quoted context omitted.

IMO, 99.9% of the time you don't need the more obscure data structures. And I speak from experience working in companies on software requiring high performance (runs taking 6 hours to two days are not uncommon). That said, I was disappointed nobody had added the corner stitched data structure - I found that to be a very intriguing idea (and in my world, it turned out to be very useful).

> IMO, 99.9% of the time you don't need the more obscure data structures Absolutely, and familiarity with these data structures is what's required to prevent these mistakes. I think a good understanding of these is more likely to prevent one from using them, or in some cases, "inventing" them.

That's a fair point.

Though another way to avoid making the mistakes is to not invent data structures. That's what libraries are for, and anyone not using a library data structure should be able to defend why they're not. Odds are, they've got no chance of writing something better than what the libraries provide (or they'd be a library writer and already know these things).

Re: Interesting but lesser known data structures

#19

Post by EMRo »

Noob question: I hacked together my little mobile website and am looking to cut down on search time for a "similar search" I built.

Short Description: Each "unit" has x attributes in the form of strings (tags). Searching queries a database using a standard mysql regexp search for each tag across all "units" and sorts responses by # of tags matching Desc.

I know this isn't StackOverflow so this isn't really a tech question. What I want to know is if the problem is just that I'm a noob (just learned to code/do web development in the past few months) and need to learn more about data structures or if that's just the nature of php/mysql regexp queries (if its a database structure issue, let's not even get into it lol)

Re: Interesting but lesser known data structures

#20

Post by gwern »

silentbicycle wrote: post #10

Also: binary decision diagrams (BDDs), Prolog's difference lists, and the persistent variants of common data structures. I like skip lists, too, though they seem to be fairly well-known among programmers who don't just naively use linked lists and generic hash tables for everything.

BDDs are already on there (I'd never heard of them before Knuth's fasicle, but I guess he's sort of popularized them), as are a lot of persistent variants.
Post reply on HN