Appropriate usage of data structures

[nvbhargava]

Appropriate data structures, when used correctly, can improve the speed/memory efficiency drastically. But I believe that many people resort to using hash tables at the end of the day just because they are the easiest to use. So, I was curious to see if you use (or maybe built from scratch) any data structures (trees, graphs etc.) regularly at your work or for your side projects?

[mathgeek]

> But I believe that many people resort to using hash tables at the end of the day just because they are the easiest to use.

For me, it's a matter of avoiding premature optimization. When I end up dealing with needing to optimize my code, very rarely is the data structure the primary pain point. Just because something is "easy to use" doesn't necessarily mean that the faster alternative is worth the opportunity costs.

I prefer the Donald Knuth quote:

"Programmers waste enormous amounts of time thinking about, or worrying about, the speed of noncritical parts of their programs, and these attempts at efficiency actually have a strong negative impact when debugging and maintenance are considered. We should forget about small efficiencies, say about 97% of the time: premature optimization is the root of all evil. Yet we should not pass up our opportunities in that critical 3%."

[nvbhargava]

I totally agree. This question I'd say was more focused towards that 3% of the time. So, if you believe that there is an opportunity to optimize something non-trivial, would you implement a whole new data structure for that?

[mathgeek]

Yes. That's the point of avoiding premature optimization. You only do it when necessary and thus has the best ROI.

[tannk11001]

As an engineer that identifies as being self-taught, even while having done some formal CS education after I'd already started my career, this question strikes me as unclear.

As far as I've seen in my own code, and those of my coworkers, we use all kinds of data structures when they're appropriate to a requirement and its constraints.

Are you suggesting that some people stubbornly don't use data structures that they're familiar with, even when they're important to speed/performance? I can't say I really see that happen very often. It's usually either that the engineer didn't happen to know the optimal solution, or (as was mentioned elsewhere) the optimal solution wasn't necessarily worth pursuing.

[nvbhargava]

Yes, I was wondering if people stubbornly don't use data structures that they're familiar with. To be more clear, I meant implementing a whole new data structure (let's say a trie) that a library/language might not already provide.

This, of course, is taking into consideration that the problem is non-trivial, and it improves the speed/performance.

[masokupride]

This is an interesting point. I guess it's due to the performance as well as the ease. I have used prefix trie for autocomplete, but even then i was using hashtables internally.

I also use alot of javascript, and there it is natural to use sparse arrays, which wind up being hashtables. iterating over these can be an issue though, so i have found that combining the hashtable with a linked list results in the best performance.

[nvbhargava]

Interesting.