They don't explain lock-free data-structures?
Algorithms and Data Structures Explained and Implemented in JavaScript
41–45 of 45 posts
Re: Algorithms and Data Structures Explained and Implemented in JavaScript
#42Bookmarked! Well done.
Re: Algorithms and Data Structures Explained and Implemented in JavaScript
#43The documentation and code quality is all good. The implementation choices leave some things to be desired. The Queue and Stack implementations are Linked Lists instead of array backed, the hash table is closed instead of (the only barely more complicated) open Robin hood hash table scheme, the union-find/disjoint-set implementation doesn't have path compression or rank unions. Overall very good, but it could be Grea…
What book would you recommend to learn about these implementation improvements.
Re: Algorithms and Data Structures Explained and Implemented in JavaScript
#44The documentation and code quality is all good. The implementation choices leave some things to be desired. The Queue and Stack implementations are Linked Lists instead of array backed, the hash table is closed instead of (the only barely more complicated) open Robin hood hash table scheme, the union-find/disjoint-set implementation doesn't have path compression or rank unions. Overall very good, but it could be Grea…
This is something that I feel continually comes up when dealing with implementing data structures in a higher level language, and repeatedly confused me when I was learning this stuff.
I always found it misleading for example, to use an existing language implementation of a particular data structure (in this case a JS array) to represent a queue, and then simply provide methods that mock enqueue / dequeue but don't provide the same performance guarantees. All you're doing is mimicking the queue API but actually performing O(N) shift/unshift, which defeats the point of even having the data structure.
Not saying you can't do it properly with an Array, but I can't count the number of times I've seen not only blogs, but published educational materials advocate for using an existing Array-like structure as a starting point for a queue, and totally ignore the fact that that structure was not designed to remove from the front.
Just my personal opinion, but I think a linked list more clearly illustrates how to properly implement stacks/queues in a higher level language since you're forced to handle the pointers (nodes) yourself.
Re: Algorithms and Data Structures Explained and Implemented in JavaScript
#45The documentation and code quality is all good. The implementation choices leave some things to be desired. The Queue and Stack implementations are Linked Lists instead of array backed, the hash table is closed instead of (the only barely more complicated) open Robin hood hash table scheme, the union-find/disjoint-set implementation doesn't have path compression or rank unions. Overall very good, but it could be Grea…
What book would you recommend to learn about these implementation improvements.
Really 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-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. ;)