자바 스크립트에서 상위/하위 목록이있는 평면 목록에서 중첩 목록 생성

Question

중첩 된 지리 데이터를 처리해야하는 웹 응용 프로그램을 작성 중이므로 둘 다 트리 뷰에 표시 할 수 있지만 검색 할 수도 있습니다. 원시 데이터는 다음과 같이 보입니다 :

id:1, name:UK 
id:2: name: South-East, parentId: 1 
id:3: name: South-West, parentId:1 
id:4: name: Berkshire, parentId: 2 
id:5: name: Reading, parentId: 4 

과 나는 같은 것을보고 싶지 :

id:1: name UK, children[ 
{id: 2, name: South-East, children:[ 
    {id:4: name: Berkshire, children: [ 
     {id:5: name: Reading} 
    ] 
    }, 
    {id:3: name: South-West} 
] 

각각의 지리적 위치는 모든 하위를 포함하는 "어린이"배열 속성을 가지고 -areas는 각 "children"배열 속성을 가지고 있습니다. "부모"속성을 갖는 것이 맞을 수도 있으므로 모든 하위 항목에서 상위 항목까지 탐색 할 수 있습니다.

또한 목록을 검색 할 수 있어야합니다. 트리의 각 분기를 검색하는 데 약간의 시간이 걸릴 수 있으므로 목록을 플랫 형식으로 유지해야합니다.

나는 을 (JavaScript, 필터링, 그룹화 및 정렬을 위해 jLinq을 사용하여) 할 수 있음을 알고 있지만 얼마나 빠를 것인지 잘 모릅니다. 누구나 이미 JavaScript에서이 작업을 수행했거나이를 해결하는 일반적인 알고리즘/패턴을 알고 있습니까?

Answer 1

플랫 어레이를 트리로 만들어 꽤 빨리 처리하는 것은 그리 어렵지 않습니다. 가장 느린 비트가 페이지에 데이터 구조의 정의를 가져올 것입니다 (따라서 왜 게으른로드가 성공적 이었습니까? !). 이것은 데이터 구조 정의를 더 작게 만들면 도움이 될 수 있습니다. 실행할 수있는

//Make the data definition as small as possible.. 
    //each entry is [ name, parent_pos_in_array].. 
    //note: requires that a parent node appears before a child node.. 
    var data = [ 
     ["UK", -1], //root.. 
     ["South-East", 0], 
     ["South-West", 0], 
     ["Berkshire", 1], 
     ["Reading", 3] 
     //...etc... 
    ]; 

    //Turns given flat arr into a tree and returns root.. 
    //(Assumes that no child is declared before parent) 
    function makeTree(arr){ 
     //Array with all the children elements set correctly.. 
     var treeArr = new Array(arr.length); 

     for(var i = 0, len = arr.length; i < len; i++){ 
      var arrI = arr[i]; 
      var newNode = treeArr[i] = { 
       name: arrI[0], 
       children: [] 
      }; 
      var parentI = arrI[1]; 
      if(parentI > -1){ //i.e. not the root.. 
       treeArr[parentI].children.push(newNode); 
      } 
     } 
     return treeArr[0]; //return the root.. 
    } 

    var root = makeTree(data); 

더 큰 목록에 속도를 테스트하려면 : 자바 스크립트에서

나는 이런 식으로했다 배열 100000 개 요소

var data = [['root', -1]]; 
    for(var i = 1; i < 100000; i++){ 
     var parentI = Math.floor(Math.random()*(i-1)); 
     data.push(['a_name', parentI]); 
    } 
    var start = new Date().getTime(); 
    var tree = makeTree(data); 
    var end = new Date().getTime(); 

    console.log('Took: ' + (end-start) + 'ms.'); 

가에 < 200ms의 소요 내 오래된 바탕 화면. 어떤 종류의 성능이 받아 들여 지는지 확실하지 않습니다!

Answer 2

수준에 다른 단서가없는 간단한 ID & 상위 ID 개체 배열이있는 경우 중첩 된 양식을 생성하는 것은 힘든 작업입니다. 나는 재귀 적 접근법이 긴 목록에서 실용적이지 않을 것이라고 생각한다. 지금까지 생각해 낼 수있는 가장 좋은 방법은 모든 아이들이 부모를 따라 오는 식으로 배열을 정렬하는 것입니다. 부모와 자식 그리고 루트 객체조차도 혼합 될 수 있지만 부모는 부모가되어야합니다. 객체 구조가 var data = [{id: KL442, pid: HN296}, {id: ST113, pid: HN296}, {id: HN296, pid: "root"},...] 인 것으로 가정합니다. 그러나 정렬은 작업의 첫 번째 단계입니다. 정렬하는 동안 거의 무료로 부모에게 액세스 할 수있는 LUT (look up table)을 생성 할 수 있습니다. 외부 루프의 출구에서 하나의 단일 명령 lut[a[i].id]=i;만으로 충분합니다. 이것은 중첩 단계에서 작업을 매우 빠르게 만듭니다. 이것은 정렬 및 LUT 준비 단계입니다.

function sort(a){ 
    var len = a.length, 
     fix = -1; 
    for (var i = 0; i < len; i++){ 
     while(!!~(fix = a.findIndex(e => a[i].pid == e.id)) && fix > i) [a[i],a[fix]] = [a[fix],a[i]]; 
     lut[a[i].id]=i; 
    } 
    return a; 
} 

역 반복보다 정렬하면 중첩 된 구조를 얻는 데 필요한 유일한 작업입니다. 이제 데이터 배열을 정렬하고 LUT를 준비 했으므로 중첩 코드가됩니다.

for (var i = sorted.length-1; i>=0; i--) 
    sorted[i].pid != "root" && (!! sorted[lut[sorted[i].pid]].children 
           && sorted[lut[sorted[i].pid]].children.push(sorted.splice(i,1)[0]) 
           || (sorted[lut[sorted[i].pid]].children = [sorted.splice(i,1)[0]])); 

a previous answer of mine을 확인할 수 있습니다.