4 ms·
There's a huge distinction between "used" and "implemented myself". I've used quite a lot of features from RDBMs, as well as topological sorting, LRU for cache
by perlgeek 6y ago
There's a huge distinction between "used" and "implemented myself".
I've used quite a lot of features from RDBMs, as well as topological sorting, LRU for caches, Unicode normalization, graph traversal, bloom filters, hash maps and so on.
I'm not payed to implement algorithms or data structures, but to solve problems. So for anything non-trivial I tend to use ready-made libraries.
I only implement stuff myself when it's faster and simpler to implement AND TEST it than to draw in another dependency, or if there isn't a well-made off-the-shelf component.
So what I've implemented myself at $work is pretty limited:
* depth-first tree traversal
* graph traversal
* parsers for various non-standard file formats
* maybe a topological sort once, not sure
Finally, many classical algorithms have lesser-known variants that optimize for some practical advantages (reduced memory usage, memory cache friendliness, sequential disk reads/writes etc.). So if I were to implement, say, a substring search, it might not be a by-the-book Boyer-Moore algorithm, but some subsequent paper that builds on it to add a few percent practical performance improvement.
- dolmen 6y agoYou still have to understand how things are implemented by others (even at a high level view: ex: what is a RDBMS index) to be aware of their advantages and drawbacks to make the best use of algorithms available to achieve your goals (ex: performance of the solution, ease of evolution of the solution).
- perlgeek 6y agoI agree. It's good to know a name of an algorithm/data structure, and rough characteristics (like bloom filter: O(1) lookup, super memory compact, statistical, can have false positives, no false negatives; perfect for caching lookups in "forbidden" lists). There's not much point though in knowning the minutiae to the level that you can code one on the whiteboard without prior preparation -- which is probably the main point that the article relates to.
- cmrdporcupine 6y agoAnd this is the measure of a good engineer -- recognizing that it's most likely that battle tested libraries will have superior implementations of algorithms than whatever one can draw up oneself. I use the STL daily. I know fairly well the complexity guarantees behind each data structure. That's one of the things I like about it versus other collections libraries. It forces you to be somewhat literate on data structures in order to make the right choices. But no, I could not write you up a red-black tree from scratch without going away for a few days with my Knuth books and a few pots of coffee. Sorry.