Data structures

[Kikobeats]

I miss a good set of modules for implement traditional data structures. It's true that collectionjs it's ok, but in special I miss trees and more complex structures.

https://en.wikipedia.org/wiki/List_of_data_structures

[sindresorhus]

I would like to add that implementations should preferably have an extensive test suite and come with a benchmark to prove it's efficient.

[sindresorhus]

Some inspiration here: https://github.com/nzakas/computer-science-in-javascript

[rex]

@Kikobeats - I think it would be helpful (and possibly more attractive to a potential contributor) if you were to outline a list of functions that you imagine being present in such a module. I'm always up for a challenge but when I try and think of what 'more complex data structures' means I have trouble coming up with anything. (Full disclosure: I have no formal computer science training and thus don't possess knowledge of what people that do consider complex data structures).

@sindresorhus I totally agree. Ultimately there are enough implementations in userland that writing an additional implementation that performs poorly doesn't do anyone any good.

[sindresorhus]

list of functions that you imagine being present in such a module.

That's dependent on the data structure. Each data structure should be a separate module. The modules should preferably share the same traits of performance, test coverage and documentation.

[rex]

@sindresorhus You're totally right. Mushing them together in one place would be yucky. Nevertheless, I do think it would be helpful to provide a list of data structures that @Kikobeats thinks would be useful. Something a prospective developer could start with, at least, and build on.

[Kikobeats]

@rex I would put attention a, not necessary complex, but structures that are not possible simulate with trivial javascript code and are tremendous common, as Hashes, Trees and Graphs.

Maybe start with the typical binary tree can illustrate the roadmap

[rreusser]

Things along these lines that I like (not that you can't search npm yourself, though you may or may not get good results [e.g. bluebird. 181,000 downloads today and it's the second result on the second page???]):

• https://github.com/dstructs
• https://github.com/mikolalysenko (e.g. a bunch of trees)
• https://github.com/mgechev/javascript-algorithms
• https://www.npmjs.com/package/knn
• https://www.npmjs.com/package/euclideanmst (happened to need this; GPLv3 :grimacing:)

My feeling: there's lots of good stuff out there! Would it make more sense to search out pretty good implementations of these basic algorithms and either include, fork, or submit pull requests to clean up and standardize them just a bit? Then put them under some sort of loosely affiliated umbrella/collection? Find a way to communicate more connections on top of github/npm? Maybe even a badge that links a package—either manually or through some sort of network analysis or whatever it takes—to some larger context?

So on a higher level, my module request (can submit separately :smile:) would be for tools to fill the gap between single-concern npm modules and larger contexts. I'm about 85% on board with the modularity thing, but it really would be nice if discovery weren't so challenging.

An example I like: http://stack.gl/packages/

It just scrapes a wiki page and makes a site out of it. Is there a standard tool or format for this? Should there be? Like if you could just point to a list of repos and make an index with links, references, READMEs and additional perspective on what's what, then just throw it up onto its own repo/site in a way that's familiar and meaningful?

In other words, I've searched for various algorithms. Sometimes I find them, sometimes I don't. And when I don't, I often feel like it's only because they aren't tagged and indexed very well.

Sorry for the rant. Newish to node. Still getting my bearings. Data structures are great! :smile:

[sindresorhus]

// @mikolalysenko @hughsk

[rreusser]

(Sorry to pull you into more idle chatter, @mikolalysenko. I got embarrassingly stuck on corner cases in that SVD module, then sidetracked… Haven't forgotten though.)

[hughsk]

@rreusser the scraping part has been extracted into https://github.com/hughsk/ecosystem-docs – halfway there getting a more reusable/forkable version of http://stack.gl/packages/ out but I'll be on vacation for the next week :)

[rreusser]

@hughsk Ah cool! That's great! Thanks! I'd heard mention of the concept but wasn't yet aware of its status.

[rreusser]

Okay. Seems scopes are available and ecosystems and collections are in some state. Perhaps that and ecosystem-docs answers my issue.

Perhaps an ecosystem will be the right answer for data structures, once available.

[mikolalysenko]

@rreusser @hughsk Actually, I did take a stab at setting up package listings for scijs recently. You can find the current directory here:

• http://scijs.net/packages

I need to rerun it again to pull in all the latest updates as @jaspervdg has been cleaning up all sort of older modules left and right.

On topic: Regarding data structures, it seems like people often cargo cult copy a lot of stuff that makes no sense. Take for example the data structures in that computer-science-in-js repo. These might be fine exercises for educational purposes, but they aren't something you would ever actually want to use.

The danger with just writing data structures for the sake of creating data structures is that you risk losing sight of why you are bothering to do it in the first place. Data structures only function to speed up certain queries through the use of precomputation and caching. But without a clear notion of what queries you want to answer, it is pointless to start creating data structures haphazardly!

For example, complicated data types for graphs are usually a complete waste of time. It is far better to just store an edge table or an adjacency list. The extra layers of abstraction you would get with some weird "graph data structure class" would only serve to make interoperability harder and generate more garbage to collect by wasteful type conversions.

As a result, I think that rather than thinking in terms of data structures/objects it is better to start from specific queries and problems, and only then work backwards to the best implementations.

[samarpanda]

:+1: