Как на javascript сделать древовидную структуру массива из массива из трёх полей id, name, parent?

Question

[Роман Ракзин]

Подскажите, если я имею массив подобного вида и на сервере хранится в подобной структуре

[
  id:1,name:"Text",parent:0,
  id:2,name: "Folder in Parent Folder with id 1", parent: 1,
  id:555, name: "Rekursive folder in Folder 2....", parent:2
]

Я бы хотел в списке отрисовать эти данные, полученные данные отрисовать из массива, где parent это родительский элемент.

[
 id:1, name:"Text",
 children: [
   id:2,name: "Folder in Parent Folder with id 1", 
   children: [
     id:555, name: "Rekursive folder in Folder 2...."
   ]
]

Как это преобразовать рекурсивно, так как неизвестен уровень вложений?

Comments

[mrvasilyevam]

Классный холивар за производительность

Вопрос как вывести полученную ветку дерева в плоский массив только id этой ветки типа [1, 345, 453, 456, 728] где элементы все дети одного родителя от которого началась данная ветка?

Answer 1

[Дмитрий]

Всего пару строчек кода, которые при желании можно и в одну соединить в ущерб наглядности

const map = Object.assign({} , ...arr.map(v => 
  ({ [v.id]: Object.assign(v, { children: [] }) })
))

const tree = Object.values(map).filter(v => 
 !(v.parent && map[v.parent].children.push(v))
)

Comments

[Somewhere Intech]

пятерка за производительность и кол за результат

[Дмитрий]

Спасибо, забыл скобку. Исправил. Теперь полная гармония результата и производительности.

[Дмитрий]

Bavashi, конечно неоднозначные, ведь у вас в тестируемых данных аж 8 элементов, кто ж на 8 элементах тесты проводит, должно быть максимум два, ну три на худой конец =)

[Дмитрий]

Bavashi, Не верьте этим тестам: сайт глючный, работает через раз и выдает разные результаты. На 1000 элементах мой код работает почти на порядок быстрее.
https://jsbench.me/4ekgqo7v99/1

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

[Дмитрий]

Bavashi вы можете дальше разбираться с сайтами и искать тот, где на тысяче ваши алгоритмы не сильно проигрывают, а по этой ссылке они проигрывают в два раза, но факт в том, что они замедляются в геометрической прогрессии по очевидным причинам. На benchmark на 10000 ваши вообще вылетают с ошибкой, опять же по очевидным причинам, странно что эти причины для вас неочевидны и вы продолжаете отстаивать свой совершенно бестолковый с точки зрения производительности код.

[Дмитрий]

Bavashi, Хорошо, раз с сайтами непонятки, предлагаю просто запустить одинаковый код в своих браузерах и выложить результаты, каждый сможет для себя сделать выводы. Вот код теста, просто скопируйте его в html-файлик, запустите в браузере и скопируйте результаты из консоли

Файл поочередно запустит тесты с размерностью 500 по 400 раз, затем 1000 по 200, 2000 по 100 и 5000 по 50

<button onclick="startTest()">Запустить тесты</button>

