loading...

re: Not an "Easy" Algorithm: Rotating an Array, Three Ways VIEW POST

TOP OF THREAD FULL DISCUSSION
re: After reading the problem, just on top of my head, this can be easily solved with a ring buffer. Best of all, it can be implemented in any language.
 

A good point, one of those if you knew the actual problem you'd find a way of solving it better than actually manipulating an array which feels "expensive".

 

I feel exactly there opposite on this. Using built in methods to manipulate an array (slice in my case) feels less expensive to me because I expect the engineers working on the browser build optimizations into their implementations of these methods.
Not looking to argue it just throwing another perspective in there.

I guess my point was that the array is a specific data structure, I expect it to be optimised for being an array. If my problem is something that includes a "rotation" then a rolling buffer may well be a better algorithm - requires no shifting, just a very slightly more complicated retrieve operation and then move a head and tail pointer.

For example: if you are constantly inserting all over a list and only rarely retrieving all the items then no contiguous array, no matter how optimised, will be anywhere near the performance of a linked list.

If I want to implement a thing that has the last 100 values in it then shifting an array for every insertion is massively more costly than increment and modulus. Getting a new array with slice is allocating memory every time. It's easy to write the code, but the consequences may be significant under load.

Totally agree with your linked list example, and your argument about multiple shifts getting expensive quickly.
I am curious though, do you think creating a new data structure from the original array is going to use less memory than the slice solution? Probably would have to dig into the source to be sure, but curious about your intuition here.

It's probably the game programmer in me coming out. Don't allocate things because something has to garbage collect them later. That takes time, causes glitches etc.

I wrote the below a while ago about this. It really doesn't matter if you are sure the code isn't going to work on giant data or be called frequently. If that is the case then my "dont allocate/copy/garbage collect" OCD kicks in :)

Nice article. It's actually something I've given little though to. Thanks for sharing, I'm sure I'll think of it in the future now.

Glad you like it :) Honestly only do that when it matters though - I mean I write code that uses all of the slow things when I know it will not be handling lots of data because it's quicker to write and that is the important thing for the task at hand!

Specifically on your point of immutability, a lot of frameworks in many languages implement collections like this. I usually just use them without even thinking about the memory issues. Your example in the article is very eye opening!

Yeah immer.js allows you to mutate arrays and then it works out an immutable version from it. That's very cool, but still has a cost as I replied in the comments to that article with a sandbox example showing (on my machine at least) significant frame drops in some use cases.

It so happened the example I had given and then implemented in immer is a kind of kryptonite to immer.js (because it happens over multiple cycles) but yeah, I see things on DEV all the time that use spread in loops - I just think, hope no one calls that example with 1 million entries not the example 10!

code of conduct - report abuse