Оптимизировать рекурсию js

Question

Есть большой массив 70к объектов, нужно в соответствии массивом IDs, конечных узлов (1к элементов) вывести вложенный результирующий массив в виде дерева. Сделал через рекурсию, код отрабатывает ~8 сек. Пытался делать через цикл for + break не особо что-то изменилось, даже медленнее стало. Как ускорить?

const arr = [
  {
    CATEGORY_ID: 136,
    CATEGORY_PARENT_ID: null,
    CATEGORY_NAME: 'Двигатель'
  },
  {
    CATEGORY_ID: 137,
    CATEGORY_PARENT_ID: 136,
    CATEGORY_NAME: 'Двигатель в сборе'
  },
  {
    CATEGORY_ID: 138,
    CATEGORY_PARENT_ID: 137,
    CATEGORY_NAME: 'Прокладка двигателя'
  },
  {
    CATEGORY_ID: 139,
    CATEGORY_PARENT_ID: 137,
    CATEGORY_NAME: 'Подвеска двигателя'
  },
  {
    CATEGORY_ID: 140,
    CATEGORY_PARENT_ID: 136,
    CATEGORY_NAME: 'Основные элементы двигателя'
  },
  {
    CATEGORY_ID: 141,
    CATEGORY_PARENT_ID: 140,
    CATEGORY_NAME: 'Блок цилиндров и головка блока'
  },
  {
    CATEGORY_ID: 142,
    CATEGORY_PARENT_ID: 140,
    CATEGORY_NAME: 'Картер масляный и крышки блока'
  },
  {
    CATEGORY_ID: 143,
    CATEGORY_PARENT_ID: 140,
    CATEGORY_NAME: 'Вал коленчатый и маховик'
  },

  {
    CATEGORY_ID: 1136,
    CATEGORY_PARENT_ID: null,
    CATEGORY_NAME: 'Трансмиссия'
  },
  {
    CATEGORY_ID: 1137,
    CATEGORY_PARENT_ID: 1136,
    CATEGORY_NAME: 'Трансмиссионый блок'
  },
  {
    CATEGORY_ID: 1138,
    CATEGORY_PARENT_ID: 1137,
    CATEGORY_NAME: 'Шайба м8'
  },
]

const ids = [138, 140, 1138]


let result = [];

async function getTreeCategoriesByIds(ids) {

  function getPatch(ids) {
    arr.forEach(elem => {
      ids.forEach((id, index) => {
        if (elem.CATEGORY_ID === id) {
          result[index] = elem;
          if (elem.CATEGORY_PARENT_ID !== null) {
            recursive(elem.CATEGORY_PARENT_ID, index);
          }
        }
      });
    });
  }

  function recursive(parrentId, index) {
    arr.forEach(elem => {
      if (elem.CATEGORY_ID === parrentId) {
        result[index] = { ...elem, child: result[index] };
        if (elem.CATEGORY_PARENT_ID !== null) {
          recursive(elem.CATEGORY_PARENT_ID, index);
        }
      }
    });
  }
    getPatch(ids)

}

 getTreeCategoriesByIds(ids)

console.log( ...result );

Answer 1

Создал вспомогательный объект вида { CATEGORY_ID: obj, CATEGORY_ID: obj } для быстрого нахождения объектов по id.

Без рекурсии, в цикле находить родителей и вложить текущий объект в родителя, условие: while (CATEGORY_PARENT_ID)

