array.md

Usecase

• There are too many items.
  • e.g. log output
  • It migght be more than million.
• Need to store latest 1000 items.

Solution

We can implement with simple array

var store = [];
var MAX = 1000;

function push(item) {
  if (store.length >= MAX) {
    store.shift();
  }
  store.push(item);
}

Problem

What is problem of this solution?

• Array#shift is slow
  • because it needs buffer copy every time.
• LinkedList is an alternative

Any other solution?

Circular buffer

https://en.wikipedia.org/wiki/Circular_buffer

• It can be implemented with array.
• The cost of push/pop/shift/unshift are same.

implementation

https://github.com/trevnorris/cbuffer

Demo

https://shunjikonishi.github.io/cbuffer-test/

P.S. On nodejs v4.4.4: CBuffer's perfomance is about 80%

Conclusion

• Circular buffer is effective data structure when you want fixed size array.
• Array#shift of Firefox is too slow