you are 3b1b of programming, keep going 👍.

Only a little improvement in your implementation: You said that when you remove an element and the array gets less that half its max size, you shrink it. But imagine the case that the array has 4 elements with max size of 4, and then you add, an element, remove, that element, add other element, remove, etc (common use case that acts like this is an stack). In this case you resize your array every operation. It is better to shrink you array in half only when it drops to 1/4 of its max size Btw, awesome channel :)

4:12 another way to think about it is to convert to base 2. 1+2+4+8+16+32+64+128+256+512+1024... is nothing but 0b11111111111, and if we add one, it's trivial to see that all of the digits roll over and we get 0b100000000000. Therefore, the sum must be 0b100000000000 minus 1.

That's interesting, I was expecting the answer to be a linked list. This seems especially good for storing 1 or 2 byte items re space required.

I've often daydreamed of making a 3blue1brown-style youtube channel but more focused on software and computer science topics .. very glad to discover someone beat me to it! lol Subscribed! It might be nice to add third chapter on this a topic, to cover what real runtimes and libraries do, in pragmatic practice. Especially modern, garbage-collected runtimes... but even when I was writing C code 20 years ago, I remember almost never wanting to deal with copy-on-resize expanding arrays. Eg. knowing the OS virtual memory page size of 4kb, we just allocated linked lists of (4kb/sizeof(T)) slabs, and encapsulated all access to the "array" behind an interface, which could walk the list to find the right memory address quickly enough. Sure that means lookups are technically O(n) instead of O(1) but in practice it just doesn't matter much for vast majority of cases where n < 1000 and you're not iterating over random-accesses repeatedly. And if you do an expanding-array of slab-pointers instead of a linked list, you get better RAM locality (fewer page faults) walking through the list.. in practice these things matter! And it also lends itself well to a specialized implementation of merge-sort, and especially so, if each slab fits within the L1 cache line of your CPU. (And if you continue to generalize that array of slab-pointers .. you end up with a thing called a Skip List, which is probably a data structure worth doing a video on.)

Imagine having to resize an array when inserting new elements. This comment was made by the linked list gang.

Your visual geometric summations are gold

To avoid memory crawling one should not grow by a factor 2 every time, but more like 1.3.

My new fave channel

please keep posting consistently on data structures and algorithms

Got me thinking, and I came up with a solution that is always O(1) for appending new elements, but results in 3N writes, and takes 3N

Really it was the first idea that came to my mind when I watched the last video

An excellent one!

Would like to see videos on BSTs, Topological Sort, and Minimum Spanning Trees!

This video is excellent.

It is also worth noting that some programming languages support manual designation of sizes for dynamic arrays. In Swift, for example, you can call reserveCapacity(_:) method on arrays to manually set the minimum size of a dynamic array. This is favourable when you know the exact required size of the array because after the reserveCapacity call, it will always be O(1) operation when inserting elements up until you run out of the reserved capacity.

2:06 when you said 1 million here my first thought is that virtual addressing dramatically alters this at scale above the page size. Once you exceed the page boundary items never need to be copied when the array is resized. This means you can freely add pages with O(1) overhead and the 2x is unnecessary (Though it is also unimportant as the allocated memory is also not wasted).

contiguous storage FTW!

This method is brilliant. But I did not know that the runtime of allocating memory is independent of the size of the allocation. Great!!

great channel

I like what you do, and you might find me needlesly picky but "on average" and "amortized time" are not the same thing. Being O(f(n)) amortized time is stronger that being O(f(n)) on average. For example, if you start from an empty binary search tree and insert elements one by one, if the elements are chosen "at random", then each insertion will take, on average, O(log(n)) time. But this does not rule out the case in which you are really unlucky, and each insertion takes O(n) time, thus the total time is O(n²). This case is just very unlikely. If your binary search tree had O(log(n)) amortized time, then the total running time will be O(n.log(n)) regardless of the data. As a matter of fact, in the scheme that you describe for both insertion and deletion, every operation if O(1) on average but not in amortized time. Indeed, suppose that you have an array of size 1024 which contains 1023 elements. - You then insert 2 elements. You thus have to create an array of size 2048 which take O(n) time. - You then remove 2 elements. You end up only using 1023 element in an arry of size 2048. You thus create a new array of size 1024. - Then you insert 2 elements, then you remove 2 elements... Of course, this is very unlikely to happen but this cannot be ruled out. The operations are in O(1) time on average. Let N be the size of the array and n the number of elements used. If you create a bigger array of size 2N only when the array is full and you create a smaller array of size N/2 only when n

Pls share more videos...Thanks !!!!