const arr = [
  {
    CATEGORY_ID: 136,
    CATEGORY_PARENT_ID: null,
    CATEGORY_NAME: 'Двигатель'
  },
  {
    CATEGORY_ID: 137,
    CATEGORY_PARENT_ID: 136,
    CATEGORY_NAME: 'Двигатель в сборе'
  },
  {
    CATEGORY_ID: 138,
    CATEGORY_PARENT_ID: 137,
    CATEGORY_NAME: 'Прокладка двигателя'
  },
  {
    CATEGORY_ID: 139,
    CATEGORY_PARENT_ID: 137,
    CATEGORY_NAME: 'Подвеска двигателя'
  },
  {
    CATEGORY_ID: 140,
    CATEGORY_PARENT_ID: 136,
    CATEGORY_NAME: 'Основные элементы двигателя'
  },
  {
    CATEGORY_ID: 141,
    CATEGORY_PARENT_ID: 140,
    CATEGORY_NAME: 'Блок цилиндров и головка блока'
  },
  {
    CATEGORY_ID: 142,
    CATEGORY_PARENT_ID: 140,
    CATEGORY_NAME: 'Картер масляный и крышки блока'
  },
  {
    CATEGORY_ID: 143,
    CATEGORY_PARENT_ID: 140,
    CATEGORY_NAME: 'Вал коленчатый и маховик'
  },

  {
    CATEGORY_ID: 1136,
    CATEGORY_PARENT_ID: null,
    CATEGORY_NAME: 'Трансмиссия'
  },
  {
    CATEGORY_ID: 1137,
    CATEGORY_PARENT_ID: 1136,
    CATEGORY_NAME: 'Трансмиссионый блок'
  },
  {
    CATEGORY_ID: 1138,
    CATEGORY_PARENT_ID: 1137,
    CATEGORY_NAME: 'Шайба м8'
  },
]

/***/
let elements = {};

arr.forEach(obj => {
  elements[obj.CATEGORY_ID] = obj;
});

function getTreeCategoriesByIds(ids) {
  return ids.map(id => {
    let obj = { ...elements[id] };

    while (obj.CATEGORY_PARENT_ID) {
      obj = { ...elements[obj.CATEGORY_PARENT_ID], child: obj };
    }

    return obj;
  });
}

/***/
const ids = [138, 140, 1138];
let result = getTreeCategoriesByIds(ids);

console.log(...result);

Answer 2

Чтобы каждый раз не искать родителя/детей необходимо произвести подготовку массива и свернуть его в объект, где ключом является CATEGORY_ID, и значением сам объект. Это позволит находить объекты быстрее.

Далее достаточно будет функции, которая по конечному ID пройдет по всем PARENT_ID и построит искомый объект

выглядеть она может так:

function getPath(id, map) {
  var cur = map[id];
  while (cur.CATEGORY_PARENT_ID != null) { // если родитель NULL - дошли до верха и можно выходить
    cur = { ...map[cur.CATEGORY_PARENT_ID], // формируем объект
      child: cur
    };
  }
  return cur;
}

Конечный код может выглядеть так:

const arr = [{
    CATEGORY_ID: 136,
    CATEGORY_PARENT_ID: null,
    CATEGORY_NAME: 'Двигатель'
  },
  {
    CATEGORY_ID: 137,
    CATEGORY_PARENT_ID: 136,
    CATEGORY_NAME: 'Двигатель в сборе'
  },
  {
    CATEGORY_ID: 138,
    CATEGORY_PARENT_ID: 137,
    CATEGORY_NAME: 'Прокладка двигателя'
  },
  {
    CATEGORY_ID: 139,
    CATEGORY_PARENT_ID: 137,
    CATEGORY_NAME: 'Подвеска двигателя'
  },
  {
    CATEGORY_ID: 140,
    CATEGORY_PARENT_ID: 136,
    CATEGORY_NAME: 'Основные элементы двигателя'
  },
  {
    CATEGORY_ID: 141,
    CATEGORY_PARENT_ID: 140,
    CATEGORY_NAME: 'Блок цилиндров и головка блока'
  },
  {
    CATEGORY_ID: 142,
    CATEGORY_PARENT_ID: 140,
    CATEGORY_NAME: 'Картер масляный и крышки блока'
  },
  {
    CATEGORY_ID: 143,
    CATEGORY_PARENT_ID: 140,
    CATEGORY_NAME: 'Вал коленчатый и маховик'
  },

  {
    CATEGORY_ID: 1136,
    CATEGORY_PARENT_ID: null,
    CATEGORY_NAME: 'Трансмиссия'
  },
  {
    CATEGORY_ID: 1137,
    CATEGORY_PARENT_ID: 1136,
    CATEGORY_NAME: 'Трансмиссионый блок'
  },
  {
    CATEGORY_ID: 1138,
    CATEGORY_PARENT_ID: 1137,
    CATEGORY_NAME: 'Шайба м8'
  },
]

