JavaScript 평면 배열 트 리 구조의 실현 예제

백 스테이지 에서 1w 개의 데 이 터 를 잃 어 버 렸 다.
아무리 계산 해도 도망 가지 못 했 습 니 다.백 스테이지 에서 정말 수만 개의 데 이 터 를 한 번 에 프론트 에 잃 어 버 렸 습 니 다.좋아,다행히 아직 10w 마리 가 아니 야.다음 과 같이 백 엔 드 는 이러한 구 조 를 되 돌려 줍 니 다.

const flatArr = [
  { id: '001', name: '  1' },
  { id: '0011', parentId: '001', name: '  1-1' },
  { id: '00111', parentId: '0011', name: '  1-1-1' },
  { id: '002', name: '  2' },
]

이 를 통 해 알 수 있 듯 이 이것 은 실제 적 으로 평평 하 게 깔 린 배열 입 니 다.우리 의 수 요 는 이러한 데 이 터 를 Element-ui 의 직렬 선택 기 에 보 여 주 려 면 다음 과 같은 트 리 구 조 를 받 아야 합 니 다.

let options = [
  {
    value: 'zhinan',
    label: '  ',
    children: [
      {
        value: 'shejiyuanze',
        label: '    ',
        children: [
          { value: 'yizhi', label: '  ' },
          { value: 'fankui', label: '  '}
        ],
      }
    ]
  }
]

자식,이 건 내 가 평평 한 배열 을 나무 구조 로 바 꿔 야 하 는 거 잖 아!
한 차례 의 조작 은 호랑이 처럼 맹렬 하여,두 마디 말 도 하지 않 고 쓰 고 돌아 갔다.
귀속 방식

큰 성 과 를 거 두 었 습 니 다.코드 가 간결 하고 생각 이 뚜렷 합 니 다.실행 하면 무엇 입 니까?페이지 가 끊 겼 습 니 다.console.time()계산 은 약 18s 를 사용 해서 우리 가 필요 로 하 는 트 리 구 조 를 계산 합 니 다.
나 는 나 자신 을 반성 했다.이것 은 수만 개의 데이터 이다.아래 에서 위로 돌아 가 부모 노드 의 하위 노드 를 찾 을 때마다 배열 을 한 번 씩 옮 겨 다 녀 야 한다.이것 은 당연히 시간 이 걸린다!그리고 계산 시간 이 현저히 페이지 가 멈 추 었 습 니 다.이 방법 은 분명 바람 직 하지 않 을 것 입 니 다.그러면 더 좋 은 방안 이 있 습 니까?
비 귀속 방식

여기 서 대상 이 저장 하 는 것 은 인용 하 는 특징 을 교묘 하 게 응용 했다.현재 노드 의 id 를 key 로 하고 해당 노드 의 인용 정 보 를 저장 하 며 배열 을 옮 겨 다 닐 때 object Map 의 children 정 보 를 업데이트 할 때마다 object Map 에 모든 노드 의 하위 노드 를 보류 했다.가장 중요 한 것 은 우 리 는 배열 만 옮 겨 다 니 고 시간 복잡 도 는 O(n)이다.이런 방식 을 사용 하면 계산 시간 이 60ms 밖 에 안 됩 니 다!
총결산

재 귀적 방식:현재 노드 의 하위 노드 를 재 귀적 으로 찾 을 때마다 배열 을 다시 한 번 옮 겨 다 녀 야 합 니 다.시간 복잡 도 는 O(nlogn)

입 니 다.

비 재 귀 방식:뿌리 노드 에서 하위 노드 를 찾 고 Map 을 통 해 각 노드 와 하위 노드 의 정 보 를 저장 합 니 다.하위 노드 는 Map 의 인용 을 저장 합 니 다.각 노드 의 하위 노드 는 Map 에서 id 를 통 해 찾 을 수 있 고 시간 복잡 도 는 O(n)

입 니 다.
우 리 는 대비 도 를 보 자.

위의 시간 복잡 도 는 데이터 양 이 증가 하 는 추 세 를 통 해 알 수 있 듯 이 데이터 가 점점 커지 면 재 귀 알고리즘 의 소 모 는 비 재 귀 알고리즘 보다 훨씬 클 것 이다.따라서 데이터 양 시간 에 재 귀 알고리즘 을 사용 하 는 것 은 어느 정도 장점 이 있 지만 데이터 가 어느 정도 클 때 재 귀 하 는 방법의 약점 이 점점 뚜렷 해 지고 비 재 귀 알고리즘 을 사용 하 는 것 이 훨씬 빠 를 것 입 니 다!
마지막 으로 감개 할 수 밖 에 없습니다.이 대 비 를 통 해 우 리 는 알고리즘 의 중요성 을 뚜렷하게 느 낄 수 있 습 니 다.서로 다른 실현 방식,차이 가 매우 클 수 있 습 니 다.이것 은 모든 developer 가 알고리즘 에 대한 중 시 를 불 러 일 으 킬 필요 가 있 습 니 다!
자 바스 크 립 트 평 포 배열 의 트 리 구조 구현 에 관 한 예제 에 관 한 이 글 은 여기까지 소개 되 었 습 니 다.자 바스 크 립 트 평 포 배열 의 트 리 구조 내용 은 우리 의 이전 글 을 검색 하거나 아래 의 관련 글 을 계속 찾 아 보 세 요.앞으로 많은 응원 부 탁 드 리 겠 습 니 다!