I had a different idea for dynamic arrays, my idea is that you have a "segmented" system where instead of reallocating and copying the array every time you want to resize it you just take the pointer to it an add it to an auxiliary data structure that contains some more information about the array at large like how many "segments" there are, how large each one is (based on what its size was when you allocated it) etc. Like let's say for example when you create the array originally you want it to have 4 elements, so when you create it you could allocate n*2 like in the video (in this case 8) elements then take the pointer to that array and add it to the array segment table or whatever you would call it, along with the size and the current index into that segment (for adding/removing elements) which at the start would be 0 ofc. Every time you want to increase the size of the array you just get the new chunk/segment and repeat the process over and over until the array of segment information is full in which case THEN you would reallocate and collapse the array fully then start the process over again. The pros of this idea would be that resizes would be pretty fast because most of the time you dont have have to copy anything, and insertions/deletions would be pretty fast because you dont need to move around the values in the entire array, only the ones in the segment of the value you want to remove/insert, in fact you could accelerate insertion and deletion even further by adding an array of bitmasks for each segment in the information part that tell whether each slot is open or not so you can just do in place insertion and deletion and not have to move anything unless you explicitly need to in which case you could just make another function for that. Of course the main downside to this idea is it would take a lot of memory and disproportionally favors large allocations and disadvantaging small ones which doesnt exactly help. And resizing the array down would be a bit more finicky than sizing up because you would be tied to the size of the chunks you allocated originally so your best option would probably be to take the slow route and collapse it if you actually need to free up space and downsize and not just move stuff over while keeping the chunks. Maybe this is a really bad idea but it's what I came up with 😂 its probably not even original either, I don't think it's a linked list because I'm pretty sure in a linked list each entry contains information about the next whereas in my idea the data and information are separate, but idk much about the different types of dynamic arrays so maybe it is

6:30 It doesn't quite work. If We have an array of size n = 2^k and then delete an element and then insert an element again, we'll perform O(n) operations. We can continue this delete-insert pattern O(n) times which will result in O(n^2) time complexity. The better approach is to resize the array by half of its size when there are not < capacity/2 elements but < capacity/4.

