4 ms·

The documentation and code quality is all good. The implementation choices leave some things to be desired. The Queue and Stack implementations are Linked List

The 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 Great (tm) with just a little bit of work.

pitaj 8y ago
Wait are linked lists not better for first-in first-out data structures? I thought arrays were not preferred in those cases because shift/unshift are highly inefficient. Am I wrong? I thought array-based queues resulted in O(n) queue/dequeue. Now for stacks, which are last-in first-out, it makes sense to use an array.
- eximius 8y ago
  You use an array with pointers to the front and back of the queue, essentially a circular buffer. You might need to resize, but that happens for any array backed structure and is one (or two) memcpys.
- deathanatos 8y ago
  > I thought array-based queues resulted in O(n) queue/dequeue. Not necessarily. A circular buffer[1] can be used as a queue with O(1) queue/dequeue. C++ implementations (gcc?), IIRC, uses an interesting array-of-arrays approach; it also has O(1) queue/dequeue. I'm not sure why the array-of-arrays approach is better than a circular buffer, though. Array based designs can result is less allocations, and maybe less overhead. For example, if you have a circular buffer with space for 16 items, it only needs to allocate space if you need more room, whereas a linked list queue would allocate for each and every item placed into it. Linked lists also require space for the pointer to the next link, for each link in the list. (And, if you keep them, back pointers, though these aren't necessary for just a queue.) Arrays might have some unused slack space, however. [1]: https://en.wikipedia.org/wiki/Circular_buffer https://en.wikipedia.org/wiki/Circular_buffer
  - jayd16 8y ago
    Resizing a fully contiguous circle buffer would cause a copy every element as well forcing you to make a single contiguous memory section. Array of arrays just needs to resize the top level array.
    - manwe150 8y ago
      But the copy only has to move n items, but was constructed with m items, where n < m (and usually n << m). Where n is the max size of the queue and m is the total number of items that will ever be enqueued. On the other hand, an array of arrays (no recursion) doesn’t change the big-O complexity cost, just the constant multiplier. That should definitely improve performance of the uncommon operation (the copy), but hypothetically might slow down the actual queuing operations (and drastically reduce throughout) But maybe you meant the array of arrays to be recursive? That seems like it would alter the big-O (from n+m to log(n)+m). But typically m>>n, so the net result is the same.
- manwe150 8y ago
  Only if you eagerly shift all elements on every operation. If you allocate extra space, and only shift every N operations (N being the max size of the list), it’s O(n/n), eg O(1) amortized. As mentioned already, you can represent it as a circular buffer to save a bit of memory. But this cost analysis also means that a simple array can be much faster than a linked list for almost all operations in theory (excludes random insert given an insert token, which is not an index). I believe there’s also experimental evidence of this showing that an array is almost always preferable to a linked list - even in the cases were a linked list is often taught as the obvious choice (such as a queue). Yep, surprised me quite a bit too.
profunctor 8y ago
What book would you recommend to learn about these implementation improvements.
- eximius 8y ago
  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-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. ;)
solaxun 8y ago
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.

pitaj 8y ago

Wait are linked lists not better for first-in first-out data structures? I thought arrays were not preferred in those cases because shift/unshift are highly inefficient. Am I wrong? I thought array-based queues resulted in O(n) queue/dequeue. Now for stacks, which are last-in first-out, it makes sense to use an array.

eximius 8y ago
You use an array with pointers to the front and back of the queue, essentially a circular buffer. You might need to resize, but that happens for any array backed structure and is one (or two) memcpys.
deathanatos 8y ago
> I thought array-based queues resulted in O(n) queue/dequeue. Not necessarily. A circular buffer[1] can be used as a queue with O(1) queue/dequeue. C++ implementations (gcc?), IIRC, uses an interesting array-of-arrays approach; it also has O(1) queue/dequeue. I'm not sure why the array-of-arrays approach is better than a circular buffer, though. Array based designs can result is less allocations, and maybe less overhead. For example, if you have a circular buffer with space for 16 items, it only needs to allocate space if you need more room, whereas a linked list queue would allocate for each and every item placed into it. Linked lists also require space for the pointer to the next link, for each link in the list. (And, if you keep them, back pointers, though these aren't necessary for just a queue.) Arrays might have some unused slack space, however. [1]: https://en.wikipedia.org/wiki/Circular_buffer https://en.wikipedia.org/wiki/Circular_buffer
- jayd16 8y ago
  Resizing a fully contiguous circle buffer would cause a copy every element as well forcing you to make a single contiguous memory section. Array of arrays just needs to resize the top level array.
  - manwe150 8y ago
    But the copy only has to move n items, but was constructed with m items, where n < m (and usually n << m). Where n is the max size of the queue and m is the total number of items that will ever be enqueued. On the other hand, an array of arrays (no recursion) doesn’t change the big-O complexity cost, just the constant multiplier. That should definitely improve performance of the uncommon operation (the copy), but hypothetically might slow down the actual queuing operations (and drastically reduce throughout) But maybe you meant the array of arrays to be recursive? That seems like it would alter the big-O (from n+m to log(n)+m). But typically m>>n, so the net result is the same.
manwe150 8y ago
Only if you eagerly shift all elements on every operation. If you allocate extra space, and only shift every N operations (N being the max size of the list), it’s O(n/n), eg O(1) amortized. As mentioned already, you can represent it as a circular buffer to save a bit of memory. But this cost analysis also means that a simple array can be much faster than a linked list for almost all operations in theory (excludes random insert given an insert token, which is not an index). I believe there’s also experimental evidence of this showing that an array is almost always preferable to a linked list - even in the cases were a linked list is often taught as the obvious choice (such as a queue). Yep, surprised me quite a bit too.

profunctor 8y ago

What book would you recommend to learn about these implementation improvements.

eximius 8y ago
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-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. ;)

solaxun 8y ago

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.