How Data Structures & Algorithms are Actually Used

all right hey my name is Forest welcome back so lately I've talked about some algorithms and I've talked about some data structures I've shown what they look like how the code behind them works why it's important to choose right ones and mentioned how they're used but it's been brought to my attention that I haven't shown how they're used in real world applications take a social media app for example every single one has a feed a feed of whatever content that that social media application that platform provides and this instance it's a bunch of posts that are used as examples because I'm still working on this but are these posts stored in a data structure kind of kind of not really but kind of we have to work our way to it as you can see the posts are actually stored in an array of objects or at least when they're being used see they're stored actually in the database in this instance it's a postgressql database with all of the posts being stored in a table and this table has all of the information each row is a single post and it has the unique ID created it updated at the user ID for who created it the title content URL image you get the idea but then we need to use this so the way we use it is that we call to our database and we fetch those posts from our database and we put them in descending order so the most recent is up top and then once we do that we return the data for whenever this function is being called like right here so we are calling our fetch posts and storing all of that data remember what it's returning into our array of objects just like you can have an array of strings where each value is a string or an integer each one here is an object so each object has all of that post data that you need and then we map through it just to make sure that our types are all consistent and things of that nature and then what we're doing here is returning it by passing it through posts and the post feed as you can see right here post is the parameter that's being passed into Post Feed and then we are using it throughout our code and however we see fit with this being that front end code that you see here so within each post we need to identify the user and that user's username and profile the title the content the upvotes and that's what we do down here as well we get the user posts image we get the username we get when it's created at that's what this data is here the post title as you can see so on and so forth so that's how an array would be used in an instance like this but what about an algorithm so as you can see here we have home that's where we're at right now and you can notice that we have these being upvoted one one one and then there's a zero down here and then there's a one right here if we go to most upvoted you can now see that all of those that are actually upvoted by me the sole user are at the top because it's ordered from the most upvoted down but how do we do that it's actually very very simple so what we do is we do the same thing as before we fetch the post so remember we're using this we're calling to our database and bringing in all of that data storing it in an array of objects but then we are sorting that array of objects based on vote count which is one of the values within the object as you can see right here and this right here is a sorting algorithm now in JavaScript it depends on what engine you're using so if you're using Chrome or node.js that uses the V8 engine so that uses timsort which is a hybrid sorting algorithm derived from merge sword and insertion sword this is also what python used is actually developed for python however if it's in Firefox which uses the spider monkey engine then it uses variations of merge sort and then Safari uses JavaScript core engine whereas the specific algorithm used can vary as far as I know at least so right there is a real world use case of how arrays array of objects in this instance are used in an actual application as well as how sorting algorithms are used and I'm really glad we could do that one because it not only fits the criteria of that original comment where wasn't really asking about real world applications but more so how you can utilize and use data structures and algorithms in our own projects as he said but it also hit that other criteria of how they're using railroad applications like a social media application whereas this one that we're about to discuss not so much but it does fit the how you can use them in your own projects and it translates outward but not like it lays the foundation it allow like it allows you to learn about data structures and algorithms and how they're utilized in ai ai is very broad it doesn't just have to be machine learning by the way and things of that nature but this project will showcase arrays hashmaps array lists link lists hash sets and how they're used as well as DFS and BFS and AAR which are three of the algorithms that I went over in my three types of algorithms video and all of this in my sooon solver Java application that I built about 7 years ago in my intro to artificial intelligence class wait what happened oh yeah yeah yeah yeah yeah GTC 2024 is about to start March 18th to 21st it's the number one AI conference for developers and your boy will be there live and in person well not live but in person I'll be attending a handful of Tours workshops and of course the main keynote presented by the CEO of Nvidia himself Jensen hang who is also the same man who signed this GTX 490 GPU that I'm giving away to one of y'all didn't see that coming did you all you have to do to enter is attend a GTC 2024 session virtually is obviously fine and send me a screenshot of your session to prove it just follow these instructions register for GTC using my link in the description box it's free to attend virtually and if you've already registered that's perfectly fine then as you're attending a GTC session take a screenshot and fill out the Google form also linked below and while not part of this giveaway it may or may not it won't give you a better chance to win the GPU if you sign up to my newsletter devotes also free devotes daily.com that'll be the third link in the description we'll be covering everything mentioned at this event that developer should know and summarized beautifully and concisely for y'all if you're curious about my top choices that I'll be attending those are linked below as well and include AI assisted developer tools for Accelerated Computing AI for agriculture because farmer and implementing Omniverse to produce cinematic content that one seems wildly interesting and if you're going in person and you see me feel free to say what's up all right now back to the video so the sooon silver you've probably played soan one way or another without even realizing it especially if you played Pokémon and you had to move all of those rocks in a certain order to get them where they need to go so you have a path that's sooon that's literally the game sooon I think I'm pronouncing that right is a puzzle game where you push boxes to their designated spots but you have to figure out which boxes to push where and in what order so you don't block yourself off from the rest of the boxes a beautiful game to practice some algorithms on and we really get intricate with some of these data structures and it all starts with the board State this is a snapshot of where the walls boxes goals and the player are located on the game board that is these are bit fields and then we capture this snapshot of the game using a specialized data structure take a look here so we use hashmaps and we have the hashmap for exactly what it says here character to bitfield BU mapping so it's for biral mapping between the characters you see in their bitfield codes because well hashmaps are great at quickly finding and updating these items so as you can see we have a new hashmap chart of field with a character and a bite and these are our bytes as you can tell and these are our characters that will represent said bites and you can see a little bit more of how that works here but then down here we use arrays so the array it's in charge of holding the entire game board's layout which is really just a it's a big grid that keeps everything in its place the walls boxes everything and we chose an array because it's well organized and provides a fixed siiz container that perfectly matches the 2D setup of this Soom puzzle meanwhile we have sets for the goals in the boxes to keep an eye on where the movable boxes in the player are because a box and a player cannot be in the same location at the same time and of course sets they allow us to really easily add move or check these positions and then with every move or push you make in the game you're essentially changing this data structure which leads to Transformations that you see on the screen which you can see how that works in these methods down here so here we're returning whether or not the player can move in a certain direction down here we're returning the new board state after moving in a certain direction down here we're returning true if the next move has the input bit field that otherwise it'll be false and you get the idea now if we want to come over to BFS this is one of our many solvers let's get that out the way and as you know BFS is Brett the first search so it's a layer by layer exploration strategy that examines all possible moves from a given node before moving on to the moves six accessors or next layer so our BFS solver here inherits from abstract solver which as you can see over here sets up a framework for a search based puzzle solver like these this is this is where the real magic happens here here's our Constructor for this class we're first passing in that board state which will be assigned to current state here we're preparing a list well technically it's a set a hash set as you can see here to keep track of all the puzzle States we've already seen and here is our backtrack hash map which stores every move the solver makes and where that move came from this way once it finds the solution it can trace all of those steps back so you have a final solution after the fact otherwise then you do it once you forget how to do it you have to do it again doesn't make sense and down here is where our search algorithm is implemented with the use of a q determining the order which states are explored so first in first out exploring all possible moves from a given State before moving on to the moves that result from those moves so covering the search space layer by layer as BFS should and you can see how this translates back over in our BFS solver this is it it's convenient but it's annoying when I just want to highlight something in GitHub so in our BFS solver class we initialize with the board State set and our queue being implemented as a linked list because we'll be adding and removing many states as we explore the puzzle and because link list in Java comes with methods ready to unq and DQ by default so it just made it easier for me that's that's really why I used it and down in this method we create an array list of valid moves where when we move we log it in the backtrack hash map this keeps track of where each move came from and then we add the move to the que for further exploration that without really going down like a crazy rabbit hole is that's all I got for you I don't know if I answered the question I often times stray uh but I have fun doing it so take the video for what it is feel free to subscribe if you enjoyed the content and you want to see more like this again I'm forest and I'll see you in the next one

Channel: ForrestKnight

Views: 181,107

Keywords: data structures, algorithms, data structure and algorithms, graph algorithm, sorting algorithm, searching algorithm, bfs, dfs, breadth first search, depth first search, dijkstra's algorithm, a*, a* algorithm, linear search, binary search, bubble sort, insertion sort, merge sort

Id: ALPWOiUKIjY

Length: 11min 39sec (699 seconds)

Published: Fri Mar 15 2024