31–40 of 45 posts
https://gist.github.com/robertfairley/11ba23640578650671dbde...
Earlier quoted context omitted.
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.
> 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 over…
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 Grea…
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.
Earlier quoted context omitted.
> 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 over…
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.
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.
This repo is beautiful. The README is detailed and clear, and the contents seem pretty exhaustive. As a native JS guy I'm especially excited to check out the implementation of non-tree graphs! Having said all that: The algorithms I've had to tackle at work tend to be fairly trivial or total one-offs involving scheduling events in human time. How much algorithmic work do you other JS folks end up doing?
> How much algorithmic work do you other JS folks end up doing? I recently built a questionnaire/form editor/builder which relies heavily on tree structures. I ended up writing a lot of tree walking code. It was the first time I've ever needed to implement interview-like questions in an actual project. I make heavy use of functional programming in Javascript, which lends itself to really clean implementations of algo…
is there a similar thing with python too ?
Earlier quoted context omitted.
I have to admit I’m far from a FP guru, very little experience with true functional languages like Haskell etc. For me it’s more a question of style and applying functional paradigms when possible, eg treating functions as first class citizens, making heavy use of .bind() and passing functions as arguments. I use ES6 via Babel and actually find it to be quite expressive and powerful when used correctly. I just try to…
It requires use of Babel, but you might find the function bind operator an interesting alternative to .bind(). https://babeljs.io/docs/plugins/transform-function-bind/
[1] https://www.packtpub.com/web-development/learning-javascript...