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

Question

我有对象的数组，象那些的：

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

... 

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

我必须遍历数组的每个元素，并检查path，然后找到父元素，并将其推入该父元素的新数组属性sub。每个孩子可以拥有自己的sub财产，因此是更多孩子的父母。最终的结果（在这个例子中）看起来像：

{ 
    "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创建一个新的关键商店。

逻辑：

1. 如果路径是'/'，它的根，付诸_categories阵列。

2. 如果不是，请检查目标父项是否存在于hashStore中，如果没有，则创建一个假目标父目录，并将其自己指向目标为sub attr。

3. 对于所有元素，通过_category.path + _category.short_id + '/'创建密钥，并检查其在hashStore存在，如果存在，一个在商店应该是假的，假的，从获得sub。然后通过创建的键将自己分配给hashStore。

使用一个键来决定对象是否存在于地图中应该是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);