从 objects 的普通数组构建嵌套数据树

Question

我有一个 objects 数组，比如那些：

{
  "short_id": "2p45q",
  "path": "/",
  "name": {
    "en-US": "IndustrialDesign"
  }
}

...

{
  "short_id": "2q56r",
  "path": "/2p45q/",
  "name": {
    "en-US": "Automotive"
  }
}

我必须遍历数组的每个元素并检查 path，然后找到元素的 parent 并将其推入新的parent 的数组属性称为 sub。每个 child 可以有自己的 sub 属性，因此是更多 children 的 parent。最终结果（对于此示例）如下所示：

{
  "short_id": "2p45q",
  "path": "/",
  "name": {
    "en-US": "Test A"
  },
  "sub": [
    {
      "short_id": "2q56r",
      "path": "/2p45q/",
      "name": {
        "en-US": "Test A.1"
      }
    }
  ]
}

我有一个工作代码（使用 this jsonpath lib）：

function(categories) {
    var _categories = [];

    angular.forEach(angular.copy(categories), function(_category) {
        if (_category.path === "/") {
            _categories.push(_category);
        } else {
            var _path = _category.path.split("/");
            _path.pop();
            var _parent = _path.pop();

            jsonpath.apply(_categories, "$..[?(@.short_id=='" + _parent + "')]", function(obj) {
                if(!obj.hasOwnProperty("sub")) {
                    obj.sub = [];
                }
                obj.sub.push(_category);
                return obj;
            });
        }
    });

    return _categories;
}

但是性能真的很差，主要是因为我每次迭代都要查询整个数组。

我的问题是如何优化我的代码？

备注：

每个 short_id 正好是 5 个字符长。
short_id中的每个字符都可以是[0-9a-z]
path 保证以 /

Answer 1

创建另一个 tmp 对象作为 Hashmap，这样您就可以只使用路径和 id 创建一个新的密钥来存储。

逻辑：

如果路径是 '/'，它的根，放入 _categories 数组。
如果不存在，检查hashStore中是否存在target parent，如果不存在，则创建一个假的，并将其自身放入target is sub attr.
对所有元素，通过_category.path + _category.short_id + '/'创建一个key，并检查其是否存在于hashStore中，如果存在，则存储中的应该是假的，得到sub 从假的。然后通过创建的key将自己分配给hashStore。

用一个key来决定对象是否存在于map中应该是O(1)。所以这个函数的性能应该是 O(n) 而 n 是原始列表中的元素数。

function buildTree(categories) {
  var _categories = [];
  var store = {};

  angular.forEach(angular.copy(categories), function(_category) {
    if (_category.path === '/') {
      _categories.push(_category);
    } else {
      var target;
      // If parent exist
      if (typeof store[_category.path] !== 'undefined') {

        // Check parent have sub or not, if not, create one.
        target = store[_category.path];
        if (typeof store[_category.path].sub === 'undefined') {
          target.sub = [];
        }

      } else {
        // Create fake parent.
        target = {sub: []};
        store[_category.path] = target;
      }

      // Push to parent's sub
      target.sub.push(_category);
    }

    // Create key map
    var key = _category.path + _category.short_id + '/';
    // If fake object exist, get its sub;
    if (typeof store[key] !== 'undefined') {
      _category.sub = store[key].sub;
    }
    store[key] = _category;

  });

  return _categories;
}

Answer 2

此解决方案更灵活，因为它不需要了解路径长度或与 short_id

的相关性

var source = [{
  "short_id": "2p45q",
  "path": "/",
  "name": {
    "en-US": "IndustrialDesign"
  }
}, {
  "short_id": "2q56r",
  "path": "/2p45q/",
  "name": {
    "en-US": "Automotive"
  }
}];

function buildTree(arr) {
  var source = arr.slice();
  source.sort(function(a, b) {
    return a.path.length <= b.path.length;
  });
  var tree = source.splice(0, 1)[0];
  tree.subo = {};

  source.forEach(function(i) {
    var re = /[^\/]*\//g;
    var context = tree;
    while ((m = re.exec(i.path.substr(1))) !== null) {
      if (context.subo[m[0]] === undefined) {
        context.subo[m[0]] = i;
        i.subo = {};
        return;
      }
      context = context.subo[m[0]];
    }
  });

  (function subOsub(i) {
    var keys = Object.keys(i.subo);
    if (keys.length > 0) {
      i.sub = [];
      for (var j = 0; j < keys.length; j++) {
        i.sub.push(i.subo[keys[j]]);
        subOsub(i.subo[keys[j]]);
      }
    }
    delete i.subo;
  })(tree);
  return tree;
}

alert(JSON.stringify(buildTree(source), null, '  '));

Answer 3

好吧，只需检查每个对象的路径，看看把它放在哪里。您只需要将路径映射到对象。例如

var objs = [
    {
        "short_id": "2p45q",
        "path": "/",
        "name": {
            "en-US": "IndustrialDesign"
        }
    },
    {
        "short_id": "blah",
        "path": "/2p45q/foo/",
        "name": {
            "blah": "blah"
        }
    },
    {
        "short_id": "2q56r",
        "path": "/2p45q/",
        "name": {
            "en-US": "Automotive"
        }
    }
];

// map paths to objects (one iteration)
var path_to_obj = {};
objs.forEach(function(obj){
    path_to_obj[obj.path] = obj;
});

// add objects to the sub array of their parent (one iteration)
objs.forEach(function(obj){
    var parentpath = obj.path.replace(/[^\/]*\/$/, '');
    var parent = path_to_obj[parentpath];
    if(parent){
        parent.sub = parent.sub || [];
        parent.sub.push(obj);
    }
});

var pre = document.createElement('pre');
pre.innerHTML = 'Result:\n' + JSON.stringify(path_to_obj['/'], null, 4);
document.body.appendChild(pre);

从 objects 的普通数组构建嵌套数据树

Building a nested tree of data from plain array of objects

javascript

arrays

performance

json

jsonpath