4 ms·
What book would you recommend to learn about these implementation improvements.
by profunctor 8y ago
What book would you recommend to learn about these implementation improvements.
- eximius 8y agoReally any algorithm book should cover these (excluding hash table optimizations). The Sedgewick book is often recommended as a good starter book, though I'm not sure how much of what I said is explicitly covered, it's been a while since I read it. The array vs. linked list thing is sort of just knowledge you pick up, I suppose? Linked lists have their place, just fairly rarely. For a more in depth listing of the pros and cons, https://stackoverflow.com/questions/393556/when-to-use-a-linked-list-over-an-array-array-list https://stackoverflow.com/questions/393556/when-to-use-a-lin... is a good discussion. I consider use cases for linked lists to be rather niche (if someone comes in and mentions the kernel - that is niche). a & b are both basically on embedded systems (real time or low memory), c is rare outside of, well, queues and stacks, which are better in arrays anyway, and d is reasonable but with a bad example (a heap-based priority queue is better - and your heap should be array backed). They're flexible and easy but rarely the best solution. The union-find thing should be fairly standard. I mean, the optimizations are on the wiki page for union find. Pretty sure Sedgewick and online course cover those optimizations too. Adding those optimizations is equivalent from transforming a naive binary search tree into AVL or a Red-Black tree, which is a pretty huge improvement. The hashtable stuff I learned mostly from lurking here on HN. ;)