22 ms·
JavaScript-algorithms: Algorithms and data structures implemented in JavaScript
- golovatyi 4y ago[dead]
- scscsc 4y agoI would like to point out that such a resource is useful for reference purposes (only). If you want to really understand an algorithm/a data structure, you have got to read it up and get your hands dirty and implement it yourself. There is no way around this. This is a bit like taking notes in classes. The notes themselves are (nowadays mostly) almost worthless, with easy access to textbooks and other resources. The fact of taking the notes is what actually counts.
- PartiallyTyped 4y ago> implement it yourself ... ... in C or something that allows you to get to the nitty gritty details. Or if the DS are immutable, do it in Haskell or similar.
- wruza 4y agoSometimes you don’t want to understand it or go through “find all bugs you’ve introduced again” cycle. In that case, off-the-shelf or abstract solution is much better.
- quickthrower2 4y agoThe number of stars on that repo!
- sublinear 4y agoI would like to point out that a possible reason this repo is so popular is that Javascript is more accessible to more people than any other programming language today and this shows the demand to meet these programmers halfway and help further their education. I think most js devs know Javascript is a poor choice for this, but they have to walk before they can run. I tend to think of Javascript as the language that fulfills the promises that BASIC never did. If every student walking into a computer science course only knew Javascript, that would still be a massive improvement over the past where half the students didn't know any programming language at all or only some vastly underpowered ones like Logo or BASIC.
- _s_a_m_ 4y agoIts purpose seems understanding and showing implementations of data structures, in this sense JavaScript is used like pseudocode. No sane person would implement something efficient outside of C++ or C.
- gumballindie 4y agoJS runs on any device regular users might want to use. If done right it’s the best language for what it was built for.
- yCombLinks 4y agoRight, it's the best language because it's available almost anywhere, not because it's well designed or a good teaching language.
- dahart 4y ago> I think most js devs know JavaScript is a poor choice for this Please elaborate, why is JavaScript a poor choice for demonstrating algorithms? Also what would be a better choice, and why?
- aketchum 4y agoAs someone that writes Node as main production language, I will say I am very glad to have been taught my DSA courses in Java. I think a strongly typed language like Java that also requires explicit memory management (if you restrict yourself to using only Arrays) is ideal because you can not ignore things that are abstracted by the language. In python or JS the standard array class is more like ArrayList and it automatically reallocates space when needed. This is hidden from you and you do not realize the additional computations that are occurring and thus you do not learn as well.
- account-5 4y agoAre there similar resources for other languages? I'd like python, lua, tcl, and dart... Likely not , maybe python, well definitely python you'd think.
- throwaway290 4y agoAre these considered the best possible implementations of relevant algorithms in JS? I wish these were in their own repositories, it's a bit unwieldy to follow issues/PRs in a monorepo. Also would make sense to publish them on NPM for reuse...
- esprehn 4y agoThese implementations are nicely written for learning purposes, but look inefficient. For example many of the data structures are implemented with a LinkedList, but the allocations and pointer chasing is likely slower than just using arrays.
- throwaway290 4y agoThank you!
- imbnwa 4y agoAs a relative novice, I notice that a few animation libraries rely on linked lists for sequencing animations, and, as I understand it, React uses a linked list to implement the queue created from the Hooks calls in a component; is there no benefit to a linked list over an array that counters the downside of pointer chasing?
- esprehn 4y agoLibraries and frameworks generally use intrusive linked lists where the pointers are embedded inside the objects. That enables a lot of useful properties (like traversal) with minimal overhead. That's how the DOM and Layout is implemented in browsers as well. Link lists that use separate nodes (like the project in TFA) are rarely the best choice due to the performance trade offs and way modern CPUs work. This article explains it well: https://www.data-structures-in-practice.com/intrusive-linked-lists/ https://www.data-structures-in-practice.com/intrusive-linked... See also: https://github.com/trekhleb/javascript-algorithms/blob/bbbfd32a45a677950554a91c4ece8976b8b31c38/src/data-structures/linked-list/LinkedListNode.js#L1 https://github.com/trekhleb/javascript-algorithms/blob/bbbfd... https://github.com/trekhleb/javascript-algorithms/blob/bbbfd32a45a677950554a91c4ece8976b8b31c38/src/data-structures/linked-list/LinkedList.js#L4 https://github.com/trekhleb/javascript-algorithms/blob/bbbfd... Vs what React does: https://github.com/facebook/react/blob/657698e48d5b093b4ea5a7684e26d3fdd16695f2/packages/react-reconciler/src/ReactFiber.js#L148 https://github.com/facebook/react/blob/657698e48d5b093b4ea5a...
- 1bent 4y agoSeems like this might be worth bookmarking in case I ever want to learn Javascript; reading implementations of algorithms I've written before in other languages seems like it might be helpful.
- dpweb 4y agoAlso, Stack: [] Hash table: {} Queue: []. It’d be nice if Linkedlist and others (neural network) were made part of the language.
- illiarian 4y agoAnother useful resource is Functional Jargon Explained (in Javascript): https://github.com/hemanth/functional-programming-jargon https://github.com/hemanth/functional-programming-jargon
- mathisfun123 4y agoAs someone that knows enough cat theory and fp to scoff at most formal presentations (including all of the famous hypebeast ones hn loves to recommend), I have to say bravo to that guy (person) for doing something I've thought of doing many times (and doing it very well!). My strongly held belief is that FP/category theory is a language game (in the wittgenstein sense) played for its own sake. If you don't know fp and you're curious/impressed by all the jargon and I told you functor/monad/applicative is all just a means to runtime operator overloading would you still be as impressed? And if you do know fp and I say the same to you, if your response is I'm wrong, can you please give me a concrete example for something that Applicative (or one of those other things) can do that runtime operator overloading can't? And don't allude to purity or laziness because those are orthogonal. Here I'm talking about specifically what `lift` and `bind` enable you to compute. Further preempting the very common responses: equational reasoning is an artifact of the type system that enforces various "contracts". You can enforce the same contracts in whatever imperative language (at runtime, at compile time, whatever).
- illiarian 4y ago> if your response is I'm wrong I've actually seen people criticise the definition and implementation of monads there because they apparently don't conform to monadic laws :) As a guy who's tried and failed to get into Haskell a few times, I say: so what :)
- mathisfun123 4y agoYes monads in Haskell aren't "lawful" but they're still useful, which you rightly point out does indirectly reaffirm my claim.
- 4y ago
- asicsp 4y agoFor other languages, see https://github.com/tayllan/awesome-algorithms https://github.com/tayllan/awesome-algorithms — resources to learn and/or practice algorithms
- codetrotter 4y agoCmd+F Rust 0 results >:(
- asicsp 4y agoThat's surprising. Anyway check these out: * https://github.com/EbTech/rust-algorithms https://github.com/EbTech/rust-algorithms * https://github.com/TheAlgorithms/Rust https://github.com/TheAlgorithms/Rust
- asciimov 4y agoOne can spend an enjoyable afternoon re-implementing some of these using the equivalent of lisp's cons as a node: let node = (a,b) => (bool) => bool?a:b; It's a fun little exercise to also keep the rest of the functions minimalist.
- snowstormsun 4y agoSee also: https://github.com/Yomguithereal/mnemonist https://github.com/Yomguithereal/mnemonist
- smusamashah 4y agoAs far as sorting goes, I made a visualizer a while ago https://xosh.org/VisualizingSorts/sorting.html https://xosh.org/VisualizingSorts/sorting.html which additionally let's you visualize your own algo and share it via url.
- internetter 4y agoThis is really cool. It inspires me to try and visualize my old AOC solutions
- photochemsyn 4y agoTutorials such as this one seem geared more towards college DSA courses rather than actual production code. For example, the code for traversing a tree in any order is implemented using recursion, but this is not what production code would do, as for any large amount of data the stack would be exhausted as recursive depth limits are exceeded. Thus, real-world code always requires the creation of a dynamically allocated stack or queue on the heap to store the values at each node. I don't know if there are similar issues with say, the presenation of hash tables, but it does cause a certain lack of confidence. This kind of gap between academic presentation of concepts and real-world production approaches is fairly common - but why not always teach the latter, I wonder? I imagine 'baby steps' is the argument, but it could also be called teaching bad practices. Incidentally, ChatGPT continues to astound: > "What would a code snippet for traversing a binary search tree in in-order in Javascript using a dynamically allocated heap approach look like?"
- tylerhou 4y ago> For example, the code for traversing a tree in any order is implemented using recursion, but this is not what production code would do, I think this is much too strong of a generalization. For small trees, a recursive traversal is clearer & easier to modify, and I would prefer to ship a recursive traversal vs. an iterative one. In fact, part of my job at Google was optimizing a particular (recursive) tree traversal in Search. Every time you search on Google, that traversal happens many thousands of times behind the scenes :).
- lizardking 4y agoThe primeagen has a great free DSA course using js on front end masters too. https://frontendmasters.com/courses/algorithms/ https://frontendmasters.com/courses/algorithms/
- wfhBrian 4y agoI would love to see HNSW in JS.
- soul_grafitti 4y agoI hear almost exactly this same discussion over roughly the same points about every coding language I have encountered. Well, in the forums of those languages...