Подсчет (дочерние) элементы в массивах

Question

У меня есть массив объектов. Каждый объект выглядит следующим образом:

{text: 'foo': level: N: children: M} 

Оба N и M являются числами. N представляет, как «глубоко» находится объект (подумайте обо всем массиве, как будто это было представление дерева). M - общее количество детей, которые имеют данный предмет. Всего означает сумму всех узлов и листов всех подуровней.

Объекты в массиве, которые у меня отсутствуют, не содержат свойства children, и я должен его вычислить.

Пример «вычисленные» данные:

{text: 'A': level: 0: children: 0} 
{text: 'B': level: 0: children: 1} 
{text: 'C': level: 1: children: 0} 
{text: 'D': level: 0: children: 2} 
{text: 'E': level: 1: children: 1} 
{text: 'F': level: 2: children: 0} 

A 
B 
|--C 
D 
|--E 
    |--F 

я мог бы легко сделать for петли, а затем итерацию еще раз над элементами, начиная с текущей позицией в массиве и сосчитать ребенок (на основе на уровне свойства), но я чувствую, что это не лучший (как в «самом быстром») способе сделать это.

Как еще я мог это сделать?

Просто чтобы убедиться, что никто сообщения «хуже» кода, чем то, что я в настоящее время, это то, что у меня есть:

for (var i = 0; i < data.length; i++) { 
    var item = data[i]; 

    for (var j = i + 1; j < data.length; j++) { 
     if (item.level < data[j].level) { 
      item.children++; 
     } else { 
      break; 
     } 
    } 
} 

Answer 1

В текущем примере вы не вычислить детей вообще, потому что ваша данные не показывают отношения родителей/детей. level:1 для text: 'C', например, не имеют данных, если они должны быть прикреплены (т. Е. Увеличить счетчик children) до A, B или D.

Если вы имеете в виду, но забыл упомянуть, что дочерний объект должен быть привязан к тому, кто недавно был упомянут ближайший родитель, просто сохраните массив, где каждая запись будет соответствовать ссылке на последний вид родительского элемента этого уровня и изменить его chlildren Недвижимость с += непосредственно после прочтения каждой новой строки.

Answer 2

Единственный способ, который я могу сделать для этого без цикла for, потребует от вас реформирования вашей древовидной структуры. объекты JavaScript могут быть вложенными, и поэтому я предложил бы использовать формат, такие как:

[ 
    { 
     text: 'A', 
     children: [] 
    }, 
    { 
     text: 'B', 
     children: 
     [ 
      { 
       text: 'C', 
       children: [] 
      } 
     ] 
    }, 
    { 
     text: 'D', 
     children: 
     [ 
      { 
       text: 'E', 
       children: 
       [ 
        { 
         text: 'F', 
         children: [] 
        } 
       ] 
      } 
     ] 
    } 
] 

Тогда для каждого объекта, формула для «общего количества детей» было бы что-то вроде:

function countChildren(obj) { 
    var count = obj.children.length; 
    for (int i = 0; i < children.length; i++) { 
     count += countChildren(children[i]); 
    } 
    return count; 
} 

Answer 3

Это ответ, который, как мне кажется, сказал О. Вольков в своем комментарии. Я думаю, что это очень хорошее решение проблемы & очень быстро, так как вы смотрите только на каждый элемент 1 раз. Тем не менее, нижняя сторона заключается в том, что она может быть более интенсивной в памяти, в то время как она вычисляется из-за множества родителей.

function countChildren(tree) { 
    var currentParents = []; 

    for (var i = 0; i < tree.length; i++) { 
     // Initialize value of children 
     tree[i].children = 0; 

     if (i == 0) { 
      continue; 
     } 

     // Find if the level increased, decreased, or stayed the same. 
     var levelChange = tree[i].level - tree[i-1].level; 

     // If level increased (by 1) 
     if (levelChange == 1) { 
      // Add previous element to list of parents 
      currentParents.push(tree[i-1]); 

     // If level decreased by 'x' 
     } else if (levelChange < 0) { 
      // Remove 'x' number of elements from the end of the list of parents 
      for (var j = 0; j > levelChange; j--) { 
       currentParents.pop(); 
      } 
     } 

     // Increase the number of children for all parents 
     for (var j = 0; j < currentParents.length; j++) { 
      currentParents[j].children++; 
     } 
    } 
} 

Answer 4

Это другой подход, despide все другие решения, начиная со дна.

Преимущество заключается в том, что всякий раз, когда достигается меньший уровень, сумма берется, а фактический аккумулятор уровня устанавливается на ноль.

Это решение имеет только один цикл и массив count для накопления уровня.

