An Overview of Arrays and Memory (Data Structures & Algorithms #2)

hey guys in this video I'm gonna give you an introduction to erase and a quick overview of how memory works and this video it's gonna be split into three parts first of all I'm gonna cover the basics of arrays and this part is gonna be pretty basic so if we already familiar with erase don't worry about watching this part and in the second part I'm gonna cover what memory is as opposed to storage and finally I'm gonna cover how integers and integer arrays are stored or memory arrays and memory or two of the fundamental topics in data structures and algorithms so let's get started okay so first of all what is an array an array is basically a collection of items of a single type so an example would be this one which is an array of integers or this one which is an array of strings and it's not usual for an array to have multiple types so it's not usual for us to have something like this where this array has both strings and numbers inside and let's take a look at some code snippets in C here to see how you can use arrays in practice I'm only gonna take a look at C here but it's gonna be pretty similar to other languages too like Java this line int sample array square brackets 5 equals 2 4 6 and so on says create a new array with five integers and then populate it with the elements 2 4 6 8 and 100 and you can visualize this array as a box with 5 partitions because this array is able to contain 5 integers if you want to change some of the elements in this array of course you can use code like this the first line says change the first item of this array to 20 and then the second line says change the second element of this array to minus 5 so after executing these two lines of code sample array will look like this you can see that the first two elements have been changed but not the other three elements and of course here the index of the array starts at 0 instead of 1 and it's not necessarily the case with all the languages but this is what we're going to use throughout this course - now what if you already have five numbers in this array and you wanted to add two more numbers let's say two and three after the fifth item you might say well why don't you just add two more partitions at the end of this array and then put those numbers in there but actually you can't do that and to understand why that's the case why you can't add more partitions at the end of this array I'll need to give you a quick overview of how memory works on a computer okay so what is memory exactly for me to explain what it is the first thing you'll need to understand is that there are mainly two mechanisms for storing data on your computer the first one is memory or it's sometimes called RAM and the second one is storage which has different types for example a flash drive hard disk or a solid-state drive now the biggest difference between storage and memory is that the data on storage is permanent while the data on memory is not what I mean by that is you know if you think about your laptop when you turn off your laptop the data on storage will still be there but the data on memory will disappear as soon as you switch off your laptop so if you think about the bunch of photos you have on your laptop you know when you turn off your laptop and turn it back on again they should still be there right and that's because they're on storage and not necessarily our memory so like I said the data on memory on the other hand just disappears when you switch off your computer have you ever had an experience where you started working on an essay or you started drawing something on your computer and then suddenly you just lose all your progress because your computer crashes and then it shuts down and that's probably because those documents were on memory but not necessarily on storage so when you you know work on those documents and when you hit the Save button that finally becomes a file on your computer on storage this time so that the next time you know your computer crashes it's still gonna be there so at this point you might say wait why do you need these two separate mechanisms then why can't you just store everything on storage well the thing is reading data from and writing data into storage is pretty slow it's sort of like walking all the way to the file cabinet you have in the basement to retrieve you know the files there whether there are photos or documents it is necessary sometimes because that's where you have those documents but if you do it too often it's just gonna take too much time and that's actually where memory comes in memory is sort of like a temporary desk you have in your room so once you retrieve those documents you know from your storage whether they're text documents or photos you'll be able to put them on your desk or on your memory and once they're there it's gonna be so much faster to work with them and the reason it's so much faster is because it's so much quicker to write data into and read data from memory than it is with storage and then once you finish working with those pieces of data on your memory once you finish editing them and modifying them then you can bring them back to your storage so that you can save them they're more permanently as computer files again so that's the gist of how memory and storage work together with files and the way they work together for applications is actually pretty similar so when you have applications on your computer they're stored on storage originally and you can easily tell that's true because when you you know turn off your laptop and turn it back on again those applications are still gonna be there but when you launch one of them let's say Google Chrome it's gonna be loaded onto memory so that it's faster to use and you know faster to access there and so if you start running too many applications at the same time you know they're all gonna be loaded onto memory and you might actually start running out of memory space and that's why you know that's one of the reasons why to many applications at the same time on your computer might actually slow down your computer and let's now see how this whole thing actually looks on my computer since I'm using a Mac if you want to get an idea about how much memory I have you just need to click this Apple icon and then about this Mac and you can see that I have eight gigabytes of memory here now what about storage for storage I have 251 gigabytes and actually one feature of storage is that it's usually much bigger than memory and actually on the Mac there's a way to get a rough idea about how memory is being consumed you can just open Activity Monitor I think there's something similar for Windows 2 and here you can see that for example Dropbox is using about two hundred forty megabytes of memory and Google Chrome's using about 100 megabytes of memory and what happens if I go to Chrome and quit this application it should stop consuming so much memory right let's see if that works I'm gonna quit Google Chrome and it's no longer here now how is all of this related to programming and in particular using a race to understand that let's take a look at this piece of code in C this line int a equals 1 when you compile and execute this line of course a variable called a is created and the integer 1 is assigned to that number and this integer 1 is stored on memory and not on storage and that means that when you turn off your computer after executing this code this integer 1 will just disappear because everything on memory of course disappears when you turn off your computer but how is this integer store on memory exactly for me to explain that you'll need to understand two things the first one is that each integer when it's stored on a computer it's often expressed as 32 ones and there's so for example the number one can be expressed as a bunch of zeros and then one at the end actually that's 31 zeros and then one one at the end and the number two can be expressed as a bunch of zeros and then one and then there again that's actually 30 zeros 1 1 and then 1 0 and just like that pretty much any integer that you might encounter in real life whether they're 100 or 200 or minus 223 each of them can be expressed as thirty-two ones and zeros now each of these zeros and ones is called a bit so a bit is either 1 or 0 so we say each integer can be expressed with 32 bits and you don't have to worry about how it's converted exactly if you don't know about it yet but just know that pretty much any integer within a reasonable range can be expressed with 32 bits or 32 ones and zeros okay the second thing you'll need to understand is a simple model of memory memory can be thought of as a long tape of bytes now what is a bite a byte is basically a small unit of data and it consists of eight bits so each byte might look like this Woori has eight bits or this one now you can visualize the simple model of memory along table bytes like this so this is the long tape and each of these compartment represents each byte so you can sort of imagine a bunch of bits eight bits to be exact being crammed into each of these compartments and then you can store bytes which are of course small units of data in these compartments to represent anything you want to represent on your computer now your computer needs a way to find any particular byte very easily and you want to be able to do that because you want to be able to do things like store two bytes in these two compartments and then store four bytes right after that and maybe retrieve two bytes from the first two compartments and your computer achieves it by assigning an address to each byte and each of those address is represented by a sink integer so in this hypothetical example we have the address 124 despite and 121 for this byte and so on at this point you might say wait why do we have these particular numbers 120 121 and so on representing the addresses for these bytes well the answer is you know I came out with this arbitrary number 120 to represent the starting address for these bytes but in reality you don't have to worry about it and you know how to worry about it because the operating system determines what this starting address will be for your particular application so basically the operating system whether it's Mac or Windows this size well your application should live over here in memory and then someone else's application let's say Google Chrome should live over here and so on but the important thing to understand here is that even though the starting index 1 to 20 is arbitrary here the way you have consecutive addresses 1 to 20 121 122 and song that's exactly like a real system on your computer anyway like I said earlier each integer can be represented with 32 bits sometimes depending on the environment it's stored with 64 bits instead but let's just say 32 bits for now and the question I have here for you is how many bytes do you need to store each integer well that's pretty simple because you have 8 bits in each byte so if you have 4 bytes you can store 4 times 8 bits which is 32 bits which is just enough to store each integer so how can we store an integer on memory you might say wait why don't you just take 4 bytes the four consecutive bytes right here and then use that to represent an integer and that's exactly what a real computer does so in this particular case when you have int a close one one is first of all converted into 32 bits zeros on ones and those bits will be split into these 4 bytes and then they're gonna be stored right here on those 4 bytes if you have one more integer for example int B equals three right after this line that variable will be stored on those four bytes right after the first four bytes so that's how integers are stored on memory but actually the idea is gonna be the same for things like this mouse or characters you might need a different number of bytes to store each different type of data 2.3 or a or whatever but the idea of using consecutive bytes to store each piece of data is exactly the same anyway what if you wanted to store an array of integers instead of single integers to see how that can be done let's take a look at some more code in C here and let's say just like before we have int a equals 1 then that integer a or 1 will be stored let's say in these 4 bytes from 122 123 and let's say right after this line we have this line in sample racecar back at 3 e goes 5 3 and 20 this array will actually take 12 bytes right after the first 4 bytes so that's from 124 to 135 right here and we need 12 bytes because we need to be able to store three integers so that's of course 3 times 4 equals 12 bytes and the first number 5 will be stored in the first 4 bytes so that's from 124 to 127 right here and the second number 3 will be stored in the 4 bytes right after that naturally so that's from 128 to 131 and then 20 will of course will be stored in the last 4 bytes right here now the question we asked ourselves earlier was why can't we just add two more numbers let's say 1 and 2 to the end of this sample array you know if you look at this model of memory it looks like we'll be able to just allocate 8 more bytes over here and then use those 8 bytes to store these two integers but actually you can't do that to explain why you can't just do that why you can't just allocate more memory allocate more bytes right after this array I would actually need to explain a little bit more about how memory works exactly but let me give you a more simplified argument here instead the simplified argument here is that after this line after allocating 12 bytes for this array we don't know what's gonna be right after that in this memory space so for example you might have this line int C equals 4 right after this line in that case this number 4 would be stored in these 4 bytes from 136 to 139 and when you store an array you need a bunch of consecutive bytes and that's basically why you won't be able to just add more bytes to this array and actually if you wanted to still add 2 more numbers to this array what you would need to do is you will need to create an entirely new array you know over here in memory and you would need to make that array longer than the original array you know let's say length 5 instead of length 3 and copy over these numbers one by one to the new array and you would probably create this array dynamically and this word dynamically is important but if you don't know what it means exactly don't worry about it for now and then if you wanted to add even more numbers let's say three more numbers to the new array that's longer than the original rate then you would actually need to create a new array again which is even longer than the second array and then copy over all the elements to the new array again so you might think this whole strategy is a little bit awkward because you need to keep creating new arrays and maybe keep deleting the old arrays but that's actually what's used in practice often so if you wanted to create sort of a resize of all array you know a kind of array a kind of new array you might say that can accommodate as many elements as you want to put in there this is one strategy for doing that so for this you know resizable ray you can initialize it as a small array let's say ten elements and then when you want to put in the eleventh element you can make a new array that can accommodate you know twenty items instead and then copy over old items to that new one and then keep going like that you know 28 elements forty elements and then length eighty and so on and this is actually the essence of how many sort of resizable arrays work in different programming languages so for example in Python you might see you know the Python lists and in Java you might have used the array list they might not look like resizable arrays when you look at them or when you use them but actually if you look at the source code if you you know sort of look inside a hood that's how they are implemented okay so this was actually a somewhat simplified explanation of these topics arrays and memory and you'll be able to actually start using them to start building more complex data structures that you got to learn throughout this course like hash tables and trees and by the way when I was doing some research for this video I actually used this video sponsors website a lot and it's called brilliant org so for my research I was using this computer memory course and the section I used the most is called linear memory model which is in the introduction to memory chapter this linear memory model section basically gives you a more detailed picture of what I explained in this video about memory and it comes with a bunch of practice problems too like I said in my last video applying what you've learned is through solving problems is a good way to solidify your understanding of the topic and personally I found that going through this section helped me refresh and solidify my understanding of how memory works and this linear memory model section actually assumes that you're already familiar with binary and hexadecimal numbers so if you want a quick refresher on those I'd get started with the previous section instead and that one is called binary this mode and hexadecimal if you want to check it out for yourself you can go to brilliant org /ch dojo okay as always i'm YK from CS dojo thanks for watching and you know hopefully you can keep what you've learned in this video in your memory as well as your storage I guess anyway I'll see you guys in the next video

Channel: CS Dojo

Views: 478,428

Rating: 4.9619918 out of 5

Keywords: memory, ram, array, data structures and algorithms, data structures, algorithms, brilliant sponsor

Id: pmN9ExDf3yQ

Length: 20min 20sec (1220 seconds)

Published: Sat Mar 17 2018