Video 2-2: §2.2 Resizable arrays

0:00 <Untitled Chapter 1>

0:04 in the next soft section uh I'll show you a classic data structure that achieves exactly what we were wishing for in the in the case of Stack have an array but be able to change its size sounds contradictory

0:19 um but uh we can work our way around this contradiction I thought it's useful to say to have on the slide at one point what an array is so I try to formulate the operations of an array here [Music] um don't think of a race as an abstract data type really an array is is a concrete data structure okay I just used the language of an abstract data type here because it's it's convenient to say what an array is in case you wouldn't know uh I mean scc3 over you can create an array of a fixed size and you can do this in Python like this even though uh there's no real arrays it's it's just the closest approximation you can do it in Java like this in other languages look similar you can get the position the element out of position using square brackets and you can write to that position in the same syntax in a way you probably have seen this so I don't want to spend much more time on this um the thing is erase are really part of the the operating system of the programming language so you don't have to create those yourself normally

1:36 Doubling trick

1:41 so how can we get an array that changes size well we cannot but we can get a new array so uh whenever we need more space we just make a bigger array and use that instead that's uh the whole Magic behind this resizable race

1:58 um so I I formulated it here again as an implementation for Stacks the idea is essentially more flexible but we'll come to that at the end we had these two invariants from the array-based stack we maintained an array s remember I drew this so that it resembles this stack of books and the trouble was it has fixed capacity C so it has a height C and we kept the pointer top pointing to whatever is the the current uh topmost element that is in use now we want uh just I just postulated like that for now we want that this capacity C um is um bounded in terms of n or more conveniently expressed the other way around the number of elements n so n is the number of elements on the stack

3:05 is that not somewhere on the slide you're better Happy Well now it is so the number of elements on the stack should be at most C well we can't store more but also not not fewer than a quarter times C

3:23 uh if if we can maintain this invariant magically somehow we will always have space for more elements because the capacity magically uh matches up but of course we'll have to make that happen ourselves

3:44 and how do we do that how do we get to the point that this this is always true uh by two little changes whenever we do a push we first check if the array is completely full if so we double the size of the array and what that means is we have to allocate a new array of double the size and copy all the limits over that sounds costly and it is similarly if we pop and that was the last element that brought us below this lower bound if the new size of the array is less than a quarter of the capacity then we shrink the array so it looks like this is the same but remember that here n is really small so again we allocate an array that's twice as big as we currently need it and we again have to copy the elements over uh that's that's always the costly step we need these two things together are usually known as as resizable arrays it's a bit of a misnomer because this is just what it looks to looks like from the outside uh maybe the constants the these factors here are not always two um but that's the basic trick that that's used everywhere and that's how python lists are implemented at least in C

4:59 python in the reference implementation uh they use something like this this uh doubling trick okay uh let's let's have a look at um well you know this stuff already

5:26 okay it's reloading here I can do it here should we go to 50 Now 60 again right 60 wasn't I'd love to be able to show there's I can do it here

7:26 I mean try to resist the urge to change your answer uh this is a fairly tricky question I probably meant to not show you the result yet you'll figure out why the why the answer I already revealed is correct after the fact

7:57 Amortized Analysis

8:03 so the bit we haven't touched on yet is uh what does this do to the cost of our operations and the problem here is uh because this this copying I mean creating a new array may or may not be costly that's a bit of a question uh of what the memory uh management system does exactly if it has to fill the array with initial values or not for example but definitely copying the the elements on the stack to the new array is costly so occasionally these push and pop operations can be really expensive however we would hope that this doesn't happen all the time right because if you keep pushing we made the array much bigger so every costly operation must be followed by many cheap ones and so uh the idea of of amortized analysis is to try to offset these two things yes some operations can be expensive but you never you usually don't just use a single operation of a data structure in isolation you use many operations and then maybe it's it's helpful to spend more effort now and profit from it later

