4 ms·

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

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 voting up what they've heard of and think are lesser known, and ignoring what they don't recognize at all). I don't have a CS degree, nor am I solely a programmer, but I make sure I'm aware of the underlying fundamentals of my profession. Even without taking courses, one could easily take some time to read through the related wikipedia articles - http://en.wikipedia.org/wiki/List_of_data_structures http://en.wikipedia.org/wiki/List_of_data_structures P.S. I was trying to think up a good analogy to another technical trade, but I can't think of one where you can be completely unqualified, and work without licensing or certification.

Silhouette 16y ago
I think perhaps you are looking at basic college data structures courses through rose-tinted glasses. A typical first course in data structures is where novice students learn about everyday tools like hash tables and balanced binary trees. It probably mentions a few slightly more amibitous things, but not many. I would hope a second course at least introduced topics like purely functional and lock-free data structures and their applications, but obviously you're not going to get Okasaki and everything that's developed since at that level. Most people doing a straightforward CS/SE degree aren't going to do a lot more than two general data structures courses, and maybe encounter a few of the more specialist tools in applied courses on topics like 3D graphics or databases/information storage.
Trey-Jackson 16y ago
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).
- ominous_prime 16y ago
  > 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.
  - earino 16y ago
    huge point. Nothing like seeing someone hand-implement (poorly) a balanced tree.. and usually be very proud of it.
  - Trey-Jackson 16y ago
    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).
- cpeterso 16y ago
  I've heard someone joke that "real world" software uses just two data structures: arrays and hash tables. 1. An array can implement a stack or queue and is often cache-friendlier than a linked list of nodes scattered throughout the heap. 2. A hash table can implement a map or set for fast lookups of unordered data.
joshcrews 16y ago
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.
- ominous_prime 16y ago
  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.
  - spenrose 16y ago
    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.

Silhouette 16y ago

I think perhaps you are looking at basic college data structures courses through rose-tinted glasses. A typical first course in data structures is where novice students learn about everyday tools like hash tables and balanced binary trees. It probably mentions a few slightly more amibitous things, but not many. I would hope a second course at least introduced topics like purely functional and lock-free data structures and their applications, but obviously you're not going to get Okasaki and everything that's developed since at that level. Most people doing a straightforward CS/SE degree aren't going to do a lot more than two general data structures courses, and maybe encounter a few of the more specialist tools in applied courses on topics like 3D graphics or databases/information storage.

Trey-Jackson 16y ago

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

ominous_prime 16y ago
> 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.
- earino 16y ago
  huge point. Nothing like seeing someone hand-implement (poorly) a balanced tree.. and usually be very proud of it.
- Trey-Jackson 16y ago
  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).
cpeterso 16y ago
I've heard someone joke that "real world" software uses just two data structures: arrays and hash tables. 1. An array can implement a stack or queue and is often cache-friendlier than a linked list of nodes scattered throughout the heap. 2. A hash table can implement a map or set for fast lookups of unordered data.

joshcrews 16y ago

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.

ominous_prime 16y ago
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.
- spenrose 16y ago
  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.