Video 2-2: §2.2 Resizable arrays

0:00 Intro

0:03 in the next section we look at resizable arrays that sounds like a contradiction in itself because arrays tend to have a fixed size but there's a trick to make them feel uh to the outside world as if they could be resized

0:21 it's a very standard trick so i want to show this if you want you can say an array is both a data structure and an abstract data type let me let me say why i think that is uh in both can be justified we can say an array is something that you can create with a fixed size and yeah java can do this like this in python you can create a list of a certain size but it's not a real array it is a resizable array actually beneath the hood every list in python is a resizable array

0:58 but in java we have real arrays where the size is fixed and you cannot change it after you created it and that's what i want to understand when i say array it's fixed size and python lists are lists

1:13 we can get the ith element in the array so that we can access an element by index and we can overwrite the position by index and both java and python use the square brackets to do that and the important thing is fixed size as i said at construction time you allocate a fixed chunk of memory and that is it

1:38 we can also say an array is a data structure because it actually says by by fixing these operations um well by the term array we usually think of a concrete representation in memory namely a contiguous piece of memory where we put the elements one after the other there's a starting pointer and then you can just add offsets to get to the other positions so uh array is the one thing where i'm not sure if we would better call it an abstract data type or a data structure because it has features of both and it's so fundamental that it might be a bit outside of this distinction

2:20 a fun fun metaphor i've heard is arrays are a bit like the sharks of evolution they've been here forever they're still very efficient sometimes but they're also a bit limited

2:33 so let's let's treat them as a data structure because they're built into most programming systems and their implementation is is usually fixed to this contiguous chunk of memory now we started this section calling it resizable arrays so that doesn't work normally but we can have at least something like arrays based on sorry we can have stacks based on arrays without a fixed upper limit on the size

2:49 Resizable arrays

3:14 we change the array once in a while when it becomes too small we create a bigger one and copy everything over and we do this so one one way to do this is to save i currently have n elements in the stack i want that my array that i'm maintaining in which the stack is stored has a capacity of well at least n because i have to store all the elements but also never more than four times the number of elements okay in other words the number of elements currently stored in the stack is between a quarter capacity and the full capacity

3:55 if we can maintain that we can always add more elements because we always have a capacity a bit left maybe um after after re-establishing the invariant the rest of the implementation remains unchanged we keep an array and we keep an index of the topmost element

4:24 now how do we make this magic happen that we always have the capacity like this and the simple answer is before you push a new element on the stack that's the point where you might run out of space if we do if we do run out of space if we have filled the stack to capacity then we double the size of the array okay and then you take you take a new array of twice the size you take all the elements from the old array and copy them over and likewise if we pop an element we might violate this this other end of the invariant we might have that the array is now too empty in which case again we create a new array of size 2n but in this case this actually shrinks the capacity of the array in half or roughly around that because if we violate this bound then our n is roughly a quarter of the current capacity so if we go to twice that current size it's half the current capacity okay so two simple rules and that's what people mean if they say resizable raise maybe with slight twists if you actually double or change that two to some other some other factor other than that that's that's what's

5:47 behind resizable arrays questions uh well if you pop an element it might be that the stack is too empty for us to allow it we don't want to have more than three quarters of the array empty and if that's this if that's the case we have the capacity what's written on the slide is a more sophisticated way of saying that but it comes down to the same thing if your array is too empty you make an array that's half the size and then it's no longer too empty okay

6:55 the comment is that uh this seems to be expensive right uh so it can be expensive in different ways uh it can be wasting space so you might be inclined to use a smaller constant than two if you want to not have as much spare capacity it also is expensive in time because if you have to resize you have to copy all those elements over both are legitimate concerns but still this is very widely used so are people all just misguided and use something that's not really efficient

7:28 Check

7:32 uh let's have a quick check um if you understand this invariant did i set this up as multiple choice you can take several answers okay five four three two one and locked this is an interesting one because all the answers got roughly well a quarter of the votes right uh only one is really correct but this was a mean one

9:22 uh after we've analyzed it so from what i've said so far um you can eliminate some of these um [Music] the first one can't be really true uh because n is changing all the time if i add another element that would mean if i say exactly an array of size 2n that would mean whenever i add a new element or remove an element i have to change the size of the array but that was not what we were doing we said we only allocate a new array in these extreme cases when the capacity was completely used up or when it reached a quarter okay for the other things bear with me for a second there's a second reason why i'm discussing this resizable array primitive data structure because i want to do a little bit of amortized analysis with you and this might be something not everyone has seen formally so maybe time to wake up for the computer science graduates so we've already discussed briefly that sometimes these push and pop operations are insanely inexpensive because you have to copy a very large array to a new array so in in theta terms it's linear time effort to copy all these elements and we have to do this at the push and pop there's no discussion

