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.
@StefanReich2 жыл бұрын
Yeah it was a great talk. Even Java oldtimers like me learned a few things here
@chinmayachowdary7 жыл бұрын
Wow! Excellent.
@aprasath12 ай бұрын
Thanks for posting this is very nice.
@heinzkabutz5 жыл бұрын
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.
@AndrewKay6 жыл бұрын
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.
@NovaCyn6 жыл бұрын
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
@jonaskoelker3 жыл бұрын
> 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.)
@StefanReich2 жыл бұрын
@@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
@NovaCyn2 жыл бұрын
@@StefanReich You can actually set the growth size, so that's something. But yes that's still O(n^2) to add n elements
@dhawaljoshi Жыл бұрын
really interesting insights
@SprockPls4 жыл бұрын
I love this guy, He's pretty funny XD
@almazglaz5 жыл бұрын
toArray example with more details is explained here: shipilev.net/blog/2016/arrays-wisdom-ancients/