9:19 so in this concrete case there's uh again this is a topic many of you will have seen in some undergrad class uh there's different ways to sell the same idea um what I will what I will show you here is is kind of a a bank account uh accounting metaphor if you want whenever we do something that's expensive now but helpful in the future we get credits and we can spend credits in the future to uh amortize the cost yeah

9:49 pardon oh Phi is just the name I mean it's secret letter yeah it's uh I don't know how this came about I guess uh it's not even it's not even the Greek piece so it's not like potential I don't know where this comes from I think it's it's from physics tradition that potentials are named by don't ask me um it's a convention it's just a name right it's it's just a name so the idea is we Define uh a quantity that we can offset real costs against if we pay a lot now we want the potential to cover that for us and if we pay a little now we want to build up potential there's two ways to look at it one is the credits world that's borrowing right it's the North American World yeah you don't save up until you can afford the car you go and buy it and buy it on credits and then pay it back uh I don't know the the diligent German way is you first build up the savings and then you go and buy the car uh but data structures the two are not so different because you don't know what comes first which operation comes first this is the under the control of the outside program

11:24 let's try to walk through this uh maybe the example makes this clearer than my fuzzy explanation we Define this quantity Phi a mysterious thing it's defined as the minimum of these two things which if you think about it um let me draw a picture here that's our current array which has length C

11:50 so C is the size of this I don't know I probably need the space um that's C and we have a current number of elements in this array say up to here this is filled and to the right is empty now what this potential looks at is this distance right uh C minus n is how much free space do I have and the other one is n minus a quarter of C so you take the quarter point that's this one and you take this difference uh maybe colors right so that's the blue part

12:48 that's the blue bit let's say this is the red bit so the intuition behind the potential is how close am I from the danger region well how how far I am I from the danger region and take the smaller so take the the one where I'm closer to another costly thing and in this case red looks a little smaller so it's it's more likely that I have to pay to make the array bigger than make it smaller so the potential measures this uh safety buffer the size of the safety buffer

13:28 if you use our invariant um we I formulated this in terms of of n as a bound of C but we can flip it around if you rearrange this then you get a Bound for C it's more convenient for this so if you insert what you know for C you you find out that this potential is always between 0 and 0.6 times n that's just uh doing the calculation now uh what we'll do is for each operation we'll look at what is the amortized cost that's the real cost what I have to pay to do the operation plus the change in potential and to be to be precise I multiply the change in potential by four just because that works out to be the right constant there's no magic explanation you try your constant until it works so we Define the amortized cost of an operation like this and then we just go through the operations so for push and pop we have two different uh the different cases if they're cheap then the actual cost is one array access so that's what I said here let's count the number of axises to the array that counts both Reading Writing and copying so we've kind of lump that together the actual cost is one axis

14:54 and uh we increase the potential we lose we lose at most one credit it's minus the change in potential uh why did I do it like this uh so it it's natural to think in credits here if we look at the negative potential then it's it's credits that we build up uh so um if if we do a push or a pop that can bring move us here one step to the left or to the right so that can at most make this potential go up or down by one and I multiply that by four so whichever way is the the bad way I get at most the cost of four from the change in potential plus the one actual cost that sums up to five okay so far so good uh it's not necessarily very intuitive what happens it's just following the argument for now and so what a cheap push and pop does is it moves this this black line one one step left or right and all that can do with the potential is again cause a change of one then we have two expensive cases we can have a push where we have to create a new array and it turns out this uh costs us two n plus one um so I guess the the one array access

16:18 is to write the new element in at the end and the 2N is for copying the elements over I counted read and write separately so you have n elements at the moment you have to copy them to a new array so you read the N elements you write the N elements that's 2N and plus one is you have to store the new one at the end of the whole thing

16:44 what does that do to the credits uh well for that um you have to look at where we are um when we are at the costly push Pi is zero at this point because we know that n is the same as the capacity otherwise we wouldn't have the uh expensive push so Phi was Zero before so we only have to look at what Phi is afterwards and so here we do our twice as big array and it's filled up to half plus one element right that's that's where we are now

