Best way in performance to split an array by the item's element value

Question

I have a very large array of something like this

var array = [
    { id: 1, category: 'Apple' },
    { id: 2, category: 'Orange' },
    { id: 3, category: 'Orange' },
    { id: 4, category: 'Grape' },
    { id: 5, category: 'Grape' },
]

I want to split the items up by the element's value to something like this

var newArray = [
    [
        { id: 1, category: 'Apple' },
    ],
    [
        { id: 2, category: 'Orange' },
        { id: 3, category: 'Orange' },
    ],
    [
        { id: 4, category: 'Grape' },
        { id: 5, category: 'Grape' },
    ],
]

This is what i currently use:

var array = [
    { id: 1, category: 'Apple' },
    { id: 2, category: 'Orange' },
    { id: 3, category: 'Orange' },
    { id: 4, category: 'Grape' },
    { id: 5, category: 'Grape' }
];
var categories = [];
array.forEach(function(item) {
    categories.push(item.category);
});
var uniqueCategories = categories.filter(function(item, pos) {
    return categories.indexOf(item) == pos;
});
var newArray = []
uniqueCategories.forEach(function(category, index) {
  array.forEach(function(item) {
    if (item.category === category) {
      if (!newArray[index]) {
        newArray[index] = [];
      }
      newArray[index].push(item);
    }
  });
});

But it is very slow when on large arrays of 1000 - 10000 items.

What is the best way to do it in performance?

Answer 1

Here is how I would do it. I would first reduce your array to a tree (an object), whose keys would be the categories. The insertion and access into the object should have a complexity of O(log n), however the JavaScript language spec does not mandate the time complexity of these functions.

From that tree, I would then iterate to get the values for each key and push them to an array.

const array = [
    { id: 1, category: 'Apple' },
    { id: 2, category: 'Orange' },
    { id: 3, category: 'Orange' },
    { id: 4, category: 'Grape' },
    { id: 5, category: 'Grape' },
];

const result = Object.values(array.reduce((accum, { id, category }) => {
  accum[category] = accum[category] || [];
  accum[category].push({ id, category });
  return accum;
}, {}));

console.log(result);