從對象的普通數組構建數據的嵌套樹

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);