17:27 and you have to compute how far this is away from the two endpoints the danger Marks full and quarter of full and clearly this is the shorter in that case the blue the blue case will dominate will give you the minimum and that works out to one half n plus one credits okay this is this is basically n so it's half of it and the plus minus one you have to write down the actual numbers and then see that that's the case insert a concrete n if you sum up these two things so the credits here again remember they get multiplied by four minus four credits then four if you sum these up uh the minus four times one half exactly cancels the two n that's what you always want with these potential changes you want them to cancel out the actual cost the the big part of the actual cost and what remains is the five because we have four times this and the one so that's uh I think it's actually less per them because it's minus four but it's at most five all right still with me uh last one is the expensive pop in that case we had a before we must have had the situation that we're only quarter full

18:53 and now we copy it into a new array that's half as long and again the blue part will dominate because we're closer to this quarter Mark again than to the the right end and so if you do the if you do the exact Counting there's a change here because you do a pop instead of a push at the end so you actually losing one more element here uh but the same argument the the real cost is 2N you have n elements in there you have to copy them both plus one more that you cancel out and the credits um where zero potential was Zero before and it's roughly half n afterwards you multiply that by minus four the two n cancels and what remains is again five so the magic at this point was in all cases the amortized cost was bounded by five a constant

19:54 and so uh why is this useful if we have a sequence of M operations and those could be any operations we don't know then uh Let Me Maybe write this down um

20:19 let's say AI is the amortized cost of the ith operation then that's the actual cost CI minus four times the change of potential so we can say there's a potential at after the ice operation and then there's a potential before the ith operation or after the I minus first and we know that this is at most five that's where we lengthally argued here so these are the AIS amortized costs and now if you uh if you sum up the amortized costs from all operations one up to m we know that this is at most five times M because they're individually all bounded by five

21:02 and we can rewrite the same sum in a different way by inserting the definition if we split the sum up then we have the cost of the sum of all the Ci's and minus 4 and then a sum that some of you may immediately see is it's a special type of sum

21:32 because this sum is called a telescoping sum you're always taking a positive term from the next element and you subtract the previous but you sum this up over the whole thing so if you do this they all cancel each other out both turn all terms occur with both signs in two different for two different indices I so all that's really left of this sum

21:56 um is the first and last terms so the very last one occurs only positively and the first one occurs negatively so you can rearrange this equation the sum over the real cost that's what we care about the total actual costs

22:22 so I'm just rearranging this bringing that to the other side by m is on the other side already and I add the report times I am minus 4 times 5 0. and for an upper bound I can drop the the second one because it's always uh non-negative okay and that's what's was written in this last line the total cost are the total amortized Cost Plus the final credits what I have at the end left and that's what amortized cost is five famous we've argued and the final credits I don't know but we know an upper Bound for the credits that's what we had up here so it's at most that and these two things together is some constant times M plus some constant times times n that's Theta of M plus n so what does that mean uh if we do a sequence of operation M operations the total cost will be at most some constant times M the number of operations plus the the size of the array at the end but really that's uh not more than the number of operations if you start with an empty stack if you start with a stack that's already big and you do some operations clearly it has to be taken into account that this was already

23:47 big that's why this occurs C was the was the correct answer here that's what we've shown with amortized costs and as a last thing let me briefly show argue why the others are not quite true so the uh the elements are not always stored in an array of exactly size 2N and changes all the time we don't exactly have that size all the time this can't be true because we sometimes have to copy elements over and the last um is essentially correct but any element is the catch it's a stack we can still just pop okay that was maybe a mean one

23:52 Clicker Question

24:41 good uh apart from Stacks there's cues where you can insert at one end and take out of the other end otherwise it's the same as the stack and the implementations are the same and there's an abstraction of both of them if you only have something that you can put elements in and you can get some element out we call this a bag these are just two terms that I want you to take with with you the implementations can be very similar to Stacks it's just different terminology so we're back you can throw things in and you get some element out with no guarantee whatsoever which element and in a queue you always get the element that was inserted the longest time ago right that's why for Q people say it's it's first in first out and stack is lasted in first out