<script>
  const rnd = (min, max) => {
    let rand = min + Math.random() * (max + 1 - min)
    return Math.floor(rand)
  }

  const init = (len) => {
    const arr = [
      { id: 1, name: 'root', parent: 0 },
      { id: 2, name: '2', parent: 1 },
      { id: 3, name: '3', parent: 1 },
      { id: 4, name: '4', parent: 1 },
      { id: 5, name: '5', parent: 2 },
      { id: 6, name: '6', parent: 2 },
      { id: 7, name: '7', parent: 3 },
      { id: 8, name: '8', parent: 4 },
    ]

    for (let i = 8; i < len; i++) 
      arr.push({ id: i+1, name: i+" ...", parent: rnd(5, 8) })

    return arr
  }

  function test1( data ){
    const childs = id => 
      data.filter( item => item.parent === id )
        .map( 
          ({id,name}) => ({id,name, children: childs(id)}) 
        ).map(
          ({id,name,children}) => children.length ? {id,name, children} : { id, name }
        );
    return childs(0);
  }

  function test2( arr ) {
    const map = Object.assign({} , ...arr.map(v => 
      ({ [v.id]: Object.assign(v, { children: [] }) })
    ))

    const tree = Object.values(map).filter(v => 
    !(v.parent && map[v.parent].children.push(v))
    )
    
    return tree
  }

  function test3(array, parent) {
    var tree = {};
    parent = typeof parent !== 'undefined' ? parent : {id: 0};

    var childrenArr = array.filter(function(child) {
      return child.parent == parent.id;
    });

    if (childrenArr.length > 0) {
      var childrenObj = {};
      childrenArr.forEach(function(child) {
        childrenObj[child.id] = child;
      });
      if (parent.id == 0) {
        tree = childrenObj;
      } else {
        parent.children = childrenObj;
      }
      childrenArr.forEach(function(child) {
        test3(array, child);
      })
    }

    return tree;
  };

  function startTest () {
    const fns = [[test1, "@john36allTa"], [test2, "@dimoff66"], [test3, "@Bavashi"]]
    const counts = [[500, 400], [1000, 200], [2000, 100], [5000, 50]]

    counts.forEach(v => {
      const [len, cnt] = v
      console.log("Размер:" + len + ", повторить:" + cnt + " раз")
      
      const data = init(len)
      fns.forEach((v, ind) => {
        const [fn, name] = v

        console.time(name)
        for (let i = 0; i < cnt; i++) fn(data)
        console.timeEnd(name)

      })
      console.log("------------------------")
    })

    
  }
</script>

[Дмитрий]

Мои результаты на 3 браузерах

CHROME
Размер:500, повторить:400 раз
Johnny Lowhunter: 920.31591796875 ms
Дмитрий: 925.0927734375 ms
Bavashi: 514.877197265625 ms

Размер:1000, повторить:200 раз
Johnny Lowhunter: 1084.250244140625 ms
Дмитрий: 1118.38330078125 ms
Bavashi: 803.870849609375 ms

Размер:2000, повторить:100 раз
Johnny Lowhunter: 1955.033935546875 ms
Дмитрий: 693.781005859375 ms
Bavashi: 1630.515869140625 ms

Размер:5000, повторить:50 раз
Johnny Lowhunter: 6252.001953125 ms
Дмитрий: 707.797119140625 ms
Bavashi: 4837.2998046875 ms

OPERA
Размер:500, повторить:400 раз
Johnny Lowhunter: 564.421142578125 ms
Дмитрий: 707.365966796875 ms
Bavashi: 540.3291015625 ms
------------------------
Размер:1000, повторить:200 раз
Johnny Lowhunter: 848.5068359375 ms
Дмитрий: 1279.722900390625 ms
Bavashi: 854.94384765625 ms
------------------------
Размер:2000, повторить:100 раз
Johnny Lowhunter: 1697.964111328125 ms
Дмитрий: 731.470947265625 ms
Bavashi: 1728.457763671875 ms
------------------------
Размер:5000, повторить:50 раз
Johnny Lowhunter: 5129.18798828125 ms
Дмитрий: 704.139892578125 ms
Bavashi: 5192.26513671875 ms
------------------------

MICROSOFT EDGE
Размер:500, повторить:400 раз
Johnny Lowhunter: 1036.23193359375 ms
Дмитрий: 654.18408203125 ms
Bavashi: 506.59619140625 ms
------------------------
Размер:1000, повторить:200 раз
Johnny Lowhunter: 967.06787109375 ms
Дмитрий: 996.77392578125 ms
Bavashi: 847.37109375 ms
------------------------
Размер:2000, повторить:100 раз
Johnny Lowhunter: 1973.002197265625 ms
Дмитрий: 661.75 ms
Bavashi: 1551.324951171875 ms
------------------------
Размер:5000, повторить:50 раз
Johnny Lowhunter: 6122.143798828125 ms
Дмитрий: 666.64404296875 ms
Bavashi: 4720.76708984375 ms
------------------------

