“Throw a hash map at it and hope for the best” I gave my friend that advice when we were both looking for a job our senior year of college. He told me a few weeks later that he was in an interview and had no idea what to do so he pulled out the hash map quote. The interviewer didn’t even bother having him implement it, they just said alright you sound like you know the approach we can continue
Nice ... in my advanced graduate algorithms course now ... half-way to MS in CS at age 63. If you're in CS you will have to know all of those. Basic data structures. Great vids as always.
I am in my final year of my CS degree and I am going back to relearn a lot of basics because I half assed my way to where I am but I have grown to like the program and want to be competent. Tho don’t tell my boss
Consider these actionable insights from the video: 1. Learn about arrays to store collections of data of the same type. 2. Explore linked lists when you need to efficiently insert or delete elements in a list. 3. Understand stacks if your project requires managing data in a last-in-first-out manner. 4. Utilize queues to process data in a first-in-first-out order, like managing tasks. 5. Implement hash tables to store and retrieve data using key-value pairs for fast access. 6. Master trees for representing hierarchical data and conducting efficient searches. 7. Dive into heaps when you need to find the minimum or maximum value efficiently. 8. Study graphs to represent and analyze relationships between objects or entities.
linked lists are rarely the best solution. "array lists" which are Lists implemented using fixed size arrays, perform much better with the cache, use a lot less RAM, and are in general faster for almost all use cases.
I remember watching 1 or 2 of ur vids 8 months ago and i lost interesst and couldnt find the value.. now after hardcore 8 months of studying and practicing programing, system management and recently math.. i think this is the most valuable YT channel ive seen.. obv im not comparing it to freecode camp.. but obv ur not in the same nieche .. just went trough clearing the nonvaluable yt channels ive subscribed too and u are one of the fews i left there.. super cool, inspiring, relatable, and informative ofc!! :)
I've got a very visual mind: a tree is a specific type of graph, and if you think about it, so is a linked list. I love graph theory, I'm not very good at it, but I do love it. I enjoyed your comment about naming the same thing upteen different ways just to be confusing 😀
You can make a resizable array queue with amortized O(1) enqueue complexity, you just have to increase the size enough every time you're doing so. For example increasing the size to double the previous size will be O(1) on average since you are not increasing it most of the time
Two things to check with your solder: 1. Is it rosin core? If not, then you're going to have a hard time forever, so I would recommend upgrading. 2. Lead free solder is harder to work with as well. I use leaded solder and if you're concerned about safety then I would recommend using a mask. But I don't like lead free because it gets cold too quick
One thing never mentioned with hash maps is the performance of them, they are a heavy algorithm and will most likely slower than an array for looking up a value. One advantage arrays have is the ability to use multiple threads to divide the array up into smaller blocks to search through, but you can escape the time needed to calculate the hash and these usually don’t scale as well and can’t take advantage of multithreading. But these are essential tools for all computer science.
Are you planning on making a "The making of : Git" ? I'm kind of curious and your documentaries are.... Honestly the only kind that can keep my interest. The history. the visuals. Specially the speech pattern . can't explain it , its not just the enunciation on words , or the steady speed between , not too slow and not too fast ,but like you know what you are talking about. Not just a fact blurb , so you can logically follow the line of thought behind the product. Love it man.
I just started learning python the other day and this information I feel like is something I’m going to have to learn depending on what I want to do I really appreciate this video this is good information !
In .NET, all these structures are implemented via an Array by the base class library authors. Queue, Stack, List, LinkedList, etc., are just constructs to make their usage easier for the average .NET developer. Of course, BCL authors also put optimizations in the BCL constructs that make their usage faster than it would be for you to implement just an array, like via pointers and other methods not appropriate for most to use.
There's an asterisk on Linked Lists nowadays because most processors REALLY love their locality, a Linked List is almost always going to lose to a regular array, even if you relocate the whole thing. Exceptions are VERY VERY large lists and the Producer/Consumer pattern, where they still make sense.
"Generic" trees and many other data structures have the same drawback. Just learn how to manage memory efficiently, and locality will increase significantly.
Nice video. It might be that experience with data structures and algorithms is one of the key differentiators between more and less productive programmers.
On queues, my favorite data structure > What governs traffic on the internet? Queues! What governs process management in a computer? Queues! What governs your check-out and pay trivia at the supermarket? Queues! Who invented queuing theory? A Dane named Erlang - An Erlang is the international standard unit of traffic - and traffic in general is modeled using? queues! I love queues! /A very happy Dane
be careful making statements about performance (big o) in modern processors: true arrays are super performant in many use cases due to cpu cache use. data locally may trump big-o analysis
What questions do you have? Or what do you mean by corresponding questions? I have a master's in CS and work in a FAANG company so I may be able to answer your questions
first arrays : creates a python list with python ints, wich in itself is an object , that is a whole tree of fuctionallity that o has a hashmap pointing to objects (in this case a python int) in c an array would be the sum of he size of its elements, in python its not :), not dunking on the whole video , i like it actually just saying , that while python might look like pseudocode and makes it easy to explain stuff , be carefull not to actually cause beginners to have the wrong idea or assumption that has to be unlearned at some point, in this case i would have gone with plain old C, as for these thins C is actually really easy to understand , it also would have forced you to do what you said in the definition : set its size to a fixed number of elements
I'm a web developer who delivers Amazon packages. One of the station supervisors at my sorting station used to build software as a service. I've met doctors who drove cabs, and chefs who used to be web developers, too. People who stay in one job all their lives are missing out on life.
Hey Forest! I’ve been following your videos for a while now, and I really love your content. I would greatly appreciate it if you could make a video about Spring Boot.
Stacks and Queues and Graphs aren't "data structures" they are Abstract Data Types. You can implement a stack with a LinkedList, an array or something else. Same as queues. For graphs you can implement them as a collection of nodes, an adjacency matrix, or with adjacency lists. ADTs are the definition of operations such as Stacks and Queues, Data Structures are the ways we implement them.
they are indeed data structures as well. They are a way to structure data. Graphs live more on the edge of that definition, but they are a way to organize data. As I said for graphs, you're right that there are different implementations of them which is why they live on the edge.
@@hawks3109 they aren't "ways to structure data" they are a definition of an API that is LIFO or FIFO. The way to structure the data is via an array, a linked list or a tree implementation. Those are the data structures. Lots of confusion between Data Structure (the way to structure data, the implementation) and the Abstract Data Type (the list of operations that define the interface of the operation)
It’s worth noting, that Python also allows storing different data types in a single list. In fact, this capability is common to all dynamically typed languages.
And many statically typed languages which have a large runtime (like go for instance) have the same ability, in go you can just do this: var some [4]interface{}
this is not actually true. python lists (and other containers) store pointers to any python type. to the user it seems as though a list can store multiple type simultaneously but in reality the type it stores is always a pointer to a python object. storing fixed size data is very important because you can easily calculate it’s memory location from the index and the list start. if you cannot guarantee the size it’s a linear search. for example see why you cannot just index into UTF-8 strings
@@soothsayer1interfaces in the golang runtime are always pointers, for the same reason noted above. if you want an array with multiple types of elements, the way without using a pointer is a union type. the rust enum implementation is one such example
@@simpletongeek a union is a block of memory that can be interpreted as multiple types at the same time. so you can have a 4 byte int and a byte 4 array simultaneously. an interface is a pointer to a block of memory. the interface is also an agreement about the methods that can be run on it. this way you can call the same methods without knowing which type it is. but the important bit, is that an interface is only one of it’s types while a union is simultaneously all of it’s types
elements. elements is the word you were looking for when discussing array size. Arrays have a fixed number of elements, defined when the array is created.
So a queue is essentially an array where you only access the first or last element.Then if we make an array and only use it in this exact way, why wouldn't it be equally efficient with insertion and deletion? Also a hash table is essentially a double array. Instead of accessing an element by index, you now have to access it by a key referencing an index referencing an element. How is this more efficient exactly? How come the array isn't more efficient or at least equal compared to both queues and hash tables?
Adding an element at the end of an array is a bit costly because you need to maintain the contiguity of your elements. If the next memory emplacement after your current last element is free, then that's fine, but if it's not, you'll have to allocate a new contiguous block of memory long enough for all your elements and copy all the old elements plus the new one in this new emplacement. That makes "adding an element at the end of an array" a very inefficient operation in O(n). There are ways around that, see dynamic arrays for extensible arrays where the addition of an element is amortised O(1), but at this point, you're not just using a plain old array! And deleting the first element repetitively raises a similar problem of reclaiming the freed memory from time to time if you want to avoid a memory leak, which you probably want to, given the tendency to use queues in some long running processes. For hash table, they're essentially arrays (probably a kind of dynamic arrays, customised for this usage) underneath. The essential distinction is how you access them, the primitives you're using to manipulate them so that finding the value associated to a key is constant time (in relation to the number of keys in the hash table).
@@chaddaifouche536 Thanks for your answer! Does that mean that dynamic arrays have both the benefits of arrays and queues then? So you would really only need to care about the differences between them if you are working on legacy code. Otherwise you would just always use dynamic arrays. Did I get that right? And about hash tables, does that mean that if you need to sort or somehow rearrange the data, you don't actually sort or rearrange the values, only the keys? I can see how that would be useful over arrays if I was working with large data elements.
@@MrPellenisse Well, you're kinda right, in certain contexts where you don't care that much about performance, and kinda wrong in scenario where performance is critical… In general, if you want peak performance, you should use the data structure that fulfils your needs exactly, and no more, because any extra facilities are probably paid for in lesser performances in some operations, even if it's not reflected in the big O, or more memory usage. For instance, dynamic arrays need to reserve more memory than what they're actually using, and keep track of the length of reserved memory and the parts of the array underneath that are really used. In many (most) cases, you don't really care for the small difference in performance that would entail. For instance, Python took exactly your stance when it decided to provide "list" as its standard "array" data structure, since Python's "list" are in fact heterogeneous dynamic arrays with extra bells and whistles! On the other hand, when someone *needs* to do numeric computing in Python, using the standard lists is a terrible idea and the right decision is probably to use something like the numpy arrays (that are real typed arrays, not dynamically typed dynamic array like list). You may have orders of magnitude better performance this way. -- About hash tables, I don't think you've grasped their main advantage yet : the main "advantage" of an hash table compared to arrays is that instead of numeric indices that *have* to be consecutive, you can use any subset of an immutable type as keys (most frequently strings) and access the corresponding value in O(1). They're basically arrays where the "indices" are the names of your customers, for example. You may maintain an array of keys separately and order it as you wish but that's independent of the fact you're using an hash table (you may do the same thing with the indices of an array, after all). Hash tables are sometimes called dictionary, or associative arrays, reflecting their functionality rather than their implementation (dictionaries can also be implemented with binary search trees with O(log n) consultation and insertion instead).
@@chaddaifouche536 Thanks for your explanation! It does clarify a few things. So then you are saying that a hash table can't be accessed by an index value at all, but ONLY by its key? Is that correct? Otherwise the hash table would have both indexes AND keys pointing to the same value, which is how I thought they worked. It seems to me that hash tables would still only be useful for large datasets where you need to access values out of order. Usually when working with arrays, you use them exactly because you actually want to iterate through every single element in some loop anyways, making index values mandatory and keys simply redundant.
Writing linked lists is a good programming exercise but you should NOT use them in production code because they have terrible cache locality. Having your working set in the CPU cache is critical for performance.
It's BS an array in particular only contains one type of data. That depends on the language. I'd go so far to say that every data structure has the same property in that regard. In a strongly-typed language all data structures only store one type of data, and in a dynamically-typed one (like your python example), they usually hold every type.
@@hansjhansen2217 I certainly won't. It's not informative for anyone that got past page 30 in the tutorial of whatever programming language they started with, and even misleading in some regards, see my comment above. What do you think is wrong about my statement? In Python an "array" (which btw is not an array) can hold every kind of object. In C++ any datastructure can only contain the type with which the template was initialised.
@@gehirndoper He is stating the principel of an array. That different program languages “expands” the definition doesn’t change what he is saying is true.
You left out 2 data structures that I thought were most powerful (especially for graph searching). PriorityQueue (priority queue) Deque (double ended queue)
particular programming language biased. arrays arent always fixed width or only store one datatype. anyhow, everything is a linked list, with a feature or two added.
I was wondering if you may go deeper in another video series for each data structure with a coding example on how to build them and where we can find them in real world applications?
Slow down, and use consistent techniques (that follow a consistent order of deliver), if you really want to help people. I am tired and finding it hard to follow you, even tho I have used all of these technniques, and it's a shame, because i'd like to find content I can share with other people who could do with understanding these concepts. Doing it per language could be great for views btw. ✌
The one point I disagree with is about the definition of an array. Same type for each slot and contiguous memory storage, yes, but not statically sized. And there's a lot more complexity to hash tables if you care to make a more complete description there. You have different hashing algorithms, balancing schemes, and even storage methods. For instance, in one implementation, I made the storage backing for a hash table as a balanced tree and each node was also part of an interlaced series of trees that were the chains. It used up a lot more memory than either a tree or a hash table alone, but it was an interesting experiment in maintaining sorted order while yielding slightly faster searches.
It depends on the language and exact type of array being used. Higher level languages do tend to muddy the waters a bit with static vs dynamic sizing of arrays, but lower level languages, especially systems languages, tend to define arrays as being of a fixed, statically known size, since the memory that the array occupies is typically allocated in-place, either from the stack or as part of another object that the array resides within. The compiler needs to know the size of the array to know how much memory it occupies, so arrays in lower level languages tend to come with the restriction that the size be fixed and statically known, and if you need a dynamically sized array then you typically go with a vector which allocates the memory backing the array from the heap.
@@jcm2606 Yeah, it doesn't matter whether it's from the heap or stack, all allocations in a computer are dynamic while at runtime. Yes, even a stack allocated array can be resized in place, with a few caveats.
1:45 JS stands for just sucks. Non static typing is stupid. Just like the mixed "array" types. As someone whos been around coding and electronics embedded engineering stuff. I like html, css is fine, Java was interesting, C++ was nice, arduino version of C also very nice and deobfuscated. Javascript? Just terrible. Also any class about only using JS to make html is hell and im glad i dont have much use for besides inserting a few minimal things for sensor data being updated for me
Just chiming in to trash JavaScript... there is no array at all, it is literally an object like any other, except with the property names as contiguous integers. So, since all JS objects are hashmaps, it's a hashmap. You can add functions properties ("methods") with regular names or do anything else.
that's why i stopped learning cobol ...no dynamic memory allocation, lol i have since 'grown up' and realize, you don't always need dynamic memory, choose the right tool for the job! in fact, run this code on your computer and see how fast it 'recovers' : def sum_odd_evens1(np_ary): r1 = sum(np_ary[np_ary%2!=0]) r2 = sum(np_ary[np_ary%2==0]) return (r1,r2) def main(): num = [n for n in range(1,1000000000)] np_num = np.array(num) res = sum_odd_evens1(np_num) print(res) i may not have waited long enough but, i think there may be a memory leak in my python3 interpreter (new one installed with most recent update)
![[MV] A leap of faith...ความเชื่อใจครั้งสุดท้าย (From "Petrichor the series")](http://i.ytimg.com/vi/U1piZH2CNXA/mqdefault.jpg)
“Throw a hash map at it and hope for the best”
I gave my friend that advice when we were both looking for a job our senior year of college.
He told me a few weeks later that he was in an interview and had no idea what to do so he pulled out the hash map quote. The interviewer didn’t even bother having him implement it, they just said alright you sound like you know the approach we can continue
Sounds about right 😂😂😂😂😂
I Also wowed my first job/boss by basically using a hashmap where it was vaguely applicable lol.
😂💀
Hashmaps saved my life more than once lol
(Furiously takes notes for interview)
Nice ... in my advanced graduate algorithms course now ... half-way to MS in CS at age 63. If you're in CS you will have to know all of those. Basic data structures. Great vids as always.
Wow, great. It's commendable. Do you feel anything different than say you were studying in your 20s? Keep it up, sir.
I am in my final year of my CS degree and I am going back to relearn a lot of basics because I half assed my way to where I am but I have grown to like the program and want to be competent.
Tho don’t tell my boss
I tried in my 40's but I had too much going on to focus on 3d calculus..
What is ms and cs?
Lmao dude same@@dalitsobanda7658
As a graduate of computer science 30 years ago, I wish I had a lecturer like this. You have a knack for educating people. Well done!
You sound and intonate almost exactly like Dave from Dave's Garage - it's amazing. You explained the data structures very clearly and concisely.
Consider these actionable insights from the video:
1. Learn about arrays to store collections of data of the same type.
2. Explore linked lists when you need to efficiently insert or delete elements in a list.
3. Understand stacks if your project requires managing data in a last-in-first-out manner.
4. Utilize queues to process data in a first-in-first-out order, like managing tasks.
5. Implement hash tables to store and retrieve data using key-value pairs for fast access.
6. Master trees for representing hierarchical data and conducting efficient searches.
7. Dive into heaps when you need to find the minimum or maximum value efficiently.
8. Study graphs to represent and analyze relationships between objects or entities.
linked lists are rarely the best solution. "array lists" which are Lists implemented using fixed size arrays, perform much better with the cache, use a lot less RAM, and are in general faster for almost all use cases.
Great summary!
I use stacks for parsing structured, nested data. It's about the only time I use them, but then they're invaluable.
I remember watching 1 or 2 of ur vids 8 months ago and i lost interesst and couldnt find the value.. now after hardcore 8 months of studying and practicing programing, system management and recently math.. i think this is the most valuable YT channel ive seen.. obv im not comparing it to freecode camp.. but obv ur not in the same nieche .. just went trough clearing the nonvaluable yt channels ive subscribed too and u are one of the fews i left there.. super cool, inspiring, relatable, and informative ofc!! :)
Having context makes all the difference for videos like this!
This is the most digestible explanation of these concepts i’ve ever seen. Hats off!
Dude, no way I wasn't going to subscribe! What I should've learned years ago about programming I just learned in 17 minutes! Thanks good sir!
I've got a very visual mind: a tree is a specific type of graph, and if you think about it, so is a linked list. I love graph theory, I'm not very good at it, but I do love it. I enjoyed your comment about naming the same thing upteen different ways just to be confusing 😀
🤯 the best “array” explanation ever. You make code logic feel… logic, thinking as “storage” makes total sense for me. Thanks!
You can make a resizable array queue with amortized O(1) enqueue complexity, you just have to increase the size enough every time you're doing so. For example increasing the size to double the previous size will be O(1) on average since you are not increasing it most of the time
Two things to check with your solder:
1. Is it rosin core? If not, then you're going to have a hard time forever, so I would recommend upgrading.
2. Lead free solder is harder to work with as well. I use leaded solder and if you're concerned about safety then I would recommend using a mask. But I don't like lead free because it gets cold too quick
Thanks for the informative video, btw whats that liquid cooler in your rig?
I really enjoyed this video, thanks. It reminded me how much I know and also connected some vertices in my mind..
This was kind of fascinating for me, I need to find some example labs for each in a couple of languages to satisfy my own curiosity now.
One thing never mentioned with hash maps is the performance of them, they are a heavy algorithm and will most likely slower than an array for looking up a value. One advantage arrays have is the ability to use multiple threads to divide the array up into smaller blocks to search through, but you can escape the time needed to calculate the hash and these usually don’t scale as well and can’t take advantage of multithreading. But these are essential tools for all computer science.
Great video. Thanks for sharing.
I chuckled a few times at this, especially the vertex/node joke. Subscribed.
Are you planning on making a
"The making of : Git" ?
I'm kind of curious and your documentaries are.... Honestly the only kind that can keep my interest. The history. the visuals. Specially the speech pattern . can't explain it , its not just the enunciation on words , or the steady speed between , not too slow and not too fast ,but like you know what you are talking about.
Not just a fact blurb , so you can logically follow the line of thought behind the product.
Love it man.
I just started learning python the other day and this information I feel like is something I’m going to have to learn depending on what I want to do I really appreciate this video this is good information !
In .NET, all these structures are implemented via an Array by the base class library authors. Queue, Stack, List, LinkedList, etc., are just constructs to make their usage easier for the average .NET developer. Of course, BCL authors also put optimizations in the BCL constructs that make their usage faster than it would be for you to implement just an array, like via pointers and other methods not appropriate for most to use.
There's an asterisk on Linked Lists nowadays because most processors REALLY love their locality, a Linked List is almost always going to lose to a regular array, even if you relocate the whole thing. Exceptions are VERY VERY large lists and the Producer/Consumer pattern, where they still make sense.
"Generic" trees and many other data structures have the same drawback. Just learn how to manage memory efficiently, and locality will increase significantly.
Nice video. It might be that experience with data structures and algorithms is one of the key differentiators between more and less productive programmers.
Imagine saying data instead of data.
This is so amazing, Thank you.
On queues, my favorite data structure >
What governs traffic on the internet? Queues!
What governs process management in a computer? Queues!
What governs your check-out and pay trivia at the supermarket? Queues!
Who invented queuing theory? A Dane named Erlang - An Erlang is the international standard unit of traffic - and traffic in general is modeled using? queues!
I love queues! /A very happy Dane
Thanks for sharing this
I do learn quite a lot from your great tutorials 📖💻 Thank you for providing such great content 😊
Data Structures by Matthew Mcconaughey. Alright, Alright, Alright. great video
Nice video!
You should have done the animation for the Stack segment in PostScript... A stack based language. :)
be careful making statements about performance (big o) in modern processors: true arrays are super performant in many use cases due to cpu cache use. data locally may trump big-o analysis
You look like you smell like wood
His name is ForrestKnight, seems plausible
🤣🤣🤣🤣🤣🤣
My father was a lumberjack. Gasoline and balsam. Its a magical smell.😂
I'm getting deep oak vibes, with hints of moss.
I get it, a smoky wood too
You are a good teacher. I'm a noob, and I understood everything
Excellent presentation. You have a new subscriber (me).
Python " arrays" are actually lists. And they can contain a mixture of data types.
Trees can also be used for creating file systems
Could you create a video with corresponding questions to each data structure?
What questions do you have? Or what do you mean by corresponding questions? I have a master's in CS and work in a FAANG company so I may be able to answer your questions
Thx!
first arrays : creates a python list with python ints, wich in itself is an object , that is a whole tree of fuctionallity that o has a hashmap pointing to objects (in this case a python int)
in c an array would be the sum of he size of its elements, in python its not :), not dunking on the whole video , i like it actually just saying , that while python might look like pseudocode and makes it easy to explain stuff , be carefull not to actually cause beginners to have the wrong idea or assumption that has to be unlearned at some point, in this case i would have gone with plain old C, as for these thins C is actually really easy to understand , it also would have forced you to do what you said in the definition : set its size to a fixed number of elements
Wow, I wasn't expecting the TH-cam algorithm to suggest I learn about data structures from a gas station clerk.
😂
I'm a web developer who delivers Amazon packages. One of the station supervisors at my sorting station used to build software as a service. I've met doctors who drove cabs, and chefs who used to be web developers, too.
People who stay in one job all their lives are missing out on life.
You're a savage 😂😂😂
@@PhilLesh69you missed the joke buddy 😂
@PhilLesh69 -- I didn't say he wasn't knowledgeable, it was a good video. But, come on, the dude gives vibes like he regularly goes ATV'n.
Another thing every programmer should know is, what brand of chair is that you're sitting on? Does it have a cloth backing?
Thanks!
Hey Forest! I’ve been following your videos for a while now, and I really love your content. I would greatly appreciate it if you could make a video about Spring Boot.
Stacks and Queues and Graphs aren't "data structures" they are Abstract Data Types. You can implement a stack with a LinkedList, an array or something else. Same as queues. For graphs you can implement them as a collection of nodes, an adjacency matrix, or with adjacency lists.
ADTs are the definition of operations such as Stacks and Queues, Data Structures are the ways we implement them.
they are indeed data structures as well. They are a way to structure data. Graphs live more on the edge of that definition, but they are a way to organize data. As I said for graphs, you're right that there are different implementations of them which is why they live on the edge.
@@hawks3109 they aren't "ways to structure data" they are a definition of an API that is LIFO or FIFO. The way to structure the data is via an array, a linked list or a tree implementation. Those are the data structures.
Lots of confusion between Data Structure (the way to structure data, the implementation) and the Abstract Data Type (the list of operations that define the interface of the operation)
Man this is a great video
This video is great and makes these topics easy to understand, thank you so much Forrest!
My guy finished a day in the coal mines and came home to teach data structures! (can I get a link to that flannel? :D )
Been diving into Elixir recently, and that language will have you question how you've thought about data structures before. I know the pop
I love your stile :D
Great video.
where did you buy that keyboard?
Great video! Thank you sir !
Every developer should know what sets & bags are.
And Union-Find "reverse trees".
Could you do a video about the job market situation currently?
Why do you need him to tell you that the job market is ass?
ladies and gentlemen i think my brain committed suicide; but it's the exact information i need to solve a problem so it's well worth
Please keep the pictures of examples and descriptions longer.
yo i have a mustache and my name is forrest. i subbed. did you also start with “hey my neighbors” 😂
It’s worth noting, that Python also allows storing different data types in a single list.
In fact, this capability is common to all dynamically typed languages.
And many statically typed languages which have a large runtime (like go for instance) have the same ability, in go you can just do this: var some [4]interface{}
this is not actually true. python lists (and other containers) store pointers to any python type. to the user it seems as though a list can store multiple type simultaneously but in reality the type it stores is always a pointer to a python object.
storing fixed size data is very important because you can easily calculate it’s memory location from the index and the list start. if you cannot guarantee the size it’s a linear search. for example see why you cannot just index into UTF-8 strings
@@soothsayer1interfaces in the golang runtime are always pointers, for the same reason noted above. if you want an array with multiple types of elements, the way without using a pointer is a union type. the rust enum implementation is one such example
Why does that sound like Unions in C?
@@simpletongeek a union is a block of memory that can be interpreted as multiple types at the same time. so you can have a 4 byte int and a byte 4 array simultaneously. an interface is a pointer to a block of memory. the interface is also an agreement about the methods that can be run on it. this way you can call the same methods without knowing which type it is. but the important bit, is that an interface is only one of it’s types while a union is simultaneously all of it’s types
elements. elements is the word you were looking for when discussing array size.
Arrays have a fixed number of elements, defined when the array is created.
I liked this video a lot, really does remind me of my first year in CS
Great explanation
Wasn’t that Python array example actual a list?
This is what matthew maconeghey (?) would sound and look like teaching CS
I like this guy 😅
I don’t want to escape Java
Thumbnail had a graphic that I assume is a reference to state machines, a sub study of graphs, but no mention of it in the video?
I think ur talking about hash map
this isnt really a beginners guide but a "im already familiar with all of these terms and many other adjacent concepts"
I'm fairly sure the heap in JVM has nothing to do with a heap data structure.
No visual for heaps?
Why do you call the Python list array?
3:15 why are you using Python for the array examples when Python uses lists?
He explains there's a difference between arrays and lists literally seconds before that lmao
Amazing video. Does any know what type of font he use?
So a queue is essentially an array where you only access the first or last element.Then if we make an array and only use it in this exact way, why wouldn't it be equally efficient with insertion and deletion? Also a hash table is essentially a double array. Instead of accessing an element by index, you now have to access it by a key referencing an index referencing an element. How is this more efficient exactly? How come the array isn't more efficient or at least equal compared to both queues and hash tables?
Adding an element at the end of an array is a bit costly because you need to maintain the contiguity of your elements. If the next memory emplacement after your current last element is free, then that's fine, but if it's not, you'll have to allocate a new contiguous block of memory long enough for all your elements and copy all the old elements plus the new one in this new emplacement.
That makes "adding an element at the end of an array" a very inefficient operation in O(n). There are ways around that, see dynamic arrays for extensible arrays where the addition of an element is amortised O(1), but at this point, you're not just using a plain old array!
And deleting the first element repetitively raises a similar problem of reclaiming the freed memory from time to time if you want to avoid a memory leak, which you probably want to, given the tendency to use queues in some long running processes.
For hash table, they're essentially arrays (probably a kind of dynamic arrays, customised for this usage) underneath. The essential distinction is how you access them, the primitives you're using to manipulate them so that finding the value associated to a key is constant time (in relation to the number of keys in the hash table).
@@chaddaifouche536 Thanks for your answer! Does that mean that dynamic arrays have both the benefits of arrays and queues then? So you would really only need to care about the differences between them if you are working on legacy code. Otherwise you would just always use dynamic arrays. Did I get that right?
And about hash tables, does that mean that if you need to sort or somehow rearrange the data, you don't actually sort or rearrange the values, only the keys? I can see how that would be useful over arrays if I was working with large data elements.
@@MrPellenisse Well, you're kinda right, in certain contexts where you don't care that much about performance, and kinda wrong in scenario where performance is critical…
In general, if you want peak performance, you should use the data structure that fulfils your needs exactly, and no more, because any extra facilities are probably paid for in lesser performances in some operations, even if it's not reflected in the big O, or more memory usage. For instance, dynamic arrays need to reserve more memory than what they're actually using, and keep track of the length of reserved memory and the parts of the array underneath that are really used.
In many (most) cases, you don't really care for the small difference in performance that would entail. For instance, Python took exactly your stance when it decided to provide "list" as its standard "array" data structure, since Python's "list" are in fact heterogeneous dynamic arrays with extra bells and whistles! On the other hand, when someone *needs* to do numeric computing in Python, using the standard lists is a terrible idea and the right decision is probably to use something like the numpy arrays (that are real typed arrays, not dynamically typed dynamic array like list). You may have orders of magnitude better performance this way.
--
About hash tables, I don't think you've grasped their main advantage yet : the main "advantage" of an hash table compared to arrays is that instead of numeric indices that *have* to be consecutive, you can use any subset of an immutable type as keys (most frequently strings) and access the corresponding value in O(1). They're basically arrays where the "indices" are the names of your customers, for example.
You may maintain an array of keys separately and order it as you wish but that's independent of the fact you're using an hash table (you may do the same thing with the indices of an array, after all). Hash tables are sometimes called dictionary, or associative arrays, reflecting their functionality rather than their implementation (dictionaries can also be implemented with binary search trees with O(log n) consultation and insertion instead).
@@chaddaifouche536 Thanks for your explanation! It does clarify a few things.
So then you are saying that a hash table can't be accessed by an index value at all, but ONLY by its key? Is that correct? Otherwise the hash table would have both indexes AND keys pointing to the same value, which is how I thought they worked.
It seems to me that hash tables would still only be useful for large datasets where you need to access values out of order. Usually when working with arrays, you use them exactly because you actually want to iterate through every single element in some loop anyways, making index values mandatory and keys simply redundant.
A queue is a special type of list, not array
Writing linked lists is a good programming exercise but you should NOT use them in production code because they have terrible cache locality. Having your working set in the CPU cache is critical for performance.
Python list is not an array. But Numpy array is.
Hi, can I please get a link for your keyboard? It looks awesome and I wanna buy one, thanks.
Valuable content
It's BS an array in particular only contains one type of data. That depends on the language. I'd go so far to say that every data structure has the same property in that regard. In a strongly-typed language all data structures only store one type of data, and in a dynamically-typed one (like your python example), they usually hold every type.
Maybe Watch the video again
@@hansjhansen2217 I certainly won't. It's not informative for anyone that got past page 30 in the tutorial of whatever programming language they started with, and even misleading in some regards, see my comment above. What do you think is wrong about my statement? In Python an "array" (which btw is not an array) can hold every kind of object. In C++ any datastructure can only contain the type with which the template was initialised.
@@gehirndoper He is stating the principel of an array. That different program languages “expands” the definition doesn’t change what he is saying is true.
Python only has lists built in.
Super video.
Unlike arrays linked lists don’t have any real world usage
bro im a nurse teaching myself how to code and this is excellent stuff thank you!
You left out 2 data structures that I thought were most powerful (especially for graph searching).
PriorityQueue (priority queue)
Deque (double ended queue)
Circular buffers 🙂
Ah , yes, a nightmare for most of the computer science students😂
vectors/dynamic arrays kind of make linked lists obsolete.
Linked list were made for what arrays -- dynamic or not -- are not good at.
particular programming language biased. arrays arent always fixed width or only store one datatype.
anyhow, everything is a linked list, with a feature or two added.
I was wondering if you may go deeper in another video series for each data structure with a coding example on how to build them and where we can find them in real world applications?
“JS arrays aren’t technically arrays”
*Uses a Python list to demonstrate arrays*
😅😜
Good video! 👍
Thanks
*laughs in JavaScript*
Slow down, and use consistent techniques (that follow a consistent order of deliver), if you really want to help people.
I am tired and finding it hard to follow you, even tho I have used all of these technniques, and it's a shame, because i'd like to find content I can share with other people who could do with understanding these concepts.
Doing it per language could be great for views btw. ✌
Looks more like a dude that been in the garage workin on cars.
Python is just BASIC relabeled
I just use arrays.
True golden nugget. In 17 minutes, you simplified what my professor couldn't in hours of lectures!!!
The one point I disagree with is about the definition of an array. Same type for each slot and contiguous memory storage, yes, but not statically sized. And there's a lot more complexity to hash tables if you care to make a more complete description there. You have different hashing algorithms, balancing schemes, and even storage methods. For instance, in one implementation, I made the storage backing for a hash table as a balanced tree and each node was also part of an interlaced series of trees that were the chains. It used up a lot more memory than either a tree or a hash table alone, but it was an interesting experiment in maintaining sorted order while yielding slightly faster searches.
It depends on the language and exact type of array being used. Higher level languages do tend to muddy the waters a bit with static vs dynamic sizing of arrays, but lower level languages, especially systems languages, tend to define arrays as being of a fixed, statically known size, since the memory that the array occupies is typically allocated in-place, either from the stack or as part of another object that the array resides within. The compiler needs to know the size of the array to know how much memory it occupies, so arrays in lower level languages tend to come with the restriction that the size be fixed and statically known, and if you need a dynamically sized array then you typically go with a vector which allocates the memory backing the array from the heap.
@@jcm2606 Yeah, it doesn't matter whether it's from the heap or stack, all allocations in a computer are dynamic while at runtime. Yes, even a stack allocated array can be resized in place, with a few caveats.
1:45 JS stands for just sucks. Non static typing is stupid. Just like the mixed "array" types. As someone whos been around coding and electronics embedded engineering stuff. I like html, css is fine, Java was interesting, C++ was nice, arduino version of C also very nice and deobfuscated. Javascript? Just terrible. Also any class about only using JS to make html is hell and im glad i dont have much use for besides inserting a few minimal things for sensor data being updated for me
Just chiming in to trash JavaScript... there is no array at all, it is literally an object like any other, except with the property names as contiguous integers. So, since all JS objects are hashmaps, it's a hashmap. You can add functions properties ("methods") with regular names or do anything else.
does primeagen have a twin brother?
Nice explanation, but the heap comes a little short here ;)
Fixed size arrays are boring
that's why i stopped learning cobol ...no dynamic memory allocation, lol i have since 'grown up' and realize, you don't always need dynamic memory, choose the right tool for the job! in fact, run this code on your computer and see how fast it 'recovers' : def sum_odd_evens1(np_ary):
r1 = sum(np_ary[np_ary%2!=0])
r2 = sum(np_ary[np_ary%2==0])
return (r1,r2)
def main():
num = [n for n in range(1,1000000000)]
np_num = np.array(num)
res = sum_odd_evens1(np_num)
print(res)
i may not have waited long enough but, i think there may be a memory leak in my python3 interpreter (new one installed with most recent update)