[HN Gopher] JavaScript-algorithms: Algorithms and data structure...
___________________________________________________________________
JavaScript-algorithms: Algorithms and data structures implemented
in JavaScript
Author : kiyanwang
Score : 159 points
Date : 2023-04-07 08:09 UTC (14 hours ago)
(HTM) web link (github.com)
(TXT) w3m dump (github.com)
| asciimov wrote:
| One 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 wrote:
| See also: https://github.com/Yomguithereal/mnemonist
| sublinear wrote:
| I 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_ wrote:
| Its 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.
| dahart wrote:
| > 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?
| stuartjohnson12 wrote:
| Everything in javascript except primatives are objects.
| Classes are objects, functions are objects, the runtime
| environment is an object. Not only is everything an object,
| but everything is mutable in an unlimited way.
| dahart wrote:
| And so how does this reflect on whether JS is a good
| language for demonstrating algorithms? What does it matter
| if something is an object? How would limiting mutability
| make a repo of algorithm examples any better? How are these
| things meaningfully different from other programming
| languages in this context?
| aketchum wrote:
| As 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.
| dahart wrote:
| If you look inside this repo, they don't rely on the
| standard array class for the linked-list or the stack.
| Given that, what's wrong with Javascript?
|
| My first DSA class was Scheme, btw, and it was absolutely
| fantastic, one of the best classes I had. Worrying about
| memory management is important to learn _eventually_ as a
| CS major, but certainly is not necessary for an
| introduction to algorithms and structures. It all depends
| on what you want, right?
| dxbydt wrote:
| > If you look inside this repo
|
| I actually looked in the repo & I believe some of it is
| incorrect. For instance, the signature insert(value,
| rawIndex) in [1] makes no pedagogical sense. Quoting from
| [2] - "There is no real concept of index in a linked
| list...Certainly none of the methods provided on the
| class accept indexes....Thinking of a linked list as a
| list can be misleading. It's more like a chain"
|
| He's then using this linked list as a base layer to
| implement Queue & Stack - which is correct - but doesn't
| ever use the insert with rawIndex functionality in either
| enqueue() or push() - so one wonders what the point of
| that index even was. Traditionally, a linked list allows
| you to insert before/after a node. i.e.
| addBefore(node,value) (see [2] ) He doesn't implement
| addBefore & addAfter.
|
| Instead, he provides a whole bunch of non-canonical
| helpers like reverse(), toArray(), deleteTail() etc -
| these are typical LC-Easy problems that don't belong
| inside the data structure.
|
| My own introduction to these things was a C course called
| "Data Structures in C" in the traditional CS curriculum,
| and yes, you would have to malloc a new node, get back a
| pointer with a memory address, & the process of pointing
| the next pointer of the current node to this new node so
| that the memory address of the next value was explicitly
| "linked" to the current value and hence linked list
| etc...I guess much of that terminology is lost on the new
| generation in the absence of pointers & memory addresses.
|
| The canonical exercise in those days was - Show that a
| linked list does not store objects in contiguous memory,
| unlike an array. So to solve this, you would traverse the
| list from the head node & print the actual addresses of
| the memory locations along the way, proving that the vals
| aren't stored contiguously. I wonder what that exercise
| would mean in JS land.
|
| That said, yeah its a good starting point & I applaud the
| effort.
|
| [1]https://github.com/trekhleb/javascript-
| algorithms/blob/maste... [2]
| https://stackoverflow.com/a/7777687
| hn_throwaway_99 wrote:
| > I actually looked in the repo & I believe some of it is
| incorrect. For instance, the signature insert(value,
| rawIndex) in [1] makes no pedagogical sense. Quoting from
| [2] - "There is no real concept of index in a linked
| list...Certainly none of the methods provided on the
| class accept indexes....Thinking of a linked list as a
| list can be misleading. It's more like a chain"
|
| Java's LinkedList implements List, and supports index
| insertion. I'm not arguing it's "right", but I _am_
| arguing it 's not "incorrect". It's a design decision,
| there are pros and cons to it (as your second link points
| out, C# went a different route), but I think it's a
| totally valid option.
| cxr wrote:
| Typed arrays and array buffers have been a thing in JS for
| longer than many of today's crop of programmers have even
| been writing code. (For longer than this repo has existed,
| at least.)
|
| And I don't know any language called "Node".
|
| (That isn't to say that this project is a particularly good
| example of how to write algorithms-focused code. It isn't.)
| qwertyuiop_ wrote:
| Java is anything but explicit memory management. If you
| really want to understand and work with memory management
| it's C/C++
| user3939382 wrote:
| > I tend to think of Javascript as the language that fulfills
| the promises that BASIC never did
|
| I taught myself BASIC when I was 7 when I didn't know what a
| programming language was.
|
| I've been programming JS for 25 years and I still commonly
| can't predict what the behavior of some aspects of my code is
| going to be, or what the state of the application is at a given
| point, until I try/run it.
| a_wild_dandan wrote:
| Thus far, JS has overwhelmingly been my favorite programming
| language. Expressive; amazing type system with TS; fast (V8
| is an engineering marvel); and its ecosystem has
| frameworks/libraries for nearly everything, given its
| overwhelming popularity!
|
| What makes reasoning about JS your code difficult, relative
| to other languages? Maybe the event loop is unintuitive? In
| my experience, opaque application states were caused by my
| odd engineering choices rather than any particular language.
| But I'd love to hear your experience.
| user3939382 wrote:
| There are so many gotchas that I give up even trying to
| remember them, thus I just try the code to find out what it
| will do. One fun one that just came up is that async
| callbacks work totally different inside a forEach vs a for
| loop. https://developer.mozilla.org/en-
| US/docs/Glossary/Hoisting
|
| I'm sure someone out there has compiled the list of things
| that don't make sense.
|
| It's like 100 people designed different features without
| talking to each other and glued it all together into one
| language.
| lenkite wrote:
| In one of my earlier JS projects, the coding guidelines
| strictly enforced the rule of declaring all variables at
| top of the function to not get confused by JS hoisting
| "magic".
|
| You need to enforce coding conventions in JS as soon as
| you have greater than one person working on a project.
| Sometimes even if you are the lone person - esp if you
| are coming back to it after a delay.
| azangru wrote:
| > I still commonly can't predict what the behavior of some
| aspects of my code is going to be
|
| Commonly? Could you give an example?
|
| > or what the state of the application is at a given point
|
| That's not a criticism of a language though, is it? It is
| either a criticism of how an application is being written, or
| a statement about the complexity of the application.
| kamranjon wrote:
| "4" + 4 = "44"
|
| "44" - 4 = 40
| a_wild_dandan wrote:
| In other words: play stupid games, win stupid prizes. ;)
| kamranjon wrote:
| Haha yes, most oddities in JS are a result of the
| language allowing you to play stupid games - many
| languages would just throw an error here (heck even ruby
| does). I discovered this strangeness when I forgot to
| _parseFloat_ on a string and things kept humming along as
| if nothing was wrong, until I did some addition and
| things grew exponentially.
| mdp2021 wrote:
| True, and apparently counterintuitive if presented that
| way, but it makes sense as '+' is a string concatenation
| operator. It is the type conversion that can be used in
| unclear contexts - it can be comfortable and also
| dangerous.
| [deleted]
| [deleted]
| cxr wrote:
| People love to trot out examples like this while remaining
| totally silent about why they're trying to add/subtract
| numbers and strings in the first place or articulate what
| they expected to happen when they did it.
|
| _On two occasions I have been asked, "Pray, Mr. Babbage,
| if you put into the machine wrong figures, will the right
| answers come out?" [...] I am not able rightly to apprehend
| the kind of confusion of ideas that could provoke such a
| question._
| kamranjon wrote:
| Oh I absolutely ran into this because I had a bug, I had
| forgot to parse the number into the correct format, but
| it still feels odd that the language behaves this way.
| Here is an example of what Ruby outputs:
|
| "4" + 4 : `+': no implicit conversion of Integer into
| String (TypeError)
|
| "44" - 4 : undefined method `-' for "40":String
| (NoMethodError)
|
| The funny thing being the implicit type conversion that
| javascript does. This is likely why typescript has become
| so popular.
|
| Are there other languages that have implicit type
| conversion for basic types like javascript?
| rasz wrote:
| It is practically impossible to teach good programming to
| students that have had a prior exposure to BASIC: as
| potential programmers they are mentally mutilated beyond hope
| of regeneration - Edsger W. Dijkstra
| pacaro wrote:
| At university I took one cs class, which was an easy credit
| part of a math class. It was taught in Fortran and at the
| beginning of the first lecture (this was in 1990) the
| lecturer asked for a show of hands who had experience with
| BASIC and many of us raised our hands. We were then given a
| pessimistic variant of the Dijkstra quote.
|
| I never took another CS class
|
| I have been working in the industry for nearly 30 years,
| have worked on cutting edge technology, contributed to
| software that billions of people use (and written plenty
| that fewer than 10 people use)
|
| I will, of course, never have the same impact/influence
| that Dijkstra has had.
|
| Did he ever acknowledge how fundamentally wrong he was
| about this?
| rasz wrote:
| This is quite hilarious considering the rest of the
| Dijkstra 1975 letter
|
| >FORTRAN --"the infantile disorder"--, by now nearly 20
| years old, is hopelessly inadequate for whatever computer
| application you have in mind today: it is now too clumsy,
| too risky, and too expensive to use.
| gumballindie wrote:
| JS 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 wrote:
| Right, it's the best language because it's available almost
| anywhere, not because it's well designed or a good teaching
| language.
| smusamashah wrote:
| As far as sorting goes, I made a visualizer a while ago
| https://xosh.org/VisualizingSorts/sorting.html which additionally
| let's you visualize your own algo and share it via url.
| internetter wrote:
| This is really cool. It inspires me to try and visualize my old
| AOC solutions
| account-5 wrote:
| Are 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 wrote:
| Are 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 wrote:
| These 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.
| imbnwa wrote:
| As 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?
| 1bent wrote:
| Seems 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.
| asicsp wrote:
| For other languages, see https://github.com/tayllan/awesome-
| algorithms -- resources to learn and/or practice algorithms
| codetrotter wrote:
| Cmd+F Rust
|
| 0 results
|
| >:(
| photochemsyn wrote:
| Tutorials 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 wrote:
| > 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 :).
| scscsc wrote:
| I 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.
| wruza wrote:
| Sometimes 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.
| PartiallyTyped wrote:
| > 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.
| golovatyi wrote:
| [dead]
| dpweb wrote:
| Also, Stack: [] Hash table: {} Queue: []. It'd be nice if
| Linkedlist and others (neural network) were made part of the
| language.
| lizardking wrote:
| The primeagen has a great free DSA course using js on front end
| masters too.
|
| https://frontendmasters.com/courses/algorithms/
| wfhBrian wrote:
| I would love to see HNSW in JS.
| quickthrower2 wrote:
| The number of stars on that repo!
| kilroy123 wrote:
| Wow, no kidding! This has to be one of them most popular repos
| there is?
| Rexxar wrote:
| Eleventh : https://gitstar-ranking.com/repositories
| illiarian wrote:
| Another useful resource is Functional Jargon Explained (in
| Javascript): https://github.com/hemanth/functional-programming-
| jargon
| mathisfun123 wrote:
| As 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 wrote:
| > 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 wrote:
| Yes monads in Haskell aren't "lawful" but they're still
| useful, which you rightly point out does indirectly
| reaffirm my claim.
| maemre wrote:
| I think this is more in the lines of mixing up concepts (the
| language features that enable implementing functors etc. in
| Haskell with functors as used in programming). I liked the
| JavaScript monad example in the grandparent, even if it was
| underwhelming. It is similar to Douglas Crockford's
| presentation of monads (using JavaScript, but with more
| interesting examples like promises).
|
| Type classes (as a language construct) are a way of doing ad-
| hoc polymorphism (read run-time operator overloading) more
| principled, and other language features can be used in place
| of them to implement an _interface_ for monads, functors,
| etc. One example is Scala's for expressions which boil down
| to a series of map, flatMap, filter and forEach calls so they
| work with any type that implements the subset of them you
| need without using type classes. If you want static typing
| and dynamic dispatch for stuff like monads then you'd want
| something like type classes or F-bounded polymorphism (what I
| allude to with the Mappable interface below) to have that.
|
| So, from what I see saying "run-time operator overloading can
| do what monads, etc. can do" would lead to "function pointers
| and closures can already do dynamic dispatch, what's the
| point of run-time operator overloading then?". Type classes
| are a way to have your cake and statically type-check it too
| (and they aren't the only way).
|
| Just to clarify, functors, applicatives, and monads are
| basically interfaces for polymorphic (generic) types with
| useful properties (which aren't checked by the language
| unless you're going out of your way to use something like
| Agda, so that's not the point) and they turn out to model
| accessing and changing data in a context in a nice way. You
| can just call them Mappable, Liftable, and Joinable and ship
| them in a Java library.
|
| I agree the language game part of it, the idea for them comes
| from category theory but they are different from what
| category theorists had in mind, and the jargon could be toned
| down to emphasize what they are useful for. I think the big
| idea is that a list (or an option) isn't the only thing that
| has a meaningful map and flatMap implementation, which is
| much simpler than "a monad is just a monoidal object in the
| category of endofunctors over Haskell types, what's the
| problem?"
___________________________________________________________________
(page generated 2023-04-07 23:01 UTC)