Javascript: efficiently moving elements to and from a fixed-size array

Question

If I have an array that I want to have a fixed size of N to cache the last of N elements, then after reaching the limit of N, I have to get rid of the oldest one when adding a new element.

Note. I don’t care if the new element is at the beginning or end of the array until the elements are deleted in the order in which they are added.

The obvious ways are:

• push() and shift() (so cache[0] contains the oldest element) or
• unshift() and pop() (so cache[0] contains a new element)

Main idea:

 var cache = [], limit = 10000; function cacheItem( item ) { // In case we want to do anything with the oldest item // before it gone forever. var oldest = []; cache.push( item ); // Use WHILE and >= instead of just IF in case the cache // was altered by more than one item at some point. while ( cache.length >= limit ) { oldest.push( cache.shift() ); } return oldest; } 

However, I read about memory issues with shift and unshift , as they change the beginning of the array and move everything else, but unfortunately one of these methods should be used this way

Qs:

• Are there other ways to do this to improve performance?
• If the two ways that I already mentioned are the best, are there specific advantages / disadvantages that I should be aware of?

Conclusion

After several studies in data structures (I never programmed in other languages, so if it is not native to Javascript, I probably have not heard about it!) And performed a bunch of benchmarking in several browsers with both small and large arrays, and also a small and large number of reads / records, here is what I found:

• The round buffer method proposed by Bergi is the best work (for reasons explained in the answers and comments), and therefore it was accepted as the answer. However, this is not as intuitive and makes it difficult to write your own "extra" functions (since you always need to consider offset ). If you intend to use this method, I recommend one already created, for example, this circular buffer on GitHub .
• The "pop / unpush" method is much more intuitive and works quite well, accept the most extreme numbers.
• The copyWithin method, unfortunately, is terrible for performance (tested in several browsers), quickly creating an unacceptable delay. It also does not support IE. This is such a simple method! I would like it to work better.
• The linked list method suggested in Felix Kling's comments is actually a really good option. I initially ignored this, because it seemed to me that there were so many superfluous things, but, to my surprise, ...

I really needed the Latest Used (LRU) map (which uses a doubly linked list). Now, since I have not clarified my additional requirements in my original question, I still mark Bergi's answer as the best answer to this particular question. However, since I needed to know if the value was already in my cache, and if so, mark it as the newest item in the cache, additional logic that I have to add to my circular buffer method add() (primarily indexOf() ) made it not much more efficient than the pop / unpush method. HOWEVER, LRUMap's performance in these situations blew two others out of the water!

So, we summarize:

• Linked list - most options while maintaining excellent performance
• The circular buffer is the best performance for simply adding and receiving
• Pop / Unpush - the most intuitive and simplest
• copyWithin - horrible performance at the moment, no reason to use

Answer 1

If I have an array that caches the latest of N elements as soon as it reaches the limit of N, I will have to get rid of the oldest by adding the newest.

You are not going to copy the material inside the array, which will execute O(n) each time.

Instead, it is ideal for a ring buffer . Just save the offset "start" and "end" in the list, then get access to the buffer with this offset and modulo its length.

 var cache = new Array(10000); cache.offset = 0; function cacheItem(item) { cache[cache.offset++] = item; cache.offset %= cache.length; } function cacheGet(i) { // backwards, 0 is most recent return cache[(cache.offset - 1 - i + cache.length) % cache.length]; } 

Answer 2

You can use Array#copyWithin .

The copyWithin() method shallowly copies part of an array to another location in the same array and returns it without changing its size.

Description

copyWithin works like C and C ++ memmove and is a high-performance method for transferring Array data. This is especially true for the TypedArray method with the same name. The sequence is copied and pasted as one operation; the inserted sequence will have the copied values, even if the copy and paste area overlaps.

The copyWithin function copyWithin intentionally generic; it does not require its value to be Array .

The copyWithin method is a mutable method. It does not change the length of this , but will change its contents and, if necessary, create new properties.

 var array = [0, 1, 2, 3, 4, 5]; array.copyWithin(0, 1); console.log(array); 

Answer 3

You need to splice existing element and put it in front using unshift (like a new element). If an item does not already exist in your cache, you can unshift and pop .

 function cacheItem( item ) { var index = cache.indexOf( item ); index != -1 ? cache.splice( index, 1 ) : cache.pop(); cache.unshift( item ); } 

Element

must be String or Number , otherwise you will need to write your own implementation of indexOf using findIndex for the search and the object (if the element is an object).