Hacker News Reader

Comment by jerf | Hacker News Reader

As you get into advanced data structures, you often need the gory technical details to make correct decisions about tradeoffs and usage. Succinct data structures, for instance, which are a specific thing and not just a generic adjective, are almost miraculously powerful, but you'd better understand exactly what the preconditions for using them are (which is a fairly mathematical discussion) and what the tradeoffs are before you use them because you will not be able to just "tweak" them and fix them up later if you're wrong.

View on HN

I read some of the scribe notes on succinct data structures from the link, it jumped out at me as something interesting. But going from `O(n)` to `n + o(n)` doesn't seem especially game-changing -- what lead you to describe it as "miraculously powerful"?

The constant reduction is amazing, for those precise use cases you can afford to use them. Not all linear is created equal. O(10n) = O(n/10), but in practice the performance difference of the inner expressions can be a huge difference.

(Note that is a correct usage of the O notation; because of the fact that those two things are equal we generally just use O(n) because for clarity you might as well use the simplest member of the equivalence class defined by the O notation, but it is still valid to write O(n/10). It's just an error to treat it as anything other than equal to O(n).)

With that being said, would you agree that in general one does not need to be intimately familiar with these to be a productive, useful software engineer?

I generally would.

I'm often amazed at how far a key/value store and an array type can get you.

But when you need more, it's good to know your options.

In fact I'd say nobody can afford to be intimately familiar with all the various advanced data structures. But most people will, at most, just need to know the things they might need, then go learn about them when they need it, and many won't even need that much.

Depends on what counts as productive. If you job is to get tens of billions of things done in a second, then your productivity depends a lot on what the cache locality properties of your data structure are and whether you can allocate your space up front.

Or you just use strings (and regexps to process them)!

Now you have two problems.

Now you have a number of problems unbounded in the worst-case.

Reply on news.ycombinator.com