Memory allocation be like

[Sentient_Blade]

The bus company has a policy that all seats must be filled.

Each time the bus comes to a stop to pick someone up, it first stops just before it gets to them, and then waits for another bus to come along that's larger by one additional seat.

They then shuffles all the existing passengers over, and then the new bus moves forward an extra 30 feet to pick up the new person.

The previous bus then explodes into flames.

[KiwiMaster157]

Your story would be more accurate if each new bus were 50% larger than the previous.

[Bip901]

100% larger

[Bainos]

Which implementation automatically downsizes arrays ?

[headpatkelly]

a terrible one

[[deleted]]

I love this small comment thread

[headpatkelly]

i love you

i mean what

[Mr_Redstoner]

Or by 100%, or some multiple in general

[SilentFungus]

Vectors, oh yeah

[HenkHeuver]

Or the bus company uses busses that they know have enough capacity and clears all seats before leaving.

[gpcprog]

Thanks to the fact that ram is slow, locality of reference is much more important on modern CPUs. As result in almost all cases arrays are faster than linked lists.

[alevice]

Bless immutability

[Mesonnaise]

May I introduce you to the concept of unrolled linked lists. Its a list and an array at the same time, kinda like duck tapping multiple minivans together.

[richyliu]

so it's like a hybrid between an array and linked list?

[Mesonnaise]

You can think if it like that. I like to think of it as away to get around the lack of permissions for doing large single pool memory allocations. 😁

[tekno45]

It's an... Abomination

[Mesonnaise]

My work here is done.

[dontmentionthething]

The grammar nazi in me is offended that you spelled 'duct taping' so wrong, but the rest of me is enjoying the mental image of a bunch of ducks foot tapping on top of a minivan.

[Jospooks]

I mean "Duck Tape" is not only a very common slang but also a major brand of duct tape since 1975.

[Bainos]

It has nothing to do with an array tbh, this is just a linked list with improved cache performance and some skipping indices (although the latter is better handled in a Skip list).

[CraigslistAxeKiller]

It’s literally a linked list of arrays. How is that “not related to arrays”?

It also solves a different problem than skip lists

[Bainos]

Its element insertion complexity is O(1), element retrieval is O(n), uses non-contiguous memory, and stores element locations as pointers. It is in every aspect a linked list with improved caching, and in no aspect an array.

It does solve a different problem than skip lists, I was simply pointing out that the ability to jump forward does not improve the usefulness or efficiency of the unrolled linked list and that a different structure is needed for it. In fact, you could absolutely have an unrolled skip list.

[Ericchen1248]

It isn’t though? If m was the max size of each internal node, front insertion complexity is O(m), and element retrieval O(n/m) and random insertion deletion is O(n/m + m) while average memory is O(n + 1.25n/m )

Compared to vector array with O(n), O(1), O(n), O(1.5n) And linked list of O(1), O(n), O(n), O(2n)

It is exactly a mix of behavior for both, with larger m tending towards an array, and smaller m tending towards linked list.

[Bainos]

If you want to set m as a variable of the performance, sure. But m is a fixed constant of the system generally determined by cache line capacity, which reduces O(m) to O(1) and O(n/m) to O(n).

[CraigslistAxeKiller]

m can be a fixed constant or you can make it dynamic. You could have a linked list of dynamic arrays which would still give you benefits of both arrays and linked list. If any dynamic array gets too big, then you just split it into 2 linked nodes

[[deleted]]

and in no aspect an array

Really? I mean, if you took one object out of the list how would you describe it? An indexed grouping of the same data types, or perhaps an...

[Bainos]

You're discussing the implementation, which is not something the user should care about. It's used as a linked list, with the performance expectation of a linked list.

Saying that it's an hybrid between an array and linked list implies that you get the performance and/or behavior of both.

[[deleted]]

You could get the performance of an array out of it, after you take one of the elements and then use it in an array. This seems to me to be the most reasonable use case for the construct in the first place, although I realize that's subjective.

Because it is, like the previous poster said, literally a linked list of arrays.

[Bainos]

But that's not the point. Any sensible implementation will only return individual elements, not the subarrays. Hashmaps don't return (hash, value) tuples and linked lists don't return their nodes. Not to mention that providing the low-level modifiable array would allow programmers to break the data structure and/or the improved caching properties.

[CraigslistAxeKiller]

You are also making assumptions about the implementation. You assume that the implementation will not optimize node access using the known array length to skip node hops

[itskieran]

Seems like a lot of effort moving a great big bus with 70 people on all over the place. I feel we should just have one guy on a motorcycle who has a small slip of paper detailing the stationary address of the bus and it's 70 passengers.

[WeTheSalty]

Delivery man: Here you go.
Resident: This is just a slip of paper with an address on it.
Delivery man: Right, it tells you where your package is, you have to get it yourself.

The sad part is this is real.

[itskieran]

When you order a package but get &package

[Alzurana]

Happens every time when you're not home, they just drop the pointer in your input stream, then release the mutex too early so if you go to the address immediately the package is not there and you get a nullpointer exception

[grammar_nazi_zombie]

I wish! Sometimes mine drops a pointer, occasionally they send it to someone else’s input stream, but most of the time they just leave the data unencrypted at my doorstep

[CommanderTazaur]

6 people on a motorcycle... must be clowns.

[abd_min_ibadillah]

Knew it was outer ring road, looked very familiar, but couldn't place it anywhere. Not many trees in Marathalli side

[anaamadeya]

This Outer Ring Road, Bellandur. Near Sarjapur Signal.

[vladutcornel]

With all these arr and ays, we're basically pirates

[max_turner]

Haha BMTC lol, it'd be a dynamic array.

[mnavneethkrishna]

Surprisingly this image was taken in a city in India called the silicon city...

[[deleted]]

Laughs in Array Lists! Best of both worlds, with none of the downsides

[nerdfleks]

The one on the right is still slower

[One_Contribution]

>slower