What if you had to invent a dynamic array?
Vložit
- čas přidán 26. 10. 2019
- In this video, we explore how we might create arguably the most used data structure in the world: the dynamic array (also know as the array list).
Support: / reducible
This video wouldn't be possible without the open source manim library created by 3blue1brown: github.com/3b1b/manim
Here is link to the repository that contains the code used to generate the animations in this video: github.com/nipunramk/Reducible
Music: October by Kai Engel freemusicarchive.org/music/Ka...
Choose your weapon:
std::vector
VS
Pointer to pointer that points to array of the pointers
No, more like including a library with thousands of lines VS a struct with 3 pointers
C macro that declares and defines the array struct and functions using token paste operator.
VS
Stretchy buffers
@@srijanpaul why a macro if you can make a template or just use void pointers
@@igorswies5913 In C macros are the closest thing to templates and that's what people usually do for low budget std::vector
@@srijanpaul I dont care about what people usually do and I'm talking about C++
1960's dev: I need a dynamic array - builds linked list
1980's dev: I need a dynamic array - allocates a ton of memory and hopes he never over runs the buffer
2020's dev: I need a dynamic array - declares a variable of dynamic array type
No it's still most efficient if you know how much memory you will use and just allocate upfront.
Many games and engines still use these types of allocators ALL THE TIME.
@@captlazerhawk ok buddy
@@captlazerhawk "if you know how much memory you will use"
Yes... Exactly
@@oivinf thats why you often just limit size and then cleverly reuse
@@oivinf Knowing how much memory you will use, as in knowing the max amount of memory. You don't need a dynamic array for some things if you know your memory use won't go over a certain amount. This is everywhere in the lower levels of game engines and rendering apis.
I've already written my own dynamic array, but I still clicked for some reason. Glad I did though, great video!
Same! haha. I did when i started programming in C++, i didn't know it already had dynamic array libraries. :P
I think most low-level programmers had, at least once.
@@rhodexa I did it in C - only after watching this video, based on what it said. It was pretty simple to do actually. :D
pretty sure every programmer that was banging keys in the 80s or 90s have written many dynamic array implementations, each having different strengths and weaknesses - hash tables, splay trees, hash tables of splay trees, and so on - the common misunderstanding folk have about all this is that its still fixed size at the end of the day - moving responsibility to a different allocator than your own doesnt change things
I learned c, literally the first thing I asked myself was how do I make a dynamic array. The answer as always when it comes to c is pointers.
Very nice videos. You could add that the constraint of fixed length array is often due to memory allocation : the program asks for "m bytes", and use that for the array. If we end up with needing more space, in general the memory "just after" the one we use for the current array is not available (thus we can not just extend the array). We need to ask for ">m" contiguous memory, and use that for our new array, and we have to copy the elements of the previous array into this new one before we can add the new element into it.
Hi Oliver, that is a great point and you're right that this is something I should have included in the video. Thanks for sharing!
Love this! and really appreciate you sharing your github
This is a fantastic video. Thank you for all of your hard work in putting things together so that other people can learn something new.
Great video! The style reminds me a lot of 3 blue 1 brown
He's using manim, that's why
@@jonasdaverio9369 oh word that's cool
The fact this video came on my recommended the day after a CS test on linked lists is mysterious timing indeed
Gotta be honest, I did not expect this to end up going into big O notation 😂. Awesome video
Great video! Such a simple problem, yet it introduces many concepts of computer science. Thanks
Never utilized my time better than this.. Loved this video...Pls share more videos...deepest gratitude to you
Reminds me of the time I actually did this - in C, for a two-dimensional array. The purpose of was to reconstruct a continuous image from translating video, for use in restoring scrolling text in old silent movies.
if it's for reconstructing a image then why didn't you just use a regular array?
@@phillipanselmo8540 Because C, and no way to determine the size of the final image ahead of time.
This type of channel is exactly what I have been working for
Great content and amazing animation!
Awesome video!! Keep it up :)) I'm certain you're gonna grow
Nice video and beautifully explained.
If part 2 isn't showing up for y'all like it didn't for me, here's the link czcams.com/video/Ij7NQ-0mIVA/video.html
thank you kind stranger
You are a hero
hajahhrhahsha I had to use my own comment when I came back 2 years later
your videos are fantastic dude!
This deserves way more views. Explains the concept of an array and gives an example of what Big O for runtime is like! ✌
This was an assignment I had to do back in my intro to programming class, this video would have helped back then
Love the 3blue1Brown style
Nice work!
The 3Blue1Brown of computer science
Oh I love this channel
С: Am I joke to u?
Assembly: you guys are able to declare variables?
Brainfuck: wtf
Stretchy buffers.
ever heard of malloc/realloc/free?
@@igorswies5913 : have you heard about efficiency ? have you needed to process 1 million operations in few milliseconds ?
Hey, why video so short? :)
I have expected speech about multiplying array by 2 or exponent. Or about linked lists. Or about trees and hash tables.
In hash table you have O(1) write and access time.
It would be amazing to cover this subject completely
I have no idea why I was reccomended this, but I clicked anyways.
I hate math lessons, but those little illustrations you used made this too adorable to hate.
Congratulations, sir, you made me watch a math lesson out of my own volition.
Very nice video, but I feel like a better space metric would be maximum concurrent usage; i.e. the first scheme has a max concurrent space of 2n-1 (the second scheme has a maximum concurrent space averaging 2n)
Um dos melhores do youtube
Computer scientists sometimes care about exact formulas. Given your experiments, we could conjecture that a resize of r elements has polynomial formula starting (1/2r)*N**2 + ... If we insist on a linear-cost behavior, and try to cancel a power of N, then this suggests r=N/2 without actually working a recurrence relation.
I feel so old. To me it feels like yesterday when you had to roll your own dynamic arrays.
Dhanyawad
Very 3Blue1Brown inspired?
@@ishdx9374 what library is this?
@@timkluge426 It's called Manim. It's on GitHub.
@@timkluge426 check description
yup, i've done the create new array version, next time i'll use stackoverflow and don't write it myself
Why do we need to resize by fixed size? I thought it’s always by doubling the previous size if needed, and then memcpy instead of doing elementwise assignment
Different use cases can benefit from different strategies for growing depending on factors such as:
- how constrained system/program memory is
- how often arrays are expected to grow
- how much arrays are expected to grow by
The exponential growth strategy also doesn't always need to be strictly double. Sometimes growing by only a factor of 1.2, 1.5, 3, 4, etc.
As for the memcpy point, not all data types are safe to straight up memcpy, at least in C++. memcpy also wouldn't really fit into the video, because the video is more about the conceptual idea behind dynamic arrays rather than implementation details.
@@mettaursp309 Extending by a fixed size, while I can probably come up with uses, is still SUPER niche. Doubling is indeed what is usually done.
And as explained in the video, using a fixed size doesn't help the scaling any. I suspect the follow-up video that was mentioned at the end, is going to explain how doubling is used.
As for memcpy and elementwise assignment... memcpy does nothing different. It's still just a loop copying over each word. That is assuming the assignment operator doesn't do anything crazy. I don't use C++, so it might well do that.
@@Yotanido I agree that the fixed amount increments has pretty limited use cases. I don't think I've ever personally run into a case where it would be the best option, but I've also only programmed for consumer grade PCs, not smaller devices like microprocessors.
For C++'s std::vector growth factor, it seems to not be defined in the standard so it's implementation dependent. A lot of the compilers do a factor of 2, but Microsoft being Microsoft chose 1.5 for at least one of their versions.
As for memcpy, yeah the relevant functions like assignment operator overload, copy constructor, move constructor, and so on can be changed to perform nontrivial operations.
I believe that std::vector will use the move constructor if available and compatible, otherwise it will use the copy constructor. I'm not sure if it falls back on memcpy if the class is a plain old data type though.
array list are good to search elements, but not efficient to restructure them. Linked list (or doubly linked list are better so as to add (append) new elements, but not so good to find elements. Every structure has its advantages and disadvantages.
Linked list as also the disadvantage of memory not being like an array and take a lot of time in that case
Linked lists can be kept in sorted order by using insertion sort when appending elements. Insertion sort is great for doubly linked lists because you can eliminate the bother of swapping each element between the unsorted element and its sorted place, just by rewiring some pointers.
On many computers, accessing many areas of memory that are close together can be much faster than accessing areas that are widely scattered. In the 1990s random accesses would often take between 100% and 300% as long as sequential accesses, but today that ratio has gone up by more than an order of magnitude. Even in cases where a linked-list approach would only use half as many total accesses as an array-list approach, performance may still be massively worse because all of its accesses would hit different rows of DRAM.
linked lists are horrible. period. doesnt matter wether they're forward linked, doubly linked or quadruple linked.
@@TheFlynCow Linked array-lists are useful for chain bucket hashing; I'm not sure what data structure would really be better for that purpose. Linear-probe hashing might offer better cache coherency, but at the expense of very bad behavior if hash table entries get clumped.
Okay pausing the video after the intro and taking a guess: using a hash table where each of the elements is stored at the hash of the index
Should the formula for the number of elements be N-4 rather than N+4 in the denominator?
Denominator or Numerator?
Don't you dare make me curious about langages that don't automatically store data
pannenkoek2012: _builds up speed for 12 hours_
Reductible (6:40): _copies elements from one array to another while adding new elements for 12 hours_
How do you make these videos. They are amazing and I want to teach people in a similar way
It looks like it was made using 3Blue1Brown's manim library
you deserve so many more subs than this.
Aren't fixed length array tuples?
Only in non-strictly typed languages. In strict languages such as Haskell or Rust, a tuple is a fixed length sequence that can contain mixed data types, i.e., you can do (i32, String) to have a two element tuple with a number and a string.
Arrays on the other hand must contain elements of the same type, mainly due to the fact that the size of each element must remain the same to be able to find elements. Also, it makes it really difficult to remember what is what in the array if you mix types.
link to the next vid?
where can I find the next video please?
If one needs huge array (i.e. large N), grow the array size with an exponentially increasing amount.
Loved the video ! Can you please share the code ?
Thanks for the comment! And yes, this is a great point. I added the a link to the code used to generate the animations in this video in the description.
Thank you and good luck.
"There's a lot of thought put into making this really efficient"
Java ArrayList: uses the solution around 4 minutes
(If you look at the actual code, you can see that's what it does. Who knows what kind of crazy optimization the JVM does, but the code itself is written that way)
EDIT: read the first reply, that's more accurate
can't say I'm surprised
i mean its using code from other classes
No. Java does not do this. The ArrayList.add method checks if there's enough capacity, and if not, it calls the ArrayList.grow method by indicating a MINIMUM GROWTH of 1 element. The call to grow will then delegate the calculation of the new size to the internal JDK method ArraysSupport.newLength with a preferred size of twice the length of the backing array. Then, the backing array is expanded with whatever newLength returns. This means that, most of the time, Java ArrayLists will grow by a factor of two once there's no more space.
Please don't spread this kind of rumor about Java. They're part of the reason it has an undeserved bad reputation.
@@maruseron Good to know, last time I read through the code was a looong time ago, so I probably forgot this part
Is manim shiped with this kinds of background song?
Why not allocate for n+1 elements but leave the last element to point to a memory address when you expand the array?
Why would you do that?
Arrays can be of different types (char, int , short or anything else), each lf those different types has a different size (1, 2, 4 or anything else) a pointer is always 4 or 8 bytes (depending on if youre running on 32 or 64 bit).
Not to mention it makes array access harder. Lets say i have an array of 3 items then append 3 more to it. Now lets say i want to get the 4th element of the array. With the standard implementation i can just array[3]. With ur implementation u fitst have to check if the element is in the original array, if not, do math and check if its in the next array, and so on. Also theres a 4/8 byte overhead for each time you append something. Also removing items becomes even trickier
@@c0smo709 on the first part you're right, but at least in c++ you can overload the [] operator for easy access. I made an implementation of it after I made this comment just to see how difficult it is. I'm pretty bad at c++ but I had pretty decent results (around a million appends + a collapse took 2.5 seconds iirc. It can definitely be optimized though.
It does make insert operations quite a bit faster though.
@@thedudeguy242 post the code and i will benchmark it with mine
So you can create array of pointers, each one points at different places of memory and each one contains address to array of 4 elements, and when you want some more space you just recreate array of pointers with one more cell, create new array for this pointer, and instead of copying each one number, you copy addresses to new array, and for arrays of 4 elements its 4 times faster, but you, at worst, dont use 3 elements
I’ve written a linked list before and I think the solution is similar right?
For a linked list, insertions are more efficient, because you don't have to copy every element to a new list like you do with an array. You just point the pointer of the tail of the list to your new element. They're particularly efficient for inserting elements in the middle of your list. With an array, you'd have to make your new sized array, copy all elements above that index but moved over by one, then copy the insertion, then copy the rest. With a linked list, you just have to reassign some values to some pointers.
The problem with linked lists is that to access any given element, you need to go through each element and follow the trail of pointers to get it, whereas for arrays, you can access any given element with no loss in efficiency; because array elements are stored contiguously in memory, the computer just has to add to a pointer to access them, as opposed to dereferencing a pointer, assigning it to the current node, then repeating until you find your element.
to be honest, I can't imagine putting myself into a situation where I'd have to invent a dynamic array, but if I ever find myself there, I'll be returning to this video
In my implementation I just scale the size by a growth factor every time it grows past capacity. By default the factor is 1.5 because having twice the space as is used seems wasteful. Would that be O(n log n) for the time? Anyway, another approach, if it's not required for the memory to be natively contiguous and your indexing operator can handle accessing an element, would be to use blocks, where you just allocate new blocks of a fixed size, and use the upper bits of the array index to select the block. This would also have to be scaled up at some point, and it might not be as cache friendly, but you avoid a lot of copying that way. Interested to hear there's a O(n) way of doing it. I think I'll look for that other video now. Good channel btw. :)
Oh, that is O(N), you put it nicely in the next one about dividing N into half repeatedly and adding. Technically 2N but we don't care about silly constants.
@@DFPercush Your growth factor is a common one. ArrayLists in Java and std::vector in C++ both use 1.5. Other languages like C# and Rust use a factor of 2.
They have the same time complexity, but the rationale behind using larger growth factors is that memory is usually pretty cheap, so it's better to reduce the amount of resize operations.
Going even deeper, a growth factor lower than 2 can be beneficial in languages that don't have managed memory. When a factor of 1.5 is used, the new larger array can fit into previously used blocks of memory. With a factor of 2, it will never fit. This is assuming that the previously used blocks are contiguous, which is often not the case in real world applications. Aforementioned managed languages complicate this even further, because they can shift things around in memory under the hood to reduce fragmentation.
@@DFPercush well technically it is O(N) big O notation just says it is something within a constant factor, so saying O(2N) is not technically correct:
If we get a 5th element we're Bruce Willis and we have to save the universe
int V[n]; goes brrrrr
I came here for the thing that he teased at the end wtf
3:35 First thing I do when I get a 5th Element is fast-forward to a scene with the pink-haired manic pixie dream girl, get the conditioner out of the shower and grab a few tissues.
Next video is here ; czcams.com/video/Ij7NQ-0mIVA/video.html&ab_channel=Reducible
3b1b of computer science
How lisp works ?
Just allocate lots of memory and assume unused part isn't actually allocated (Linux's victory, Windows always need pagefile)
But there are many loopholes in this explanation like why is it important for us to consider very large cases.
And I thought that dynamic arrays were trees under the hood.
9:05 in asm this feels very "rep movsd"-ey
if (allocated == length) {
allocated *= 2
data = malloc( allocated );
}
Dammit, I thought you were gonna explain why dynamic arrays are pointers. Or at the very least why we double array lengths instead of just adding k elements.
I would import system collections
Array == Stack in cpu?
Did somebody say "page tables"?
I'm not gonna hate on anyone whose first programming languages have built-in memory management and garbage collection. These are wonderful things! But it *is* really interesting to watch how these deep computer fundamentals are now getting taught to the generation who cut their teeth on python.
go Lang gives the same with name of Slice
i slept from video music 😑
conclusion: use a balanced binary tree
Why not just allocate a really big one and have a separate variable for the actual length
Because then youre wasting memory. Also whay if even the really big one is too small?
Why would you copy when you increase size though? From my time in C, I know you can request the system to resize an allocated block of memory (realloc and reallocarray).
realloc is just alloc + copy + dealloc, it just does the copy step for you.
@@API-Beast oh damn really? I guess that explains the performance... I might have to implement my own version now lol
@@matthewrease2376 The Standard would allow realloc() to, at its leisure, either adjust the size in place or create a new allocation and copy the data, but provides no means of distinguishing which of those an implementation actually did. It would be useful if there were a variation of realloc() which would ask to make an allocation as large as possible, up to a specified limit, without moving it or affecting the validity of pointers to it (the function would need to be passed the address of a size_t to receive the new size), but as it is the Standard doesn't even provide a means of knowing whether pointers to a re-allocated region would need to be recomputed.
You would not create an array with just one space. You might use pointers to achive the same thing. Intead of a next pointer you gave a privous pointer. That way you can go through the list O n. On the other hand a linkedlist seems more efficent but you do not get O 1 access to a linkedlist unlike any array. In genral if you want quick access arrays better then list.
Long ago, I was young and we didn‘t have dynamic arrays. I coded my own ones in C. And they sucked.
EDIT: just noticed this is a year old lol. It popped up in my recommended.
Are you using 3blue1brown's python library? I don't remember if he made it public. Not calling you a copycat, but I do get a similar vibe from your channels. Complex/stereotypically "nerdy" topics explained over calming music, with topic-relevant creatures discussing the material and thoughts viewers may have over a full black background where simple illustrations help work through the complexity.
Why is the music so sad. It's like you are telling us about the array that died before it could hold any data.
Link to next video: czcams.com/video/Ij7NQ-0mIVA/video.html
Array indexes usually start at zero.
When you said dynamic array i was hoping for my beloved array Placeholder.'variable'. =[]
And make a dynamic array, aka.
PlaceholderStore[], PlaceholderGarage[] and so on.
Why music is so sad like my life?
char* ptr0 = {'h', 'i'};
char* ptr1 = {' ', 'm'};
char* ptr2 = {'a', 'n'};
char** aptr = {*ptr0, *ptr1, *ptr2};
char** ptptptaotp = ***aptr;
if you double or triple the previous array the time becomes O(n) amortized!
The video doesn't awnser the question set in the title. It's was a complete waste of time for me.
Try doing it in BASIC, that was fun... not.
Or in C (scream!)
You talk incredibly slow. I had to play this in 2x to hear normal speed
I learned it as any good programmer would do. Copy paste from the internet lol
czcams.com/video/ryRf4Jh_YC0/video.html
Or
Just use python, or whatever language with a built-in dynamic array
Java lol