const ids = [138, 140, 1138]

function createMap(a) {
  return a.reduce((acc, cur) => {
    acc[cur.CATEGORY_ID] = cur;
    return acc;
  }, {});
}

function getPath(id, map) {
  var cur = map[id];
  while (cur.CATEGORY_PARENT_ID != null) {
    cur = { ...map[cur.CATEGORY_PARENT_ID],
      child: cur
    };
  }
  return cur;
}

const map = createMap(arr)

console.log(ids.map(i => getPath(i, map)));

Answer 3

Вариация с бинарным поиском (в предположении, что ваш массив таки отсортирован изначально по возрастанию id, а также, что искомые данные гарантированно в массиве есть).

По сравнению с прочими вариантами не требует лишней памяти для хранения словаря, не требует операций по перебору всего массива для построения этого самого словаря. получим наименьшее время работы, раз уж мы тут про оптимизацию говорим.

за основу взят соседний ответ @Grundy

const arr = [{CATEGORY_ID:136,CATEGORY_PARENT_ID:null,CATEGORY_NAME:'Двигатель'},{CATEGORY_ID:137,CATEGORY_PARENT_ID:136,CATEGORY_NAME:'Двигатель в сборе'},{CATEGORY_ID:138,CATEGORY_PARENT_ID:137,CATEGORY_NAME:'Прокладка двигателя'},{CATEGORY_ID:139,CATEGORY_PARENT_ID:137,CATEGORY_NAME:'Подвеска двигателя'},{CATEGORY_ID:140,CATEGORY_PARENT_ID:136,CATEGORY_NAME:'Основные элементы двигателя'},{CATEGORY_ID:141,CATEGORY_PARENT_ID:140,CATEGORY_NAME:'Блок цилиндров и головка блока'},{CATEGORY_ID:142,CATEGORY_PARENT_ID:140,CATEGORY_NAME:'Картер масляный и крышки блока'},{CATEGORY_ID:143,CATEGORY_PARENT_ID:140,CATEGORY_NAME:'Вал коленчатый и маховик'},{CATEGORY_ID:1136,CATEGORY_PARENT_ID:null,CATEGORY_NAME:'Трансмиссия'},{CATEGORY_ID:1137,CATEGORY_PARENT_ID:1136,CATEGORY_NAME:'Трансмиссионый блок'},{CATEGORY_ID:1138,CATEGORY_PARENT_ID:1137,CATEGORY_NAME:'Шайба м8'},];

const ids = [138, 140, 1138];

function search(a, id) {
  let s = 0, e = a.length - 1;
  
  while(true){  
    let m = Math.floor(s + (e-s)/2);        
    if (a[m].CATEGORY_ID == id) return a[m];    
    a[m].CATEGORY_ID > id ? e = m-1 : s = m+1;           
  }
}


function getPath(id) {
  var cur = search(arr, id);
  while (cur.CATEGORY_PARENT_ID != null) {
    cur = { ...search(arr, cur.CATEGORY_PARENT_ID),
      child: cur
    };
  }
  return cur;
}


console.log( ids.map(i => getPath(i)) );

Потенциально, если надо не просто найти пути для "трех" узлов, а постоянно дергать и искать разные, то сей поиск надо скрестить со словарем для "кэширования" уже найденных вариантов. Если же предполагается, что число вершин (с учетом родительских) будет одного порядка с размером самого массива, то тут проще сразу словарь использовать.

БЛОГ НА HUSL

Оптимизировать рекурсию js

Ответы (3 шт):