Video 2-2: §2.2 Resizable arrays

0:03 in the next subsection we'll see how we can use arrays to build something that feels like the lists in Python that they can grow as large as they're needed and uh while many of you will have seen this I think uh the analysis maybe you haven't done formally and uh it's just such a vital thing that everyone should know what happens behind the behind the under the hood for python lists and other other such resizable arrays that's the the name of the data

0:34 structure before we get to that I want to point out that arrays themselves you could somehow see as an abstract data type if you want because it supports certain operations you can create one with a certain specified size that you need to know up front and then you have two operations to read and write the array and almost all programming language have built-in support for this in special syntax because you use it all the time now now in another way it is not really an abstract data type because when people talk about arrays they always have a very specific implementation in mind so you could sometimes uh try to reimplement an array in a different style um but because they're so basic uh it's it's often not really possible I've heard this nice saying that arrays are like the sharks of data structures they've been around forever they're somehow crude and a bit primitive uh but they're still efficient in what they do and so they probably survive uh till the end of

1:44 time but we need we need lists or we need collections that can grow so how can we get the efficiency of an array without the extra pointers um and the random axis with the same time being able to to make them as big as they need to go without knowing it up front

2:05 we can do that with a a standard trick so and I'll I'll explain it in the way you would Implement a stack but the uh data structure is actually more General as before for a stack we had we had um an array that connect contains all the elements we called that s that was this upside down or flip to the side array

2:31 and we maintain this uh position in the array top it's just an index but I'll draw an arrow because it's nicer to see which tells me this part is currently in use and the rest is empty that's what we had before now we'll additionally have another thing that we maintain which is that this length of s the capacity is somehow related to the number of elements we have in the array we want that the array is always well is never over full we can't really do that anyways but also it shouldn't be too empty okay if we can guarantee these two things uh then we can always use the array so we can always push more elements if that's guaranteed afterwards the question is just how how do we do that uh let me point out um we've seen this term invariant before when we talked about proving the correctness of programs and loop invariance it's a more General notion so in the loop invariant it was uh a certain condition that was true before the loop and at the beginning of the loop and at the end of the loop body and then iteratively or uh by induction throughout the loop and after the loop so it was almost true all the time with

3:57 maybe a short transition period while you were EX executing the loop body and the same notion is very useful in data structures as well an invariant is something that is supposed to be true at all times maybe with the except exception of the time during an operation while an operation is executed you're allowed to violate it but then once the operation is finished you have to guarantee it again and that's a powerful feature to prove that your data structure works if you don't have an invariant that in the end implies that the operations work well you haven't understood how the data structure works or it's not actually correct and so um we often list invariance like this as a as a way to for you to understand what happens and also as a way to check uh if you followed everything correctly in the operations so here we'll have these three invariants once you have this and I promise you they are able to maintain it should be easy uh at least in this case it is so the first two are easy to maintain um from the code you've seen before uh but the for the third one we have to do a little work one way to do it is like this before we do a push we check if the

5:13 array is full and if it's full we double its size and after a pop we may have emptied the array too much so if then now the new size is too small or the array is too big then we'll also um allocate a new array with size 2 N so this looks like it's doubling but it's actually shrinking because n is the number of actual elements this simple trick has different names doubling arrays or resizable arrays Dynamic arrays sometimes uh they're all a bit misleading the arrays don't really resize we just allocate a new one but it feels um like we're we're resizing the array the important bit to note is it doesn't come for free we have to copy all the elements if we allocate a new array it's initially empty so we have to copy all the elements that we had previously to the new array and that takes time so uh is this really a good data structure I for those who've seen this before let me ask the the question here

6:57 if you haven't seen this trick there's no way for you to know this so in that that case you can uh you can just guess and see what you feel intuitively should be

7:58 okay we'll come back to that question so I I want won't show you the answers yet but I I'll basically show you uh what you need to answer the question yourself and uh maybe we can quickly keep

