이전 포스팅에서 React의 diffing algorithm에 대한 이야기를 하며 heuristics 알고리즘을 이용한다고 말한 적이 있다. 휴리스틱 알고리즘은 중요한 정보만 고려해서 최선의 값을 찾아내는 알고리즘이라고 나와있었지만, 조금 더 딥하게 알고 싶어(조금 더 리액트를 잘 이해하고 싶어서) 찾아보았다.
Heuristic Algorithm
A heuristic algorithm is one that is designed to solve a problem in a faster and more efficient fashion than traditional methods by sacrificing optimality, accuracy, precision, or completeness for speed. Heuristic algorithms are most often employed when approximate solutions are sufficient and exact solutions are necessarily computationally expensive.
heuristic이란 단어는 라틴어의 기원으로 "I find, discover"이란 의미를 가지고 있다. 즉, 전통적인 방식보다 빨리 문제를 해결 방안을 찾을 수 있다.
휴리스틱 알고리즘의 정의는 문제를 더 빠르고 효율적으로 해결하기 위해 디자인된 방안이다. 그래서 휴리스틱 알고리즘은 비싼 연산이 요구되는 경우나 효율적이면서 빠른 해결방안이 필요한 경우 사용된다. 다만, 정확한 연산이 필요한 경우에는 사용이 지양된다.
세상에 완벽한 알고리즘은 없듯이 휴리스틱 알고리즘에도 장단점이 존재한다. 휴리스틱은 앞서 말한 것 처럼 최적해를 를 보장하지는 않고, 단 하나의 해결법을 제공한다. 그리고 휴리스틱은 모든 알고리즘보다는 빠른 것이 아니라 과거의 방안보다는 빠르다는 것이다. 이런 점을 잘 고려해서 휴리스틱을 사용할 지 결정해야하고, 리액트에서는 '그럼에도 불구하고'이 휴리스틱 알고리즘을 선택했다.(공홈에 최적해가 아닐 수 있다는 문구와 함께 말이다)
휴리스틱 알고리즘은 알고리즘 수업시간에 배웠던 냅색 문제나 searching and sorting 문제도 빠르게 해결할 수 있었다.
Greedy와 차이점은?
Greedy 알고리즘은 수학적 최적해 문제에 많이 사용된다. 즉, 최대 최소값을 구할 때 그리디가 가장 많이 사용된다. 그리디 알고리즘은 stage를 분할해 각 스테이지별로 최적해를 찾는다. (그래서 휴리스틱와 같이 모든 순간에 최적해라는 것을, 즉 마지막 결과가 최적해임을 보장하지는 못한다) 반면, 휴리스틱 알고리즘은 최적해를 보장하지 않을 수 있지만, 최적해와 근접한 결과값을 단시간에 제공해준다.
그리디 알고리즘은 최악의 상황일때 시간 복잡도와 공간 복잡도가 상당히 높을 수 있지만, 휴리스틱 알고리즘은 시간은 상당히 절약할 수 있다.
그래서 Diffing Algorithm에서 Heuristic Algorithm을 사용하는 이유는?
최악의 경우에는 리액트의 컴포넌트를 트리가 아닌 리스트 형태로 제공해 가상돔처럼 "미리"존재하는 컴포넌트처럼 이미 존재하는 트리와 매치시켜 보아야 하기 때문에 새로운 트리가 만들어지지 않는다. 물론 이 diffing 방법에 단점이 있기 때문에 현재 리액트에서 Fiber이란 방법을 고안했다.
배운점
알고리즘에 2차원 배열도 잘 모르던 내가 이렇게 휴리스틱 알고리즘을 찾아보고 이해할 수 있다는 것이 정말 재미있는 것 같다. 그리고 리액트를 조금 더 잘 이해하는데 정말 큰 도움이 되는 것 같다. 리액트에서 가상돔을 많이 활용하는데 이런 동작 원리를 깊이 이해하지 못하면 계속 '왜?'라는 생각밖에 안떠오를 것 같아 찾아보기 시작했는데 계속 보다 보니 정말 재미있는 것 같다. 개발 공부는 정말 왕도가 없고 평생 공부해도 다 못할 것 같아, 내가 계속 성장할 수 있는 자양분이 되는 것 같아 정말 즐겁다!! 다음 포스팅에는 fiber에 대해 조사한 후 글을 적을 예정이다.
Word Cited
