Reduce를 활용한 데이터 평탄화

얼마 전에 reduce를 활용해서 데이터 접근의 시간 복잡도를 줄이는 글에 대해서 보았다.

https://www.jeong-min.com/59-reduce/

현재 나는 깊이가 최대 3인 다중 트리 데이터를 다뤄야 하는 일이 있는데 이번 기회를 통해 해당 트리 데이터를 reduce를 통해 평탄화 하는 작업을 해보려고 한다.

각 트리 노드는 유니크한 id 값을 가지고 있는데 해당 id를 기반으로 바로 데이터 접근할 수 있도록 하면 O(1)로 원하는 데이터를 찾을 수 있을 것이다.

const treeDataWithIds = [
  {
    title: 'parent 1',
    key: '0-0',
    id: 0,
    additionalData: { info: 'Root node' },
    children: [
      {
        title: 'parent 1-0',
        key: '0-0-0',
        id: 1,
        disabled: true,
        additionalData: { info: 'First child of root' },
        children: [
          {
            title: 'leaf',
            key: '0-0-0-0',
            id: 2,
            additionalData: { info: 'Leaf node 1' },
          },
          {
            title: 'leaf',
            key: '0-0-0-1',
            id: 3,
            additionalData: { info: 'Leaf node 2' },
          },
        ],
      },
      {
        title: 'parent 1-1',
        key: '0-0-1',
        id: 4,
        additionalData: { info: 'Second child of root' },
        children: [
          {
            title: "hello",
            key: '0-0-1-0',
            id: 5,
            additionalData: { info: 'Leaf node 3' },
          },
        ],
      },
    ],
  },
];

위와 같이 트리 데이터가 존재한다고 하고 특정 id 값을 가진 데이터에 접근하기 위해서는 일반적으로 재귀를 활용해서 트리를 돌면서 찾을 수 있을 것이다.

const findTargetData = (data: DataType, key: string) => {
  for (let i = 0; i < data.length; i++) {
    if (data[i].key === key) {
      return data[i]
    }
    if (data[i].children) {
      findTargetData(data[i].children!, key);
    }
  }
};

즉 특정 데이터에 접근할 때마다 최악의 경우 모든 트리를 다 순회할 것이다. 따라서 데이터를 접근하는 데 비효율적이다.

뎁스가 있는 해당 데이터를 아예 평탄화 시키고 id를 key해서 바로 접근할 수 있게 reduce를 활용해보자. 즉, id를 키로 가지는 다음과 같은 객체를 만들 것이다.

const data = {
	 "5": {
    	title: "hello",
        key: '0-0-1-0',
        additionalData: { info: 'Leaf node 3' },
     },
     "3": {
    	title: 'leaf',
        key: '0-0-0-1', 
        additionalData: { info: 'Leaf node 2' },
     }
}

최초 데이터를 가지고 온 후에 다음 코드를 적용해서 평탄화할 수 있다. 최초 한번만 모든 트리 데이터를 순회하면 그 다음부터는 바로 특정 데이터에 접근할 수 있다.

const flattenTreeData = (curTree) => {
  return curTree.reduce((acc, node) => {
    const { id, children, ...rest } = node;
    acc[id] = rest
    if (node.children) {
      Object.assign(acc, flattenTreeData(node.children));
    }
    return acc;
  }, {});
}

const newTreeData = flattenTreeData(treeData)

위 코드를 통해 평탄화를 할 수 있다.

여기서 그러면 reduce에 대해 간단히 살펴보자.

reduce는 다음과 같이 리듀서 함수와 초기값을 인자로 받는다. 초기값은 옵셔널로 넘기지 않는다면 배열의 첫번 째 요소가 초기값으로 사용된다.

reduce(callbackFn)
reduce(callbackFn, initialValue)

그리고 리듀서 함수는 4가지의 인수를 받는다.

• accumulator - 누산된 데이터
• currentValue - 현재 데이터
• currentIndex - 현재 인덱스
• array - 원본 배열

array.reduce((accumulator, currentValue, currentIndex, array) => {
  // 누산기와 현재 값을 이용해 무언가를 함
  return newAccumulator;
}, initialValue);

배열의 총 합을 구하는 예시)

초기값을 0으로 넘겨주고 배열을 돌면서 합산한다.

const numbers = [1, 2, 3, 4, 5];

const sum = numbers.reduce((accumulator, currentValue) => {
  return accumulator + currentValue;
}, 0);

console.log(sum); // 출력: 15

---

이렇게 봤듯이 reduce를 활용하면 더 효율적으로 데이터를 가공하고 접근할 수 있다.

추가로 reduce와 spread 연산자를 사용하면 성능상 좋지 않다고 한다. 결국 spread 연산자는 Object.assign의 Syntax Sugar(문법 설탕)이다.(참고)

아래 두 방식은 동일한 결과를 가진다.

const a = { value: 1, label: "no1" };
const b = { value: 2, label: "no2" };

// 아래 2개는 동일한 동작을 하는 코드
console.log(Object.assign({}, a, b)); // 신규 객체 생성
console.log({ ...a, ...b }); // 신규 객체 생성

따라서 spread 연산자를 사용하게 되면 모든 객체 내 속성을 순회하게 되어 reduce와 spread 연산자를 같이 사용하면 시간 복잡도가 O(N^2)이 될 것이다.

참고
https://dinn.github.io/javascript/js-reduce-spread/
https://developer.mozilla.org/ko/docs/Web/JavaScript/Reference/Global_Objects/Object/assign
https://yceffort.kr/2021/06/reduce-spread-anti-pattern