8:19 um so if you roughly look at this uh there's roughly a quarter of people who think each of the statement is true right something like so what comes up in this in this context is uh is something again that's that's more important than in this concrete example so I'll I'll try to be not too quick on that part and that's called amortised analysis the idea behind this is that some operations in our resizable arrays will be very expensive if I have a push and I have to double the array I have to copy all the contents of the array so that's that's linear linear time for the copying that's really expensive arrays were much faster if you if I didn't have to do that and likewise for pop if I have to shrink the array to a new one and copy over so that that sounds bad right uh We've made something that was constant time linear time that's horrible I argued earlier that if you do a insert in the middle of a list in Python that's an expensive operation that you shouldn't do at least not if you want to repeatedly do it so how does that match up with otherwise lists being fast the point is that if you have an expensive operation

9:34 it means that many other operations that follow will be cheap and so you can amortise the cost you had for this expensive operation over many cheap operations so in a way the cheap operations pay for the expense for the expensive operation that's the intuition but what does that mean um formally and so okay don't don't get too scared by all the text uh we'll go through it again things you've seen before uh we'll use something like a potential function and you can think of this like a bank account when an expensive operation happens you uh you're in depth and the cheap operations have to pay that back or sometimes the other way around uh you have cheap operations and they pay an extra deposit that the expensive operations can then use if at the end of the month your your account is in reasonable shape it doesn't matter how it went up and down in between at least not too much if you just look at the overall outcome that's the idea and uh again finding the potential is sometimes tricky um this one is motivated by the following idea if this is your array s and it has length C right so it um from end to end can hold C elements uh our stack will only use a certain

11:02 part of it that's the actual elements in the stack or uh we do it like this again so there's n elements in the stack that we currently use now there are two um magic thresholds where we uh get active one is when the uh number of elements reaches the capacity and one is when it is just a quarter full so here we have the mark C and here we have a quarter of C so that's when when things get expensive so the intuition behind this potential is we take the distance

11:49 um from where we currently are to this one expensive Point that's um n minus a quar of C right um and we have C minus n that's the distance from the other

12:10 end and whichever of these is smaller that's our potential so uh we kind of um if you think of it in this in this bank account statement it means we have uh a lot of cheap operations still to come before something expensive happens it's kind of a a budget that we still have or a yeah a balance now you can analyze what this function can be it can be zero at the point where you you just exhaust the array or just fill it to the minimal threshold and you can show it's at most 0.6n uh that basically just comes from our invariant we require C to be between n and 4N and so if you find where this is equal you just set those two equal and then you get that uh the maximum value value of the potential is this 0.6n

13:08 okay now why does that potential help in any way what we'll do is we'll analyze each operation in an amortised sense where we take the amortised cost to be the actual cost what it really costs us to do the operation which in our case will be counting the number of array accesses which is uh just one or so if we just do a push or a pop and don't have to copy but we might have to do many more if we have to resize the array but then uh the amortised cost also takes into account the change in potential and why this is multiplied by four that's just to make the math work there's no no easy uh easy way to see

13:58 this uh let me briefly go through the three different cases that we have so we have we have the option that we do a push or a pop where we don't have to resize the array the actual cost is just one array excess I just get the element or I overwrite it uh but this um might consume a credit so I might move the current Mark of how full the array is closer to the red boundary I said I might it might also increase if I move away from the boundary this depends where I am here I'm roughly in the middle uh but if I have something like this the array is almost full but I remove an element so now the new fill is only up to this point I've actually increased the potential but that's all right um in the worst case we are one step closer to the boundary and so the potential might shrink by one if you multiply that by minus 4 It Means A plus four okay so the amortised cost is at most five and the units here are just uh array accesses if you want that's the first option what can also happen is we have a push and we have to double the array size then the actual cost is two 2 n+

15:21 one so you can work this out if uh if you allocate the new array of size 2N you have to copy n elements but then you have to read and write them so that's each n aises and you still have to the actual push you wanted to do that's the plus one so that's the actual cost is a lot but if this happens uh I claim that it creates a lot of credits now how does that work

15:53 um let's do this one in a bit more examp in a bit more detail so if we have a a push that's expensive the the situation before must have been the entire array is full and equals c that's