10:51 the the trick here why it's still a fairly good data structure in many applications is if you have such an expensive operation say you suppose we only add to the stack after you've just done such an expensive operation you have twice the capacity that you had before so you have to wait a long time before you have to double again and similarly if you if you popped elements off and you reached this low threshold so that you made the the array half the size you're definitely still um another so you're then at roughly half usage of the memory so you need to pop quite a few more elements before you have to do the copying step again so we can offset we can amortize the expensive operations against the many cheap ones that they must entail and so this is this is waving our hands and the intuition behind this is it looks like maybe on average the operations are cheap but let's try to be um a bit more uh precise and quantitative about this

12:00 Potential

12:03 and that's what people call amortized analysis uh this this might look a tiny tad scary but we'll go through this in a slower pace what we'll do here formally is we define a potential that is a number assigned to a current state of the world and our world is the array this potential is traditionally called phi and so i kept that and here what we want is pi should somehow express how far are we away from an expensive operation now the catch here is expensive can mean if i have many pops or many pushes i can go up and down and so we somehow have to reflect the distance to both of the expensive operations and one way to do is is to define a potential like this we have the current size of the array n and the current capacity c and we take the smaller of these two distances

13:11 what this means is maybe use more space this is our array s which has capacity c and it's filled up to some point uh n that's occupied by our well that's currently filled with elements in our stack

13:39 and now there's there's two points where things happen at a quarter c and at c and so our potential measures the distance to these two interesting points and takes the smaller of the two

13:59 that's what the potential intuitively does uh and you can work out using the invariant that we maintain that it is always it's it's never negative and it's never more than 0.6 n that's just if you insert either the boundary cases and look where this is maximized okay

14:36 okay so the question is about what happens if you create a list in python of a certain size uh so in principle all lists in in c python in the standard reference implementation of python are resizable arrays um i'm not sure if they use a factor two for doubling or if they have a different trade-off that are you you can have a look at the code it's it's open source uh and they might have um other special cases if you create a list from another list where you know the size uh maybe the default is to create then an array of exactly that size as opposed to the next power of 2 or something like this these are details that i don't know from the top of my head how they are done but something along these lines happens if you keep appending a new element to a list in python you will have this doubling or this resizing once in a while and you can measure this and somehow prove indirectly that python uses this even if you're not looking at the code

15:40 Amortized cost

15:43 okay so that we have this potential it's a definition you can take this just as as that but you can also think about it that it measures how far are we away from the dangerous cases where we have to pay

15:59 and now we define what's called the amortized cost of an operation which is is not the real cost but something like every operation pays a little bit a little contribution towards the next expensive operation that's the idea so every operation has an actual cost and here we count the number of array excesses as our dominant operation

16:27 and it's corrected by this this term that only makes sense after you've completed the analysis really why there's this minus four but it there is a correction term that contributes the potential so if if an operation decreases the potential which means it brings you closer to the edge of paying then the amortized cost goes up okay and if an operation brings you further away from the dangerous cases then the potential increases and so the amortized cost decreases because you're you're paying for that uh up front

17:11 what we have to do for um for this uh maybe before we go into these steps uh let's have a look at what we get at the very end if we have a sequence of m operations in total then we can bound the total cost that we actually pay for that sequence of operations by the total amortized cost that we will analyze in the second plus the final potential final number of credits and we'll see that this works out to theta of m plus n which means it's linear in the number of operations and the size of the final array and

17:54 okay yeah you need both uh the array could be very small at the end or could be roughly a size m before we continue uh with this i want to show you why this inequality is true

17:58 Why this inequality is true

18:11 and for that i'll denote by a i the amortized cost of the ith operation so a is for amortized and it has an actual cost that's ci c for cost and we subtract this go away uh four times the change in potential okay so we need um a notation for this phi at a certain point in time so all right

18:44 i'll write phi i to say this is the potential after the ith iteration and phi i minus 1 is the potential before that operation so that's just a way to assign names to these different parts so that we can work with them in the formula

19:02 uh what we'll show here is that this is at most five in all those cases we'll go through that in a second but what's behind amortized analysis in all cases is the following observation if i sum up all the amortized costs

19:23 i on the one hand know that this is at most 5m because each costs at most 5. but also i can rewrite this some by inserting the definition and then as i can split the sum so i get the sum of all the actual costs that's what we're really interested in we only care about actual cost not amortized costs the amortized cost is only a means for the analysis

