1 00:00:00,008 --> 00:00:05,483 [MUSIC]. 2 00:00:05,483 --> 00:00:10,243 We've seen multidimensional arrays now, at least two dimensions, but things 3 00:00:10,243 --> 00:00:16,890 extend, in the same way to three dimensions and four and more dimensions. 4 00:00:16,890 --> 00:00:21,178 what I want to do now is introduce you to a multi-level arrays which are a little 5 00:00:21,178 --> 00:00:25,223 bit different. They try to do some similar things but in 6 00:00:25,223 --> 00:00:29,249 a very different way using pointers rather than a continuous allocation in 7 00:00:29,249 --> 00:00:33,557 memory. Lets take a look at the multi-level 8 00:00:33,557 --> 00:00:37,376 array. Here I'm showing three one-dimensional 9 00:00:37,376 --> 00:00:42,360 array. That we've that we declared are zip digit 10 00:00:42,360 --> 00:00:46,496 arrays. one for each zip code of five digits 11 00:00:46,496 --> 00:00:50,973 each, okay? One-dimensional arrays we're now going to 12 00:00:50,973 --> 00:00:56,671 declare a multi-level array called a univ that is actually an array of pointers to 13 00:00:56,671 --> 00:01:02,107 integers. You notice the star there in front of it 14 00:01:02,107 --> 00:01:07,387 and it's going to have this number of elements in this case set 23 and the 15 00:01:07,387 --> 00:01:15,775 three elements will be our three one-dimensional arrays from above. 16 00:01:15,775 --> 00:01:20,870 And you'll see that that looks like it should be a two-dimensional array, right? 17 00:01:20,870 --> 00:01:26,260 We've just organized three zip codes into an array of three elements. 18 00:01:26,260 --> 00:01:32,280 each element having five digits. But is this a two-dimensional array? 19 00:01:32,280 --> 00:01:35,150 well it's not. It's a little bit different. 20 00:01:35,150 --> 00:01:39,359 and the reason it's different is because they, the the three a, the three sub 21 00:01:39,359 --> 00:01:43,510 arrays do not have to be continuous in memory. 22 00:01:43,510 --> 00:01:48,590 and they don't have to be in row major order like we had before. 23 00:01:48,590 --> 00:01:52,100 In this case, you'll notice that the three arrays have been allocated to three 24 00:01:52,100 --> 00:01:57,404 different locations in memory. Separately, each one of them in isolation 25 00:01:57,404 --> 00:02:01,420 they were declared as separate arrays initially. 26 00:02:01,420 --> 00:02:06,958 Then our array univ has three pointers in it it's an array of pointers after all 27 00:02:06,958 --> 00:02:11,404 and these were point to those the beginning of each of those three one 28 00:02:11,404 --> 00:02:18,010 dimensional arrays. But [INAUDIBLE] not in any set order. 29 00:02:18,010 --> 00:02:21,850 It doesn't expect them to be in a particular arrangement in memory. 30 00:02:21,850 --> 00:02:25,920 This turns out to be also the way Java represents arrays all the time. 31 00:02:25,920 --> 00:02:31,395 It does not have really multi dimensional arrays, it only has multi-level arrays, 32 00:02:31,395 --> 00:02:36,736 involving pointers like this. Although, this is made invisible in the 33 00:02:36,736 --> 00:02:40,226 language, but this is what's going on underneath. 34 00:02:40,226 --> 00:02:44,628 Okay, so our array univ has three elements, each one of them is a pointer 35 00:02:44,628 --> 00:02:51,170 that's 4 bytes long and of course, it's a one-dimensional array of pointers. 36 00:02:51,170 --> 00:02:55,856 So, they're represented one after the other, in memory, each one of them points 37 00:02:55,856 --> 00:03:00,755 to an integer basically the starting integer of the three one-dimensional 38 00:03:00,755 --> 00:03:08,348 arrays that we have. So let's take a look at how access works 39 00:03:08,348 --> 00:03:12,413 to this. So, here we're going to have the same 40 00:03:12,413 --> 00:03:17,657 procedure we had before for getting a digit of the zip code only this time 41 00:03:17,657 --> 00:03:22,673 you'll notice, although we address it, it looks the same, let's see what actual 42 00:03:22,673 --> 00:03:31,437 assembly code gets generated, okay? So see at the beginning, we'll have our 43 00:03:31,437 --> 00:03:38,084 first index in the register ECX. And we're going to multiply that by four 44 00:03:38,084 --> 00:03:43,110 and put the result in EDX. And why are we multiplying it by four? 45 00:03:43,110 --> 00:03:48,126 Well, because we're indexing into our univ array and we need to know how much 46 00:03:48,126 --> 00:03:53,165 of an offset to have to get the right pointer. 47 00:03:53,165 --> 00:03:58,181 Once we have that pointer, you'll notice we will use that, to get that pointer we 48 00:03:58,181 --> 00:04:03,045 will use that offset we've just computed added to the starting address of the 49 00:04:03,045 --> 00:04:09,010 array, and then access that memory location. 50 00:04:09,010 --> 00:04:14,066 Ac, this is actually reading that memory location, getting the pointer, and 51 00:04:14,066 --> 00:04:19,017 putting it into EDX. Okay, so we've done one memory access 52 00:04:19,017 --> 00:04:23,070 already into the univ array to get the right pointer. 53 00:04:23,070 --> 00:04:30,177 Once we have the pointer, we're going to, use that as an offset to four times the 54 00:04:30,177 --> 00:04:36,872 other parameter, the other argument to this function, the index of the digit, 55 00:04:36,872 --> 00:04:42,980 okay? And the four there is because of course 56 00:04:42,980 --> 00:04:47,600 we're doing integers and they're four byes each so we're computing the address 57 00:04:47,600 --> 00:04:52,430 along the one dimensional, the offset in the one dimensional array, adding that to 58 00:04:52,430 --> 00:04:56,770 the starting address of the one dimensional array that we just got from 59 00:04:56,770 --> 00:05:03,184 the univ array. So, that gives us a second memory access, 60 00:05:03,184 --> 00:05:07,627 we're now going to that memory location and actually reading the digit. 61 00:05:07,627 --> 00:05:12,226 So, the important thing to understand here is that in this case we must do two 62 00:05:12,226 --> 00:05:16,446 memory reads. First to get the address to the row, the 63 00:05:16,446 --> 00:05:19,678 pointer to the row and then access within that row. 64 00:05:19,678 --> 00:05:25,957 In the multidimensional case, we could do that in one address computation because 65 00:05:25,957 --> 00:05:32,986 we had the guarantee that each row followed one after the other. 66 00:05:32,986 --> 00:05:38,476 Okay, so, the access does look similar in the C code okay, in fact they look 67 00:05:38,476 --> 00:05:44,506 identical, but in reality because of the different structure, here a continous 68 00:05:44,506 --> 00:05:52,340 arrangement in row major order. And here first the level of pointers that 69 00:05:52,340 --> 00:05:57,961 get us to the start of the row. And then a one-dimensional array. 70 00:05:57,961 --> 00:06:04,014 this requires only one memory access. we can do, compute the entire address in 71 00:06:04,014 --> 00:06:07,940 one expression. here we have to do it in two parts. 72 00:06:07,940 --> 00:06:13,116 First, to get the pointer and then to add on the offset and access again. 73 00:06:13,116 --> 00:06:17,480 So two memory accesses. So these arrays are a little bit more 74 00:06:17,480 --> 00:06:23,290 expensive in performance because we have to do those two memory accesses rather 75 00:06:23,290 --> 00:06:27,508 than one. Okay let's complete this video the same 76 00:06:27,508 --> 00:06:32,400 way we did the previous one. With some examples of accesses. 77 00:06:32,400 --> 00:06:38,608 so let's go to univ two, three. the address computation here, you'll 78 00:06:38,608 --> 00:06:45,850 notice is first to get the the starting address of the third element of the univ 79 00:06:45,850 --> 00:06:51,792 array. That would be the 56, that address is the 80 00:06:51,792 --> 00:06:56,095 UCB zip code. And then the offset within that, four 81 00:06:56,095 --> 00:07:00,676 times the second index of three. So that gives us an address of 68 which 82 00:07:00,676 --> 00:07:05,760 in fact yields the fourth digit of that zip code, or the number two. 83 00:07:05,760 --> 00:07:08,749 And that is absolutely guaranteed to always be the right answer, because 84 00:07:08,749 --> 00:07:13,639 we're, we're doing the right thing here. Let's look at a case where we use an 85 00:07:13,639 --> 00:07:19,091 index that's a little off this one, five. Okay, in this case the same address 86 00:07:19,091 --> 00:07:24,166 computation is done. this time we yield an address of 36. 87 00:07:24,166 --> 00:07:29,534 which is a not part of the one-dimensional array we were really 88 00:07:29,534 --> 00:07:34,666 going after. We were going after the second element of 89 00:07:34,666 --> 00:07:40,038 the univ array which should have been to the start of the CMU array, and then 90 00:07:40,038 --> 00:07:44,857 because we have an offset of five elements, we're going off the end of that 91 00:07:44,857 --> 00:07:53,884 array and we go to address 36 out here. Turns out by pure coincidence, that is 92 00:07:53,884 --> 00:08:00,710 the first address of the UW zip code array, but that is a pure coincidence. 93 00:08:00,710 --> 00:08:04,415 It just happened to be that way the UW array could've been somewhere else in 94 00:08:04,415 --> 00:08:08,024 memory. And then, wouldn't have had any idea what 95 00:08:08,024 --> 00:08:12,644 value would've come up here. In this case, we do get the nine, but 96 00:08:12,644 --> 00:08:16,340 there's absolutely no guarantee that that will be the case if we run our program 97 00:08:16,340 --> 00:08:19,924 again, because we might end up in a different that UW array might end up in a 98 00:08:19,924 --> 00:08:26,754 different part of memory. Okay let's do that 2 minus 1 example 99 00:08:26,754 --> 00:08:29,760 next. Again, the same address computation. 100 00:08:29,760 --> 00:08:35,200 We go to address 52, but that is outside of the element we were really trying to 101 00:08:35,200 --> 00:08:39,072 address. And again, it's only working out by 102 00:08:39,072 --> 00:08:43,934 coincidence that we get the 5. no guarantee at all that that would be 103 00:08:43,934 --> 00:08:49,708 consistently that value. Similarly for this one, we're even going 104 00:08:49,708 --> 00:08:53,698 outside of the university array to the next element where the next element would 105 00:08:53,698 --> 00:08:56,980 be. but who knows what's there and what 106 00:08:56,980 --> 00:09:00,654 address we'll be reading. That will take us to some random part of 107 00:09:00,654 --> 00:09:03,520 memory. We'll then go 4 bytes before that, 108 00:09:03,520 --> 00:09:08,600 because of the minus 1. And who knows what's there even. 109 00:09:08,600 --> 00:09:12,248 so we have no idea what address it is, we have no idea what value is there, of 110 00:09:12,248 --> 00:09:15,849 course. and no guarantee that anything will ever 111 00:09:15,849 --> 00:09:20,941 be consistent in this case. for the last one here 1, 12 the same 112 00:09:20,941 --> 00:09:28,070 address computation yields a seven. just because of pure coincidence that 113 00:09:28,070 --> 00:09:32,330 there happened to be something there, but again those arrays could've been shuffled 114 00:09:32,330 --> 00:09:37,508 around, so no guarantee on that either. Remember again the code doesn't do any 115 00:09:37,508 --> 00:09:41,635 bounds checking C doesn't do that. We'll see later that Java does and will 116 00:09:41,635 --> 00:09:45,293 actually give us a warning that we're accessing out of bounds that's a very 117 00:09:45,293 --> 00:09:49,268 useful thing. At an added cost of an extra check every 118 00:09:49,268 --> 00:09:52,370 time. C doesn't bother with that extra check, 119 00:09:52,370 --> 00:09:57,858 just does the address computation. Alright, so the add, the location of each 120 00:09:57,858 --> 00:10:02,950 lower level array in memory is not guaranteed in this case. 121 00:10:02,950 --> 00:10:06,952 In the previous multidimensional case, we had a guarantee because of row major 122 00:10:06,952 --> 00:10:11,310 ordering in memory. and this time we do not. 123 00:10:11,310 --> 00:10:14,755 All we know is that there's a first set of of pointers, and then we follow the 124 00:10:14,755 --> 00:10:21,635 pointer to the one-dimensional array. no guarantee of how those will end up in 125 00:10:21,635 --> 00:10:25,414 memory. Alright, to do a little bit of a 126 00:10:25,414 --> 00:10:30,334 summarization of arrays in C then is arrays themselves are a contiguous 127 00:10:30,334 --> 00:10:35,720 allocation in memory. there is no bounds checking. 128 00:10:35,720 --> 00:10:41,048 we can usually treat the array like the array name like a pointer to the first 129 00:10:41,048 --> 00:10:45,220 element. And then elements are offset from that 130 00:10:45,220 --> 00:10:49,737 start of the array. multidimensional arrays are continuous in 131 00:10:49,737 --> 00:10:55,540 memory and in row major order. multi-level arrays, these ones we've just 132 00:10:55,540 --> 00:11:00,510 been discussing, are not contiguous, not contiguous, and pointers are used between 133 00:11:00,510 --> 00:11:07,100 levels, so we have many less guarantees about how things are arranged.