To Binary Tree or Not to Tree #473
Comments
|
First off, it's impossible to have multiple snippets with the same name, so we will have to still name them Secondly, data structure categories should be added but only as soon as we have enough snippets for each (5 sounds like a good starting amount). If someone can get started on coding snippets for each data structure and PRing them, I would be glad to get those categories up and running. |
Chalarangelo
added
discussion
help wanted
|
@Chalarangelo I def agree
Haha a lot of times I am lazy & omit my full explanation. I just used Didn't intend that we will actually have the same name, especially seeing that we have a package & would be conflicting AF when someone does |
|
We are not |
|
Hahaha 😆 🤣 |
|
@kingdavidmartins We will hit 200 before long, I have a backlog of 30 semi-implemented snippets on my computer, we might end up with 250 by next weekend. |
|
@kingdavidmartins and @Chalarangelo let's decide who is going to write which data structure so we don't come up with 2 same PRs. Should I make an Issue for this one? |
|
@fejes713 I'll do linked List you can do BST |
|
@kingdavidmartins I am not starting now either, but will do in two hours or so... It's going to be fun. |
|
I'm going to work on website features/maintenance and some other things, plus my own backlog of snippets. I'll pm either one of you if any of my code falls into one of your categories. On a side note, find emojis for the categories, too. |
|
For example, the binary tree category could have:
As for the |
|
Rewriting is ok, as it shouldn't be terribly long. You should also add a |
|
Do we want to do data-structures in this? That feels more like "30 seconds of CS" territory. Sure they're simple enough, but they are almost worthless in a website/server. If we need a binary tree we're literally recreating the Object in JS( which is doable, I'm just not certain we'd want to ) or getting into the land of odd stuff, which an advanced programmer might not understand. Remember great programmers can come from non-CS backgrounds. |
|
@skatcat31 You're right. I taught about writing that comment and then I was like "Huh I will just write snippets to see what others think about them". But yeah pretty much who would use a binary tree or a linked list on a website or a server... You got the point |
|
If we do these, we would need to create a type and reference every time in each of the BST snippets: BST Sym TestTest if a const BSTSymTest = node =>
(node.left === undefined && node.right === undefined)
? true
: (node.left !== undefined && node.right !== undefined)
? BSTSymTest(node.left) && BSTSymTest(node.right)
: falseconst BST = {}
BSTSymTest(BST) // true
BST.left = {}
BSTSymTest(BST) // false
BST.right = {}
BSTSymTest(BST) // trueWhich I'm pretty certain we said we wanted to avoid in our own contribution guidelines:
Which we kind of violate by saying "Go back and understand this first". Since we'd always have to reference the type... well I'm not certain it's a snippet then as much as a contained library and/or an extension(s) of a snippet. Beyond those caveats, I vote against doing non-EC types and classes as categories since it would require the reader to learn more about 30SoC to be able to understand, and they would have to hunt through the type snippets to find the declaration( meaning they'd be reliant on previous knowledge to understand ) |
|
I am however all for '30 Minutes of CS' lectures/articles 😸 |
|
Hey @skatcat31 👋 😄 Thanks for the feedback as always However I have to disagree with @fejes713 & You on this one
First of we are already technically using data structures. i.e Arrays. Although linear in nature. It's technically still a data structure.
Second of, the same way one who has zero web dev experience might not be able to understand code under the browser category in less than "30 seconds" or one with zero ES6 experience might not be able to understand our code using spread operator There's always going to be snippets where users have to quickly read up on especially so if they are trying to learn web dev snippets in the browser category with zero web dev experience, or trying to learn server specific operations with zero experience as a Backend engineer, and so forth. Just recently a friend of mine accepted an offer from Google. This is someone who is a "Non Traditional", who Picked up coding later on in high school, who also didn't attend college in the attempt to self study in pursuit to jump start their software dev career. During the interview process as you can imagine depending on the position/company the interview can entail solving/implementing things at scale. Let's look at the following example which is typically asked during interviews. How can one go about implementing a system similar to that of Twitter, Facebook, Google, etc that keeps track of what is currently trending as the top 10 in the midst of millions/billions of updates/post concurrently assuming your pull all the updates/post from a stream of sorts. Although one can use a Arrays to implement such a system. It is not feasible in production due to the insertion time / look up time for the greatest value or x amount of greatest values. Which if using a Binary tree would/can reach Imagine using an Array to insert all that data coming in from the stream and then sorting in place using Merge sort or Insertion sort. Then grabbing the last x values if sorted in ascending order. At scale this can incur hundreds of thousands $$$ if not millions $$$ of unnecessary expenses/resources daily/monthly 😦 I am not saying we can replace a CS course/degree. However I am saying that we can expose said users to new categories they never came across that could very much so help them in their endeavors with regards to their dev career. I'm sure it will work out the same way in how we expect users who come across new information/topics in our project to be proactive and research what's not fully understandable as a way to subsidize their learning. Personally after coming across a specifically new code block. I don't just don't copy blindly, but take time to research the subject on my own to a point where after re visiting said snippet it becomes more understandable. I believe the people who are currently pursuing whatever they can about code or JS are doing so not just to learn & understand it, but also as a way to prep/break in the industry. And as such feel they only benefit to be exposed to more categories/data structures/operations/etc NotePlease keep in mind that I also intend on keeping said snippets on par with the rules/standards set aside by the project in the sense that the time taken to grasp/understand said snippets will be on par with other their peers |
|
I'm personally really interested in learning more about data structures, so I would like these snippets and categories 😀 |
This comment shows a massive misunderstanding of a Data Structure versus a Class in terms of ES/JS:
var a = [1] // Array
var b = {0: 1, length: 1} // Array Data Structure
a instanceof Array // true
b instanceof Array // false
Array.prototype.map.call(b, x => x*2) // [2]
b // {0: 1, length: 1}
Array.prototype.map.call(a, x => x*2) // [2]
Array.prototype.forEach.call(b, (x,i,a) => a[i] = x*2)
b // {0: 2, length: 1}
Array.prototype.push.call(b, 3) // 2
b // {0: 2, 1: 3, length: 2}
b.push(4) // Uncaught TypeError: b.push is not a function |
|
@atomiks learning is always encouraged |
|
Now all this having been said, if we instead wanted to point to an external Class library for any of these CS ideas( BST, LL, Node list, etc. ) and then make snippets for them with a link to the library I have no complaints! I do not want use however putting a class definition and then a bunch of separated methods that should ideally live on the class instance into the repository. Afterthoughts: Also what implementation of BST/LL/TypeX would we do? Node Direct Construct or Node Reliant Class? |
|
My snippet earlier should have looked like BST Sym TestTest if a (Binary Search Tree)[URL to BST type in this project] is symmetrical const BSTSymTest = node =>
(node.left === undefined && node.right === undefined)
? true
: (node.left !== undefined && node.right !== undefined)
? BSTSymTest(node.left) && BSTSymTest(node.right)
: falseconst BST = {}
BSTSymTest(BST) // true
BST.left = {}
BSTSymTest(BST) // false
BST.right = {}
BSTSymTest(BST) // true |
|
In case anyone is curious about BST: class BST {
constructor( value ){
this.value = value;
}
insert(value){
if ( value < this.value ) this.left = this.left ? this.left.insert( value ) : new BST( value )
if ( value > this.value ) this.right = this.right? this.right.insert( value ) : new BST( value )
return this;
}
}This is a basic insert capable BST. It does not have the find method, but it comes in at 10 lines |
|
Hey @skatcat31 Ahh although I don't understand why you said the following
I believe you made that statement with the assumption I was addressing JS in general. During this discussion when describing data structure's please make the assumption I will be talking about data structures exclusive of any language. As I'm sure we can both agree that data structure's are not language specific in regards to implementation and/or time complexity when applied to Arrays, Lists, Vectors and/or other similar/different data structures Example:Gopackage main
import "fmt"
func main() {
var a [2]string
a[0] = "Hello"
a[1] = "World"
fmt.Println(a[0], a[1])
fmt.Println(a)
primes := [6]int{2, 3, 5, 7, 11, 13}
fmt.Println(primes)
}Javaclass Main {
public static void main(String[] args) {
// declares an array of integers
int[] anArray;
// allocates memory for 10 integers
anArray = new int[10];
// initialize first element
anArray[0] = 100;
// initialize second element
anArray[1] = 200;
// and so forth
anArray[2] = 300;
System.out.println("Element at index 0: "+ anArray[0]);
System.out.println("Element at index 1: "+ anArray[1]);
System.out.println("Element at index 2: "+ anArray[2]);
}
} & etcPending on the language one uses one can prove or disprove the your assertion NoteFeeling really lazy. So stopped there with the explanation/examples. Also keep in mind the that the following statement introduces the definition of The Array Data Structure
Although certain languages ergo JS can exhibit certain idiosyncrasies as you've shown. I still stands by the following statement
|
|
I'm a bit late to the discussion, but here's my take (an attempt at keeping the peace if you can call it that):
Based on my above points, my suggestion is the following:
On a side note, the whole style of the project is a functional one and the guidelines have to be followed, so we should avoid using classes entirely and stick to our functional style, even if that makes things slightly more difficult. |
I think again we're not lining up correctly but I was not speaking about JS in general either. What I mean by Class I stand by what I said regardless of JS, but I feel like a further explanation of a Data Structure is needed to make it much more agnostic:
Like I said in a comment before, if we link to an outside library or decide to make one ourselves and link to it then I have no problems. What I have a problem with is us using a snippet to define a Data Structure and then relying on that snippet in the future. I don't think we should have Data Structure implementations in this repo since a Class would be more appropriate and is outside the scope of the repository. While easy to implement a simple version, that version will have many downfalls in regards to the full Data Structure definition. That is why I want to avoid implementing the Data Structure as a snippet. Reading my previous comments I can see how this was a little obtuse. Where I standSnippets relating to Class implementations of Data Structures and linking to them: All for So if we can find a class we want to implement these snippets too I'm absolutely all for it, even if we code it ourselves. If we do code it ourselves we should probably make sure it fully conforms to a Previous Art Definition. |
Data Structures could be tens to hundreds of lines of codes for all the required implementation, and gets worse if we are not going to do it as a Class decleration due to possible prototype/state mutilation and exposing dangerous code that modifies Functions versus classes: Arrowconst BST = value => ({value})new BST(1) // FAILS, not a constructor, actually errors
BST(1) instanceof BST // false
BST(1) instanceof Object // trueClassical Constrtuctorconst BST = function (value) {
// to fix problem to come you'd need to include the next line in all Functional Classes
// if ( this instanceof BST === false ) throw new TypeError( `Class constructor BST cannot be invoked without 'new'` )
this.value = value
return this;
}
BST.prototype.insert = function (value) {}
BST.prototype.find = function (predicate) {}
BST.prototype.delete = function () {}var a = BST(1) // !!! modifies inherited this context without required check !!!
a instanceof BST // false, it modified the inherited context
var b = BST(1)
b === a // true, and very bad
var c = new BST(1) // works, scoped properly
c instanceof BST // true
c === a // falseClassclass BST {
constructor( value ){
this.value = value;
}
insert(value){...}
find(predicate){...}
delete(predicate){...}
}BST instanceof Function // true
var a = BST(1) // fails, throws error explaining why
var b = new BST(1)
b instanceof BST // true
var c = new BST(1)
c === b // falseRegardless of Classes we get into the territory of hosting a possibly hap hazard or dangerous implementation. We might want to instead link to an article we feel properly introduces the subject. Especially if we get into such types as Future, Functor, Collection, Iterable, Monad, Chain, CoMonad, IsoMorphic, Lens, etc. |
|
@skatcat31 A downside of using a factory instead of a constructor is indeed that it has a memory performance impact because it creates new objects with the methods every time instead of re-using a single prototype... const BST = value => ({
value,
insert(value) {
if (value < this.value) this.left = this.left ? this.left.insert(value) : BST(value)
if (value > this.value) this.right = this.right? this.right.insert(value) : BST(value)
return this
}
})But you could use a closure so that only one prototype obj is created in memory const BST = (() => {
const BSTPrototype = {
insert(value) {
if (value < this.value) this.left = this.left ? this.left.insert(value) : BST(value)
if (value > this.value) this.right = this.right? this.right.insert(value) : BST(value)
return this
}
}
return value => {
const bst = Object.create(BSTPrototype)
bst.value = value
return bst
}
})() |
|
Hey @skatcat31
Yes I agree, I believe we are currently of the same mind. @Chalarangelo I have to agree with @skatcat31 concerning the following statement
I am also for classes due to simplicity, consistency, & all the reasons @skatcat31 described above For example implementing a LinkedList should be implemented like the following, and currently can't think of any other implementation that could out way the benefits of using classes class LinkedList {
constructor(head, ...tail) {
this.head = head;
this.tail = tail.length ? new LinkedList(...tail) : null;
}
add(item) {
(this.tail) ? this.tail.add(item) : this.tail = new LinkedList(item);
}
} |
|
We are not doing classes, as this would lead to a huge host of issues with contribution guidelines and other things. Even with the tiny amount of rules we are enforcing on people, contributors have difficulty following them and PRs need some cleaning up 90% of the time. If we start doing classes, we will be causing a lot more harm than good to the project. The original scope was to provide a learning resource for people to understand and learn modern JS and showcase cool features. While classes are cool and extremely useful, they are not instantly understandable and OOP takes a lot of time to wrap your head around. JS is mainly based on prototypes and classes are a relatively new addition, which confuses a lot of developers and that many people I know just entirely avoid. Apart from that, we are following a functional style. Adding OOP would be kind of against this. Same thing applies to data structures. They take a lot of time to learn, their usefulness is not immediately apparent and it is something that most people in web development are not going to care for when starting out. Our user meta is in the beginner-intermediate range and these are quite advanced concepts that require some background in computer science. I have studied CS for almost 7 years now and I have never once used a BST or Linked List in a project (I have done like 50 of them, the majority were web-based). It's just something that doesn't come up as often and, even if it did, 30 seconds is not the place to teach people that kind of thing. I'm all for adding a list linking to resources/libraries/articles for people to learn more advanced concepts and use them, but doing it ourselves would take up a lot of time, impact maintenance and change the very definition of the project. We have so many simpler things to focus on, so many cool micro-packages on npm we can try our hand on and functional libraries that we can get inspiration from. I do not think we shall put those on the backburner in favor of data structures now or ever. TL;DR
I'm voting to close this issue and all PRs related to it and move back to things like implementing methods under #100 and similar libraries. We spent far too much time discussing this and prototyping ideas for something we have no reason to implement. Having read through a lot of criticism for the repo, nobody has ever brought up the lack of data structure snippets, so apparently it's not something that comes up often in reference to the project. |
|
Thoughts I wrote in the chat:
|
@Chalarangelo Right, close it. |
|
This thread has been automatically locked since there has not been any recent activity after it was closed. Please open a new issue for any follow-up tasks. |
[SUGGESTION] Adding The Following Categories: Trees, Linked List, Double Linked List, Graph, Trie, Stack, & Queue
Description
I believe adding other categories representing different operations/manipulation of other data structures other than arrays / objects can also be beneficial to the project.
I think its important for the following reasons: exposure, growth, performance, and simplicity
An example of this would be
Math.max()which is native and takes variadic inputsBut then we had
arrayMax()Then we made
max()take both variadic & arrays. Which I regret & I partially take credit for see #295Then #419 happened
Now there's #463
I honestly believe separating methods by their data structure would be best, and would prevent what was described above from repeating itself. Especially when looking at the following example
For example let's say we want create a function that can find the maximum number from a particular data structure
Example
Array
max
Binary Tree
max
Linked List
max
As you can see moving the project in this direction will not only prevent what was described with the following issues #295 | #419 | #463 from repeating them selves. But also keep snippetNames simple when adding to their respective categories.
Thoughts? @atomiks @skatcat31 @fejes713 @Chalarangelo
The text was updated successfully, but these errors were encountered: