React에서의 DOM 비교 최적화: Virtual DOM과 휴리스틱 알고리즘

🔑Writing Key Point in Posting

💡 알고리즘 시간 복잡도: 왜 중요할까?

---

📃 우리는 소프트웨어를 만들 때 속도가 중요한데, 그때 사용하는 개념이 바로 시간 복잡도입니다. 시간 복잡도는 프로그램이 얼마나 빨리 작동하는지, 즉 입력 데이터가 커지면 프로그램이 얼마나 오래 걸릴지를 알려주는 척도입니다

💻O(n) & O( n² )

// O(n)
for(let i=0; i<100; i++){
	console.log(i);
}

// O(n * n)
for(let i=0; i<100; i++){
	for(let j=0; j<100; j++){
    	console.log(i + j);
    }
}

⬆️ 예를 들어, 우리가 처리해야 하는 데이터가 $ n $ 개라면, 시간 복잡도가 $$ O(n) $$  데이터가 두 배가 되면 처리 시간이 두 배로 늘어나고, $$ O(n^2) $$  데이터가 두 배가 되면 처리 시간이 네 배로 늘어납니다. 이처럼 알고리즘의 시간 복잡도는 우리가 다루는 데이터가 커질수록 얼마나 빨리 프로그램이 작동하는지 중요한 영향을 미칩니다

💡 트리 비교 알고리즘 O(n³)

---

📃 Virtual DOM도 계속해서 DOM을 비교해야 하는데, 비교 작업이 매우 복잡할 수 있습니다. 예를 들어, 두 개의 트리를 비교한다고 할 때, 트리의 모든 노드를 하나씩 비교해야 하니까 시간이 많이 걸립니다. 이 과정에서 O(n³) 복잡도가 발생할 수 있습니다

💻CODE

// O(n)
for(let i=0; i<100; i++){
	console.log(i);
}

// O(n * n)
for(let i=0; i<100; i++){
	for(let j=0; j<100; j++){
    	console.log(i + j);
    }
}

⬆️ 트리 비교에서 $$ O(n^3) $$ 복잡도가 발생하는 이유는 비교가 여러 단계를 거쳐 이루어지기 때문입니다.

• 노드 비교 (O(n)): 트리의 각 노드를 비교하려면 노드마다 하나씩 비교 작업이 이루어집니다.
• 자식 노드 재귀 비교 (O(n²)): 한 노드에 대해 자식 노드들도 또 비교해야 합니다. 이때 자식 노드가 여러 개라면 자식 노드를 비교하는 데 또 시간이 걸립니다.
• 트리 전체 비교 (O(n³)): 전체 트리의 노드를 하나하나 비교하는데, 각 자식 노드도 모두 비교하는 반복적인 과정이 발생하기 때문에 복잡도가 O(n³)로 커집니다.

 

💡 DOM 업데이트

---

📃 React는 우리가 웹 페이지를 만들 때, 화면을 빠르게 갱신해주는 라이브러리입니다. 하지만 React가 화면을 빠르게 갱신하려면 DOM을 효율적으로 처리해야 하는데, DOM은 웹 페이지의 구조를 트리 형태로 저장한 것입니다. 이 트리에서 각 요소를 노드(node)라고 부르며, 트리 안의 여러 요소들을 빠르게 비교하고 변경할 수 있어야 합니다

https://ko.react.dev/

React

https://velog.io/@jeong_woo/mordern-JS-DOM-BOM-JS-tree-Event

⬆️ 문제는, DOM을 계속 갱신하다 보면 화면을 새로 그릴 때마다 DOM을 다시 바꾸는 작업이 매우 느려지기 때문이에요. 이를 해결하기 위해 React는 Virtual DOM이라는 개념을 도입했습니다. Virtual DOM은 실제 DOM을 메모리 상에 미리 만들어두고, 변경된 부분만 업데이트하는 방식입니다

 

💡 React가 어떻게 해결했을까?

---

📃 React는 휴리스틱 알고리즘을 도입해서 이 문제를 해결합니다. 즉, "우리는 모든 노드를 다 비교하지 않고, 더 빠르게 처리할 방법을 찾자!"라는 접근 방식이죠. React는 효율적으로 DOM을 업데이트하기 위해 두 가지 전략을 사용합니다

💻노드 유형이 다르면 다른 트리로 처리

// 기존
<div>
  <p>Hello</p>
</div>

// 업데이트
<div>
  <p>Good Bye</p>
</div>

⬆️ React는 Virtual DOM을 비교할 때, div는 그대로 두고, 그 안에 있는 <p> 요소만 비교합니다.  이때 React는 <p> 태그만 업데이트하고, 그 외의 div는 변경되지 않으므로 업데이트하지 않습니다.

💻key 속성으로 자식 요소 추적

{items.map(item => (
  <div key={item.id}>{item.name}</div>
))}

⬆️ 리스트와 같은 반복되는 요소에서는 key 속성을 사용하여 React가 각 항목을 정확히 추적하게 합니다. 이렇게 하면 React는 리스트의 아이템이 변경된 부분만 빠르게 업데이트하고, 나머지 항목은 그대로 두게 됩니다

📝 결과적으로 React는 어떻게 최적화됐을까?

---

📌 React는 휴리스틱 알고리즘을 활용해, DOM을 비교하는 복잡도를 줄입니다. 모든 트리를 일일이 비교하는 대신, 필요한 부분만 선별적으로 비교하고 업데이트하여 성능을 최적화한 것입니다.따라서, 데이터가 많아져도 React는 $$ O(n) $$ 복잡도로 효율적으로 화면을 업데이트할 수 있게 됩니다. 큰 데이터셋에서의 성능 문제가 해결되면서 React는 빠르고 효율적인 화면 렌더링을 제공합니다