16:08 before and after that we've doubled the whole thing and it's half full plus one element right and in the new array these two marks at at the new C and the new Quad C they're actually far away from the new border Mark indeed this is uh the new n and uh we're away by essentially half n okay that's why you get this that extra credit and uh the plus one comes from well we're not really at this but we have one one further to the right

17:05 so if you take the distance between this and inserting what the capacity is namely 2 N so here n is the old size and the new size is n plus one I just added one more element then uh a quarter of 2 N is n half and the distance to n plus one is 12 n + 1 okay so I I have to uh add the actual cost and then minus 4 * the change in potential butus 4 * this is -

17:39 2N minus 4 which magically happens to come out at again five okay so 2 n + 1 the 2 N just cancels and then I have what's left is the one and plus 4 okay so again the amortised cost is at most five we have the third case that's the pop that's very similar indeed by analyzing when the pop happens to be expensive well it only can happen if we're at the quarter full now we shrink the array to half the set okay my drawing is not to scale but now um this was n is one qu C afterwards I make my new C to 2 N so that means I'm now half filled and actually one less because I pop one

18:59 element and so again the distance to the critical marks one4 C Prime again is is n uh quarter and half so again the distance here is roughly 1 half N I get the minus one in this case because uh I'm one one more to the left so by essentially the same calculation you again get cost of five

19:36 okay basic math here is not working previously the cost is the minus I didn't do correctly but it's at most five that's the part we need and in this case it's exactly five so the slides were right so uh okay great uh let's come back from this deep dive like why did we discuss amortised costs what's the what's the whole point there uh We've shown if I take the operation and I add the actual cost and the change in potential I always get a bound of at most five so what we do now is we take

20:24 operations say m operations and what I'll sum up here that's the amortised cost and I know that um I've defined this as the actual cost so each of the AIS is the actual Cost Plus the change in potential minus

20:54 4 and we'll just write um by1 minus uh by IUS one so that's the potential after operation I and the potential after operation IUS one okay now this type of sum has a special property it's called a telescoping sum because you see a term appears positive for one I and for the next I it will be negative so we can split this sum up to be the sum of all the

21:28 CIS and then we have minus four times the sum where we always have the previous term minus the term before and that completely goes away except for the first and last uh entries so this is the total cost the actual

21:57 cost and what's left of this is uh the potential at the very end minus the potential at the very beginning every other I appears both positive and negative so it's just cancels that's one side but we've also upper bounded the amortised cost in each Case by five so this sum is at most 5 time m

22:33 okay and so if you take this inequality and rearrange it so that you get uh the sum of the actual cost on one side then that's at most 5 M plus this

22:50 part and at this point we use that um we have a bound on on on the so let me uh spell it out so it's + 4 5 m - 4

23:10 5 now uh if we want an upper bound on this we can take the largest value that fi can use in this and it's at least zero so if I subtract nothing I only make it make it bigger

23:43 okay and so that's that's what's uh summarized on the slide if you take any sequence of M operations no matter what they look like the total actual cost is at most what spelled out here and you can say that's in Theta of M plus n so it's linear in the number of operations uh but it's also linear in the final size of the of the

24:11 array and so uh well if you start with an empty one the two are are essentially the same where m is bigger so let's come back to that question uh I'll I'll show you the answer um there's only one that's really true uh so the elements are not always stored in an array of size 2 N it's size 2N at the point where we resize but then n can change and we keep the capacity for a while the same um adding an element at the end doesn't take constant time in the worst case it's only amortized so if you do many operations it takes constant time um but it could happen that this element you add is one that triggers the doubling and that takes linear time um the last one is is even worse if you don't say where you insert or delete it could be in the middle of the array of the array and there's no way to do that in constant time uh only at the end in amortized sense and the amortized sense spelled out is the third answer any sequence of operations means that on average the operation was cheap but every individual one could have been expensive so whenever you use lists in this sense you have to keep this in mind

25:34 if it's a a real-time application where every operation has to be fast you can't really use the doubling array trick then you have to think of something different uh but for almost all use cases actually is a good trade-off because you're not doing one single operation you're doing many operations on the arrays and then it advertises out