Я сделал большую проверку с этими данными (за исключением свойства children, которое является результатом алгоритма).

{ text: 'A', level: 0, children: 0 }, // A 
{ text: 'B', level: 0, children: 1 }, // B 
{ text: 'C', level: 1, children: 0 }, // C 
{ text: 'D', level: 0, children: 3 }, // D 
{ text: 'E', level: 1, children: 2 }, // E 
{ text: 'F', level: 2, children: 0 }, //  F 
{ text: 'F', level: 2, children: 0 }, //  G 
{ text: 'H', level: 0, children: 18 }, // H 
{ text: 'I', level: 1, children: 5 }, // I 
{ text: 'J', level: 2, children: 1 }, //  J 
{ text: 'K', level: 3, children: 0 }, //  K 
{ text: 'L', level: 2, children: 2 }, //  L 
{ text: 'M', level: 3, children: 1 }, //  M 
{ text: 'N', level: 4, children: 0 }, //   N 
{ text: 'O', level: 1, children: 10 }, // O 
{ text: 'P', level: 2, children: 9 }, //  P 
{ text: 'Q', level: 3, children: 7 }, //  Q 
{ text: 'R', level: 4, children: 5 }, //   R 
{ text: 'S', level: 5, children: 2 }, //   S 
{ text: 'T', level: 6, children: 0 }, //    T 
{ text: 'U', level: 6, children: 0 }, //    U 
{ text: 'V', level: 5, children: 0 }, //   V 
{ text: 'W', level: 5, children: 0 }, //   W 
{ text: 'X', level: 4, children: 0 }, //   X 
{ text: 'Y', level: 3, children: 0 }, //  Y 
{ text: 'Z', level: 1, children: 0 }, // Z 

var data = [{ text: 'A', level: 0 }, { text: 'B', level: 0 }, { text: 'C', level: 1 }, { text: 'D', level: 0 }, { text: 'E', level: 1 }, { text: 'F', level: 2 }, { text: 'F',level: 2 }, { text: 'H', level: 0 }, { text: 'I', level: 1 }, { text: 'J', level: 2 }, { text: 'K', level: 3 }, { text: 'L', level: 2 }, { text: 'M', level: 3 }, { text:'N', level: 4 }, { text: 'O', level: 1 }, { text: 'P', level: 2 }, { text: 'Q', level: 3 }, { text: 'R', level: 4 }, { text: 'S', level: 5 }, { text: 'T', level: 6 }, {text: 'U', level: 6 }, { text: 'V', level: 5 }, { text: 'W', level: 5 }, { text: 'X', level: 4 }, { text: 'Y', level: 3 }, { text: 'Z', level: 1 }], 
 
    i = data.length, 
 
    count = []; 
 
\t 
 
while (i--) { 
 
    if (data[i].level > 0) { 
 
     count[data[i].level - 1] = (count[data[i].level - 1] || 0) + (count[data[i].level] || 0) + 1; 
 
    } 
 
    data[i].children = count[data[i].level] || 0; 
 
    count[data[i].level] = 0; 
 
} 
 

 
document.write('<pre>' + JSON.stringify(data, 0, 4) + '</pre>');

Версия с укажи массива count (без каких-либо проверок на неопределенный) и переменной для уровня.

var data = [{ text: 'A', level: 0 }, { text: 'B', level: 0 }, { text: 'C', level: 1 }, { text: 'D', level: 0 }, { text: 'E', level: 1 }, { text: 'F', level: 2 }, { text: 'F',level: 2 }, { text: 'H', level: 0 }, { text: 'I', level: 1 }, { text: 'J', level: 2 }, { text: 'K', level: 3 }, { text: 'L', level: 2 }, { text: 'M', level: 3 }, { text:'N', level: 4 }, { text: 'O', level: 1 }, { text: 'P', level: 2 }, { text: 'Q', level: 3 }, { text: 'R', level: 4 }, { text: 'S', level: 5 }, { text: 'T', level: 6 }, {text: 'U', level: 6 }, { text: 'V', level: 5 }, { text: 'W', level: 5 }, { text: 'X', level: 4 }, { text: 'Y', level: 3 }, { text: 'Z', level: 1 }], 
 
    i = data.length, l, 
 
    count = Array.apply(null, { length: 50 }).map(function() { return 0; }); 
 
\t 
 
while (i--) { 
 
    l = data[i].level; 
 
    if (l) { 
 
     count[l - 1] += count[l] + 1; 
 
    } 
 
    data[i].children = count[l]; 
 
    count[l] = 0; 
 
} 
 

 
document.write('<pre>' + JSON.stringify(data, 0, 4) + '</pre>');