[Дмитрий]

Везде одна и та же картина: начиная с 2000 ваши алгоритмы начинают проигрывать в два и более раз и далее это отставание увеличивается в геометрической прогрессии.

[Somewhere Intech]

Дмитрий, да ладно Вам, я согласился сразу с тем что не производительно. Теперь пользователь тостера сможет выбрать решение под объем и даже организовать универсально оптимизированный класс ;)

[Дмитрий]

Johnny Lowhunter, Да я баваши пишу, просто тостер мои выкладки со статистикой как обращение к вам воспринял

[Дмитрий]

Bavashi, не на определённом, а на маленьком, где скорость вообще некритична, так как это меньше миллисекунды на одно выполнение. Там где скорость критична ваши решения не выдерживают никакой критики. И в отличие от вас у Johnny хватило ума просил с этим согласиться. Что выберет ТС мне все равно, мой пойнт показать, что подобная итерация в лоб не универсальна и замедляется в геометрической прогрессии.

Answer 2

[Somewhere Intech]

на скорую руку как то так можно

var rawData = [
  { id:1,name:"Root element",parent:0 },
  { id:2,name: "Child of the first element", parent: 1},
  { id:555, name: "Child of the second element", parent:2}
];


function pack( data ){
	const childs = id => 
		data.filter( item => item.parent === id )
			.map( 
				({id,name}) => ({id,name, children: childs(id)}) 
			).map(
				({id,name,children}) => children.length ? {id,name, children} : { id, name }
			);
	return childs(0);
}

console.log(JSON.stringify(pack(rawData)))

Comments

[Дмитрий]

По производительности твердый кол даже для скорой руки.

[Somewhere Intech]

Дмитрий, это да, Ваш вариант более производителен конечно

[Дмитрий]

Bavashi, Причём тут оптимизация map, когда для каждого id делается проход по всему массиву?

[Дмитрий]

Johnny Lowhunter, Вы не можете отсортировать массив по убыванию уровня вложенности, так как не знаете этот уровень.

Answer 3

[WbICHA]

Я так понимаю входные данные ─ это массив объектов с любыми ид?
Тогда можно так:
Создаёшь константу пустого массива, форичем проходишься по входным данным и по паренту пихаешь детей куда надо.
Всё.

Comments

[Роман Ракзин]

WbICHA а как организовать такой цикл?

[Alex]

Роман Ракзин, Тут подойдёт обычный for, а для хранения данных -- Map по id

Answer 4

[zealous]

пост старый - но интересный
вдруг кому пригодится
вот более быстрое решение чем у Дмитрий. в первом ответе
можно добавить в тесты из первого ответа от Дмитрий - будете приятно удивлены

function test4( list ) {
  var map = {}, node, roots = [], i;

  for (i = 0; i < list.length; i += 1) {
    map[list[i].id] = i; 
    list[i].children = []; 
  }

  for (i = 0; i < list.length; i += 1) {
    node = list[i];
    if (node.parent) {
      list[map[node.parent]].children.push(node);
    } else {
      roots.push(node);
    }
  }
  return roots;
}

вот тут добавлен этот вариант https://jsfiddle.net/zteogkuL/
------------------------
Размер:1000, повторить:100 раз
Somewhere Intech: 563.821044921875 ms
Bavashi: 614.713134765625 ms
Дмитрий: 241.9619140625 ms
--fast--: 3.85009765625 ms
------------------------
Размер:2000, повторить:50 раз
Somewhere Intech: 1106.697021484375 ms
Bavashi: 1223.849853515625 ms
Дмитрий: 154.4228515625 ms
--fast--: 3.881103515625 ms
------------------------
Размер:5000, повторить:20 раз
Somewhere Intech: 2736.092041015625 ms
Bavashi: 3024.505859375 ms
Дмитрий: 120.299072265625 ms
--fast--: 4.150146484375 ms
------------------------