19:57 and then we have this correction term so we have a sum over all these potential differences and if you look at this sum this is a telescoping sum each term we have a by i positive but then if you go to the next i where i is i plus 1 you subtract phi i again because for i i plus 1 i minus 1 is i again and so these all cancel each other the only things that's uh that's the only thing that's left is the the very first and last one

20:41 so we end up with the actual cost some of the ci and what's left is the last and we subtract the the first so we get an inequality like this

21:01 need a bit more space and so we can rearrange this this is what we're really interested in and now we have an inequality less or equal 5m and we bring this to the other side so plus 4 by m minus four phi zero and because our potential was never negative we know that we can just drop this and it only gets bigger

21:46 and so uh this is what you see spelled out here five m and four times the final potential now we don't really know what the final potential is actually but we know the potential is never more than 0.6 n so we use this upper bound there that's how we get there now the step that i skipped before was to show that the amortized cost of each operation is always at most five so that's what's uh was explained here and we have to distinguish the different cases now uh if we have a cheap push or pop that means it's one where we don't have to copy we don't have to create a resize the array so we can move with n one up or down and c remains unchanged so the actual cost is one because i have one array access

22:42 the potential can go up or down but at most i have to consume one credit and so the amortized cost is five because i have one actual cost and i might pay minus one in the change of potential minus times minus four becomes a plus four okay

23:01 at most five if i have a cheap operation it could be cheaper it could actually have amortized cost minus three but we only need an upper bound what happens if we push and have to resize the actual cost is 2n plus 1 because i have to create an array of the new size and then i have to read n elements write n elements for the copy and one more element because i'm pushing a new one that's two n plus one

23:34 if you do the math it happens to come out that you create one half n credits and for that um you have to look at what the situation is here so your array is currently entirely full because it's an expensive push that means n was the capacity before and so you resize the array so that it now has twice that capacity and the new n is is here just this one more element is used now so um

24:14 the distance to this boundary that matters is the one here to the one quarter and so you see that this is roughly half one half n and you can work out if you count exactly you get to the one half n plus one credits that you that you gain and if you multiply that by four and add the two things up then you see that the 2n that you pay for the copying and the four times the credits you gain they just cancel each other and magically it sums to 5 again okay

24:56 and similarly for pop the situation is quite similar to the other one you get the same picture at the end but you start with a bigger array where only a quarter is filled but then you resize the array to be only half that big and so again uh it's the the distance to this point that determines the potential and that's again roughly one half n

25:27 uh and previously um you had the potential at zero so now you're again at one half n new credits that you created by shrinking the array and again multiply this by four add the two things up multiply by minus four comes out to five okay i know these proofs sometimes look a bit magic the way it works is you think of a potential that intuitively makes sense and then usually you have to play with the definition of amortized cost until it works out if you want to see this in action watch the video from last year where i had to do this on the fly because i messed up the first round but now it's it works as it is on the slide which has the benefit of being correct but is not as instructive to watch

26:16 Questions

26:24 we already had the questions um i'm not asking it again now uh because we've discussed it in length um this is the right answer because that's the outcome of the amortized analysis the total cost for m operations is linear in m and it's linear in the size of the array either of which could be bigger why are the other answer is not correct we talked about the first one but the second one is not always correct adding or deleting an element at the end onl only takes amortized cost constant time if i do this many times on average every operation is constant time but each individual one if you say you look at this uh from a worst case perspective might be linear time because it might be one of those expensive ones uh the last one is almost the correct statement it talks about the right type of time constant amortized time but deleting or inserting any element means also in the middle of the array and that doesn't work because you would have to move elements over so that was kind of a trick answer

27:37 all right let's do the rest a little more quickly q is another abstract data type which is quite similar to a stack you have only two operations you can in queue and one end and dq on the other so it's like a queue where you wait you add yourself at the end because you don't uh cheat and you get pop from the front or dequeued from the front and so it's first in first out you can do essentially the same implementations as for stacks based on a linked list or based on an array also for queues

28:15 another slightly less well not as often used after data type is a back which tries to abstract what the two have in common i just want to throw in this because it's uh is it exists in the libraries of programming languages sometimes a bag is something you can put something in and you can get any item out but you're not it's up to the implementation to decide which item is is removed you just get any it's sometimes convenient to express as a programmer that what you're using here is is a back and you don't care in which order the items come out that could be useful because then you tell the programming system the compiler that it can do optimizations that change the order so that's why it's sometimes helpful to have this it's a way of expressing your intent you only need it back now you might use a stack in underneath it just because the stack is a good implementation of a bag but if you say you're actually using a back that means other options are possible that's why it helps to separate abstract data type and implementation