As far as I know, (in C# anyway,) the List class doesn't reduce the size when elements are removed. I think this is done under the assumption that if the list became a certain size, it should be expected that it could reach that size again.

Dhanyawad

thanks

or just be an omega galaxy brain chad and simply create an array big enough that you won't ever have to resize it :P

In Java a arraylist increases by 3/4 size . That's the default. However nice explanation. ❤️

Isn't the maximum space the table uses 3*N units? Because when you are copying you have allocated both the old and new array simultaneously?

Looks like my half assed attempt at dynamic arrays when I needed them in C wasn't so bad after all. I always assumed the real implementations did something more clever

In my experience, its not so much the number of insertions that takes the most time, but rather waiting on the memory allocation function to return. even so, I like the general idea here and I ran into a similar problem when implementing my own dynamic arrays years ago. my solution was rather than doubling, to simply make the array capacity equal to the nearest power of 2 that can contain every element in the array. i.e an array containing 0 or 1 elements has a capacity of 1, an array containing 2,3, or 4 elements has a capacity of 4, an array containing 5, 6, 7, or 8 elements has a capacity of 8, etc. This has the advantage that for large array sizes the array always takes up a whole number of pages since pages are of a size that is a power of 2

Is increasing size by a factor of 2 the most efficient? Would another factor, like 4, make a difference?

I had something other in mind to make a dinamic array: we have a chosen size that is the minimum size of the array, and another chosen size that is the size of every space added if the space isn't enough. It starts creating the space using the formula (M+KA): M is the minimum size of the list, A is the size of the space added every time, and K is an integer required to make the length of the array to at least the number of how many variables it contains. K can be calculated too with this formula ((L+1-M)/A): L is numbers of the variables to store. Note: if the value of K comes out as not an integer it has to be rounded up (the +1 will be explained later) This can be used instead of trying every value of K, since the M and A variables are chosen earlier after doing some testing. This doesn't work by copying all the array but bigger and adding something, instead Option 1: it has an extra space (that explains the +1 of before) that is a terminator. Option 2: the first value stores K or the length of the array, but another extra space at the end becomes the terminator, so needeng a +2 instead of the +1 mentioned before (this to ensure that some variable stored in there is not believed by the program as being the terminator). When the list still doesn't need more space the terminator is just a value telling the array at the end, but if the array is full and you try adding another value, the terminator becomes a pointer and points to another part of the memory, where an array of length A is saved, ready to save more variables in it. The new array has the same properties as the first one, but now you access the data trough the first one. The way to delete a value and add a value in the array is pretty much the same you said in the video. The big O notation would be this: O(1) to add a variable. O(N) to access a variable. O(1) or O(N) to delete a variable. O(N) to add a variable at a specific index. O(N) or O(2N) to delete a variable at a specific index. All the parts I didn't specify are because I tought of them as they are explained in the video. edit: A(the size of the space added every time) has not to be constant, like in the video, but it could be powers of 2.

we know the formula to calculate geometrical progression . ar^(n-1) 4:25

I don't think that most implementations of dynamic arrays shrink automatically. You usually have a trim operation for this.

Does this all happen in the stack memory?

Wonderful video, brilliantly explained but the answer is a bit anticlimactic. After the first vid is was obvious that copying the array with every insertion was expensive so I just shrugged and right the obvious answer was to double but I wonder what brilliant solution is in place. Doubling. Ok. Don't get me wrong, this was a super valuable insight into performance analysis and big O notation. Just the solution is what I think every programmer's first instincts would have been if they had to put it together with a tight deadline.

but what about array with different data type for each element?

I have seen many professional implementations of a dynamic array that use a resize-factor of 1.5 instead of 2. Really sure 2 is the best resize-factor? What's with "memory-wasting"?

why not use fibonnaci instead of **2?

Why not just use fixed arrays of say, 16 and when an array becomes bigger than 16, create a new empty set of 16? Wouldnt this greatly improve mutation speed?

6:13 can't you just deallocate the unused half of the array?

Can we do O(1) on insert in the middle?

Why the factor of 2? What about factor of 3 or you know any number 1.5, 1.2,… Will it still work or work better?

Can someone explain me the difference between dynamically allocated array in C using Realloc and the one demonstrated in the video.

1:28 Insertions 12? Huh? You don't show that or explain the insertions count.

nice vid!, deletion may be simplier than shifting in some scenarios, sometimes if you only want a collection of elements and don't care about index consistency (vertices, particles, event buffers, etc) and you want to delete an element X, you can just copy the last element into X and pop the array being a O(1) operation.

Here is an interesting problem with doubling the array size: You can never re-use the memory that was used previously. No matter how many times you move your data forward, the new array is always larger than all the previous space you ever used. If your dynamic array is the only used memory on the whole computer, you will therefore at most reach 50% efficiency. The answere to this is to increase the array by a factor that is smaller than 2. The amortized runtime is still O(n), but the array grows slow enough that whatever memory you used previously will eventually leave a gap large enough that your new array can fit in it. Of course, this is not a problem for most software. If you are dealing with a truly massive amount of data and still require a dynamic array, using a factor such as 1.5 should be worth trying out. (1.5 can be easily achieved by multiplying the size by 3 and then dividing by 2. Make sure the multiplication by 3 doesn't accidentaly create an overflow.)

I am sad that nobody said "page tables"...😢

I am wondering what would happen if you use a number different than 2, but that's a question for tomorrow when I have had some sleep

Um dos melhores do youtube

But why not Arraylist?

I thought the solution would've been a mix of arrays, linked lists, and modular arithmetic, but it was much simpler than I had imagined :D

My idea for dynamic arrays would be: Every item in the array takes up two pieces of memory, one to store the item, and then one that stores the address of the next item in the array (a nullptr if it is the last element) This should mean that it uses 2N memory, but wouldn't have to do much moving around. To insert a new element, it can just go to the end, change the pointer to a free space in memory, and then put the new element there. For inserting and deleting elements, it would be a bit more complicated, but not too complicated. Sorry if I didn't explain this well.

;)

What about *pointers

ha jokes on you i learned all this from C++ since you need to learn how a vector works.

While technically correct, it really bothers me that you use the verb ‘insert’ for the operation of appending a new value at the end. At least in my mind the verb ‘insert’ is reserved for inserting at a given index, requiring the relocation of later elements.

In my data structures class (or was it discrete math?) my teacher off-hand said "oh yeah, for a dynamic array you want to always double the space if you reach the limit." and that stuck with me because he said it so casually but it represents so much math

Actually any memory pointed by an array address pointer isn't "real memory", it's all virtual. Nominally it's 4k smallest size nowadays. Array pointers are virtual addresses and the cpu's mmu takes care of converting it to a real memory address. No copying is needed when the page limit (say 4k) is exceeded, kernel just allocates a new page from the real memory and appends it to the arrays virtual memory, mmu takes care of all the rest and it seems contiguous to the program.

Am I not seeing something restricting an obvious answer here? How about: You start with K elements. You want to add N elements to it. You just make a new array that is K+N long, and insert your K+N elements into it, resulting in K+N insertions. This results in a space requirement of N+K, which is O(N), and a time requirement, based on insertions, of N+K, which is also O(N), and performs better than the one in this video that uses 2N time. Also, only one numerical calculation is required for the entire process, computing N+K. No multiplications are done. How is that not the real final answer to this?

How about an array of arrays. When you need to grow beyond the boundary, you only have to grow and perform inserts on the the parent array plus memory allocation for a new page. Find the page offset by dividing the index by the page size and get the page index by taking the remainder of the previous division operation. Performance is dependent on the page size. Adding is faster, reading almost as fast. Insert and removing an element is still problematic, but you only have to shallow clone the outer array before the point of insert/removal and then perform inserts on pages beyond the insert/removal point.

Wait... it is that simple?

I have absolutely no clue what this is a about

just do realloc lmao.

What if instead of when you make an array and you clone everything over, you don't clone everything over? You just make a new array, and start over but from index (amount of arrays + 1) not including the new array. I guess the new array size can be the current full array size to double it, as described how this is efficient in the video. Then you memorize where all the arrays are stored.