无限层级目录算法

设计 1

核心字段

ColumnDesc
oid组织 id
name组织名称
parentoid上级组织 id
rootoid根组织 id

测试数据, 一个复杂组织目录(根据 oid = 47378 查出):

test1.json

树形结构生成

期望结果:

tree1.json

递归方法:

// 将测试数据保存
const orgs = require('./test1.json');

// 递归
const loop = (list, oid, isRoot = true) => {
  const c = list
    .filter((x) => oid === (isRoot ? x.oid : x.parentoid))
    .map((x) => {
      // 问题1: 每次都将数组完整传入遍历
      x.children = loop(list, x.oid, false);
      return x;
    });
  // 问题2: 循环次数最多 n^n 次
  return c;
};

console.log(JSON.stringify(loop(orgs, 47378), null, 2));

设计 2

核心字段

ColumnDesc
oid组织 id
name组织名称
parentoid上级组织 id
rootoid根组织 id
depth层级深度

测试数据, 一个复杂组织目录(根据 oid = 47378 查出):

test2.json

树形结构生成

期望结果:

tree2.json

循环算法:

// 将测试数据保存
const orgs = require('./test2.json');

const loop = (list) => {
  const sorted = list.sort((x, y) => (x.depth < y.depth ? 1 : -1));
  // 计算深度
  const depth = sorted[0].depth;
  const items = {};
  // 分级遍历, 问题1: 空间复杂度
  for (let i = 1; i <= depth; i += 1) {
    items[i] = list.filter((x) => x.depth === i);
  }
  // 循环自下而上遍历
  for (let i = depth; i > 1; i -= 1) {
    items[i] = items[i].forEach((x) => {
      const parentNode = items[i - 1].findIndex((y) => y.oid === x.parentoid);
      items[i - 1][parentNode].children = (items[i - 1][parentNode].children || []).concat(x);
    });
  }
  // 循环次数: CN(Depth)
  return items[1];
};

console.log(JSON.stringify(loop(orgs), null, 2));

BenchMark

使用matcha进行性能测试

suite('Categories', function () {
  bench('test 1', function () {
    loop1(orgs1, 47378);
  });
  bench('test 2', function () {
    loop2(orgs2);
  });
});
                     Categories
           2,620 op/s » test 1
             531 op/s » test 2
在 GitHub 上编辑本页面 更新时间: Mon, Apr 10, 2023