Video 3-3: Resizable arrays deamortized & optimal space

0:03 Sometimes you would like to use these amortized doubling arrays but you can't really because you really really really want a worst case guarantee for individual operations. So sometimes uh this is called a real time requirement that you cannot afford some operations to be slower than others even if they average to a good time. You need every single one to be fast and then you simply cannot use this data structure we discussed and analyzed last time because it occasionally has to do the copying. There's no way around it. Now, here's a um a trick that is I'll show it on this data structure. It's somewhat more general. You can apply this often times when you have amortized data structures that lets you get around this and in a way you trade a bit of space for time here. Um it has one assumption that we'll come to. Uh the general idea is to deamortize such a solution as we've seen. One an amortized solution that needs to spread the cost of expensive operations over several deamortization tries to preempt that so that you um you already know you will eventually have to do this expensive copying. Let's try to spread the cost of that out a bit and um work ahead of of time. The way to do this here is to have three arrays instead of just one where you keep the current one that you actually want to work with and also the twice and half as big ones around as a fallback. So that when you run into the situation where you would have to now say double the size, this twice as big array is already there for you ready to jump to.

1:51 There's um there's one caveat that this needs um which is I'm I'm assuming here I can allocate arrays in constant time without initialization. So sadly in Java you couldn't implement this properly. There's no way to do that without spending the time to fill in the array. Uh but that aside, in a low-level language, you could do this. Um and the trick is so here's uh what this might look like. Uh you have some actual array in the middle that works just as the amortized solution we've seen. And then you have um the two versions of the array of half and twice the size. Of course, the half the size one may not be big enough to hold all elements. It holds the prefix up to this position where it can. And um the longer one has space for many more elements. Now, let me show you what this looks like briefly before we discuss um the solutions. there.

3:07 Here's the situation. Now, uh this shows an intermediate stage where um some elements are already filled. Let me go back to what happened when we had to say double the size.

3:22 So, we're coming from some previous state. Now the array our actual working array is out of capacity. So we have to allocate the twice as long array and make that the current one. Right? This this is the previously bigger one. This becomes the current. I'm allocating a new twice as long array. Suppose that is possible in constant time. Wouldn't be in Java. But with me alloc you could m alloc you could do this. and the smaller previously smaller array we three that one we forget. Now, of course, there's a problem, right? Normally, if I double the array, I would have to copy my elements down here because they eventually need to be in that array that I'm working with. But the trick is that we don't need this twice as big array for quite a while. We can only need that once we run out of spare space in this current middle array. And so what we do over the subsequent operations is whenever we add a new element here, we add that also to the two other arrays. That's kind of for free. But on top of that, I'm going to copy two elements from my uh small array to the bigger one.

4:39 Why two? because that happens to be enough so that by the time I might need the bigger array, I'm guaranteed to have caught up with my copying. So, um here for the for the case where you um only add elements, you certainly run out of elements to copy before you have to double again. The bad case happens if you pop elements. So that you may want to go down uh maybe so the copying two elements is already a bit uh overly cautious and once you're done with the copying the operations get a bit cheaper.

5:20 So you can add more elements and then here okay pop one. And if you now go back to insize, I should really go back to in size. Sorry.

5:43 Now you have quite some time before you reach back the point where you have to half again. Okay. Um again, two things we have to do. Question.

6:01 Yeah, I'll put the links on the website. I'm a bit behind on updating the website with these. Uh but yeah, you can you can have a play with them. Um they try to stick very close to the lecture, but they're not all equally polished in terms of what they show. Let me know if you find some bugs. Yep.

6:33 Oh yeah. Um so the question is don't we pay something for the copying of the elements? Uh we do. Um we definitely need what previously was a single write operation. We may need three for each of the three copies. In the example it was when you were be half the length of this small array. and only these two arrays get updated. But in principle, it could be all three. Uh plus you may have this uh copying that you have to do to catch up with the duplicate doubling of the array size. So this also costs namely uh two extra copies. So you may copy quite a bit um I guess up to five operations where previously it was a single one. On the positive side, you never ever have to do more. Each step now costs at most five full stop. No amortization needed. Of course, understanding why this data structure works kind of relies on the analysis we've done for the amortized one. So, pedagogically speaking, you would first want to go to the amortized one, understand the analysis there, and then deamortize it again. But in the guarantee for the runtime you get at the end, this has no amortization anymore.

7:56 Uh I'm I'm skipping the details of why exactly you get um ready in time. Um let's just state the results here. Uh we have a constant number of things that we need to do for all these operations we've had before. no unknown um amortization anymore. We may have up to seven array accesses. I guess that's um if you do uh a push that needs to double, then you also write your new element in two arrays. And um if you work out the worst case, it's 14* n space that you may have at some point in time. That's a bit annoying that we pay so much. And you can play with the constants to reduce the space and increase a bit in time. Um, by uh basically by doing more than two copies, you can get away with not exactly doubling the array, but maybe just making it 50% larger, something like this. Um, if you really need this worst case guarantee and no amortization is possible, that kind of trade-off may be inevitable.

9:13 And the caveat from before, you can't really do this in Java. Now, once you started thinking about this, and I should say the whole um this whole slide is is kind of not exam material. This is just for a bit of extra fun. All of these um data structures still need linear extra space. And yeah, you may ask yourself if this is necessary. So all of them all of them store essentially a large integer multiple of the space that we would need for elements. Um, and if you insist that it's a contiguous chunk of memory, it seems tricky to um, avoid, but it is actually possible to do better. Uh, there's a research paper that shows in some sense the best possible way to do this. Um what it gives you is constant time worst case operations like the uh previous solution but it has not a multiple times the space that you need then rather just square root n extra space on top of only storing the elements that you really need. This is way way better than our amortized solution. So we've not even come close to this and I'm not going to explain in detail how it works. is a bit more complicated. Uh but in uh the intuitive essence is you don't really maintain one long array. You just simulate you had access to something like this and you fake it if you want. Uh you keep a collection of small arrays of uh cleverly chosen sizes say. So you have certain um uh a hierarchy of of sizes um where you have arrays of of a certain length and then a certain collection of those and you keep the sizes just so that you can add another uh chunk of this size without using too much extra space. But the hierarchy is still cheap enough to navigate so that you can do constant time access by index.

11:26 It's not a real array anymore, but it behaves as if it was one. So maybe that's good enough. And um in some senses even this extra space is the best possible trade-off that you can have.