Performance talks like this rarely disappoint. Some might call it trivia, but it's nice to understand what's going on behind the scenes, especially when optimising performance.
By default Vector doubles the number of elements when you run out of space. We can override that behaviour by constructing it with a capacityIncrement, but hardly anyone ever does that.
At 37:10, the claim about O(n log n) is wrong - exponential resizing really does take only O(n) operations to build a collection of n items. If the scale factor is 2, for example, then the total number of copies is up to n + n/2 + n/4 + ... + 2 + 1. This is a geometric sequence with a sum of 2n - 1, which is O(n). The same is true for any other scale factor.
He's talking about vector. vector as he said a few seconds before does NOT scale exponentially (with a factor) What you say is true of all the OTHER collections
> exponential resizing really does take only O(n) [...] [n + n/2 + ... + 1 = an + b which is in O(n)] I'd like to restate this in plain terms. The speaker did say something right: there is a copy every log n iterations*. However: most of those copies are a lot smaller than the size of the final array. That's why it's O(n) and not O(n log n). (* approximately. If the starting size is 10 rather than 1, the first few copy operations can be skipped. So it's (log n) - (log 10) or something. Still O(log n) though.)
@@NovaCyn My God it's true - it grows by 1 every time another element is added! So adding n elements takes O(n^2). That makes Vector pretty much unusable... but thankfully no one is using it anymore anyway
Performance talks like this rarely disappoint. Some might call it trivia, but it's nice to understand what's going on behind the scenes, especially when optimising performance.
Yeah it was a great talk. Even Java oldtimers like me learned a few things here
By default Vector doubles the number of elements when you run out of space. We can override that behaviour by constructing it with a capacityIncrement, but hardly anyone ever does that.
Wow! Excellent.
really interesting insights
At 37:10, the claim about O(n log n) is wrong - exponential resizing really does take only O(n) operations to build a collection of n items.
If the scale factor is 2, for example, then the total number of copies is up to n + n/2 + n/4 + ... + 2 + 1. This is a geometric sequence with a sum of 2n - 1, which is O(n). The same is true for any other scale factor.
He's talking about vector. vector as he said a few seconds before does NOT scale exponentially (with a factor) What you say is true of all the OTHER collections
> exponential resizing really does take only O(n) [...] [n + n/2 + ... + 1 = an + b which is in O(n)]
I'd like to restate this in plain terms. The speaker did say something right: there is a copy every log n iterations*. However: most of those copies are a lot smaller than the size of the final array. That's why it's O(n) and not O(n log n).
(* approximately. If the starting size is 10 rather than 1, the first few copy operations can be skipped. So it's (log n) - (log 10) or something. Still O(log n) though.)
@@NovaCyn My God it's true - it grows by 1 every time another element is added! So adding n elements takes O(n^2). That makes Vector pretty much unusable... but thankfully no one is using it anymore anyway
@@StefanReich You can actually set the growth size, so that's something. But yes that's still O(n^2) to add n elements
I love this guy, He's pretty funny XD
toArray example with more details is explained here: shipilev.net/blog/2016/arrays-wisdom-ancients/