자료 구조(data structures)는 알고리즘의 구성요소이고 인공지능, (AI, Artificial Intelligence)나 기계학습 (ML, Machine Learning) 알고리즘이 효율적으로 작동하는데 아주 중요합니다. 보통 간단하게 데이터를 포함하고 있는 저장소로 생각을 하는 경우가 많은데 그 보다 더 큰 의미가 있습니다. 복잡한 계산을 효율적으로 빠르게, 그리고 성능면에서 아주 많은 영향을 주죠. 그러므로 자료 구조의 결정은 심사숙고하며 해결하고자 하는 문제와 계산의 복잡성등을 생각하여 이루어져야 합니다.
이 포스팅에서는 AI와 ML에서 사용되고 있는 몇가지의 자료 구조 타입들을 간단하게 배워보고 예제를 통하여 각각의 장단점들도 알아 보겠습니다. 예제 코드는 파이썬 (Python) 코드로 진행을 하겠습니다.
우선 심플한 배열 (arrays)과 동적배열 (dynamic arrays)의 기본 개념으로 시작하여 연결 리스트 (linked lists)나 이진 탐색 트리(binary search trees) 같은 고급 구조를 알아본 후 해시 테이블(hash tables)로 마무리를 하겠습니다.
1. 배열과 동적 배열 (Arrays and Dynamic Arrays)
컴퓨터 공학에서 가장 기본적인 자료 구조입니다. 배열은 인접한 메모리 위치에 저장된 동일한 타입의 컬렉션이고 배열의 각 요소에 랜덤한 액세스를 제공합니다. 메모리 할당량이 심플한 배열보다 더 많은 파이썬의 리스트와 같은 동적 배열은 심플 배열의 기반으로 엘리먼트의 추가와 삭제가 가능합니다. 자동 메모리 할당의 기능은 동적 배열의 중심이죠. 보통 데이터의 수가 변화하지 않는 곳에 배열을 사용합니다. 이런 데이터는 기계학습에 사용이 되는 데이터셋이죠.
장점 (PROs):
인덱스를 사용하여 구성 엘리먼트를 빠르고 쉽게 액세스를 할 수 있음. 이 점은 시간이 중요한 많은 AI와 ML에 필수입니다.
알려져 있거나 정해진 사이즈의 문제에 좋음. 구성 요소의 개수가 정해져 있거나 거의 변하지 않는 경우입니다.
단점 (CONs):
정해진 사이즈 (정적 배열일 경우). 미리 최대 배열의 사이즈를 알고 있어야 합니다. 그러므로 사용될 수 있는 경우가 제한적입니다.
추가와 삭제의 비용이 큼 (정적 배열일 경우). 추가또는 삭제시에 구성 요소들을 이동시켜야 하므로 계산의 비용이 크죠.
ML의 세계에서는 벡터나 행렬로된 특성의 데이터셋을 처리하는데 배열이 아주 중요합니다. NumPy 같은 수와 관계된 고성능의 라이브러리들은 효율적인 데이터 처리를 위해 배열을 사용합니다.
아래의 예제는 파이썬의 동적 배열 자료 구조인 리스트입니다:
2. 연결 리스트 (Linked Lists)
연결 리스트는 순서적인 노드로 구성된 또 하나의 기본적 자료 구조입니다. 각 노드는 데이터와 다음 노드의 포인터로 구성되어 있습니다. 단순 연결 리스트(singly linked list)는 구성 노드가 다음 노드의 포인터만 있어서 정방향으로만 순회 (traversal)가 가능합니다. 이와는 다르게, 이중 연결 리스트(doubly linked list)는 이전과 다음 노드의 포인터 레퍼런스가 존재하므로 양방향으로 순회가 가능합니다. 이러한 점은 연결 리스트가 배열보다는 더 유연합니다.
장점 (PROs):
동적 확장과 축소가 자료 구조의 재할당이나 이동같은 추가적인 계산 비용이 없이 가능함.
다른 노드의 이동이 없이 빠른 삽입과 삭제가 가능함.
단점 (CONs):
예측이 불가능한 구성 요소들의 저장 위치로 인해 배열보다는 불완전한 캐싱.
처음의 노드 부터 순회를 해야하므로 인덱스로 구성 요소를 찾는데 시간이 더 많이 소요됨.
동적인 사이즈 변형 기능이 연결 리스트의 강점이므로 보통 구성 요소의 개수가 알려지지 않았거나 잦은 삽입과 삭제가 필요할 경우에 사용이 적절합니다. AI와 ML에서는 사용 범위가 배열보다는 적지만 연결 리스트는 유전 알고리즘(genetic algorithms)의 데이터 풀 (pools) 관리 같은 빠르게 변하기 쉬운 자료 구조가 필요한 곳에 사용이 되고 있습니다.
아래의 예제는 파이썬으로 연결 리스트를 구현하였습니다:
LinkedList 클래스는 생성, 데이터 추가, 노드 삭제, 그리고 리스트 프린트 같이 연결 리스트의 모든 기능을 관리하는 클래스입니다. 초기화 시에 헤드 포인터, 헤드, 그리고 빈 연결 리스트를 생성합니다.
append 메서드는 빈 리스트일때는 처음에 그렇지 않으면 끝에 새로운 노드를 생성하며 데이터를 추가합니다.
delete_node 메서드는 주어진 키를 이용하여 노드를 삭제합니다. 다음의 세가지 케이스가 있습니다 (1 - 키가 헤드 노드일 경우, 2 - 키가 리스트 중의 노드일 경우, 3 - 키가 일치하는 노드가 없는 경우). 포인터를 정확하게 사용한다면 남은 노드의 순서에 영향을 주지 않고도 노드를 삭제할 수 있습니다.
print_list 메서드는 헤드 부터 시작하여 각 노드의 내용을 프린트합니다.
아래의 예제는 위의 LinkedList의 사용 예제입니다:
3. 이진 탐색 트리 (Binary Search Trees, BST)
트리는 상위-하위 (부모-자식) 관계의 노드를 가진 비선형 자료 구조의 한 예입니다. 각 트리는 루트 노드가 존재하고 계층적으로 노드들은 하위 노드가 0에서 여러개가 있을 수 있습니다. BST는 노드당 2개 이하의 하위 노드를 가질 수 있고 2개의 하위 노드는 왼쪽과 오른쪽 하위 노드로 나뉘게 됩니다. 노드에 속해있는 키의 값은 모든 좌측 하위 노드들의 값 이상이어야 하고 모든 우측 하위 노드들의 값 이하여야 합니다. 이런 BST의 특성은 트리가 균형이 잡혀 있는 동안 더 효율적인 검색, 삽입과 삭제를 가능하게 합니다.
장점 (PROs):
배열이나 연결 리스트에 비해 BST의 검색, 삽입, 삭제의 성능이 더 좋음
단점 (CONs):
트리의 균형이 깨지면 BST의 성능이 둔화됨
성능의 둔화 시에는 최악의 경우 O(n)의 시간 복잡도를 가지게 됨
시간 복잡도(time complexity)란 ? https://namu.wiki/w/시간%20복잡도
BST는 아주 많은 검색, 삽입, 삭제를 빈번하게 해야하는 데이터셋에 유용합니다. 그리고 시스템이나 조직도 (organizational chart) 같은 상하관계가 존재하는 데이터에 사용이 됩니다.
액세스, 삽입, 삭제 시 평균적으로 O(log n)의 시간 복잡도를 가지므로 검색 성능이 뛰어나므로 데이터의 액세스와 수정의 성능이 뛰어나야하는 애플리케이션에 도움을 줍니다.
기계학습 중 분류 (classification)나 회귀 (regression)에 많이 사용되는 의사 결정 나무(decision trees)는 특성에 의해 만들어진 룰을 기반으로 타겟 변수를 예측하는 모델을 가능하게 합니다. 시나리오의 시뮬레이션을 하고 최적화 액션을 취하는 체스같은 전략성의 게임 프로그래밍에 트리는 자주 사용이 됩니다.
아래의 예제는 파이썬으로 간단한 BST를 구현하는 코드입니다:
TreeNode 클래스는 노드의 값(val)과 좌측 우측 하위 노드의 포인터(left, right)를 저장합니다.
insert 함수는 재귀적인 (recursive) 전략으로 값을 BST에 삽입합니다. 루트가 없을 경우 새로운 TreeNode를 생성하고, 그렇지 않은 경우에는 BST의 구조를 유지하면서 값의 크기에 따라 노드의 좌측 우측의 위치가 결정이 됩니다.
search 함수는 루트로 시작하여 하위 노드들을 재귀적인 방법으로 원하는 값을 검색합니다.
delete_node 메소드는 세 가지의 케이스로 나뉩니다 (1 - 하위 노드가 없는 경우의 삭제, 2 - 우측 하위 노드가 있는 경우의 삭제, 3 - 두개의 하위노드가 있는 키를 삭제). 재귀적인 방법으로 BST의 구조를 유지하며 삭제를 합니다.
헬퍼 함수인 minValueNodes는 최소 값을 가진 (가장 좌측의 노드) 노드를 찾는 함수입니다. 이 함수는 두개의 하위 노드가 있는 노드를 삭제할 경우에 호출이 됩니다.
아래는 위의 코드를 사용하는 예제입니다:
4. 해시 테이블 (Hash Tables)
빠르게 데이터를 액세스하려면 해시 테이블이 최적화된 자료 구조입니다. 해시 함수를 이용하여 인덱스를 슬롯이나 버킷 시리즈로 계산하여 원하는 값을 리턴합니다. 해시 테이블은 해시 함수로 인해 즉각적으로 데이터를 액세스하므로 대용량의 데이터셋에 사용합니다. 해시 테이블의 효율성은 객체들을 버킷의 배열상에 나란히 분포시키는 해시 함수에 의존을 합니다. 이런 분포는 키 충돌을 막습니다. 적절한 키 충돌 해결은 해시 테이블 적용시에 주요점입니다.
장점 (PROs):
빠른 데이터 검색. 해시 테이블은 평균적으로 액세스, 삽입, 삭제 시 O(1)의 시간 복잡도를 가지고 있습니다.
평균적인 시간 복잡도의 효율성이므로 일관성있는 속도를 가지고 있어서 실시간 데이터 핸들링에 적합합니다.
단점 (CONs):
동일한 버킷에 많은 아이템이 해싱되면 O(n)의 시간 복잡도로 성능이 둔화됩니다.
해시 함수에 의존. 해시 함수는 버킷들 사이에 데이터가 어떻게 분포되는가에 영향을 주므로 이 함수의 해시 테이블 성능에 기여하는 중요성은 아주 높습니다.
해시 테이블은 순서가 필요없이 빠른 데이터 찾기, 삽입과 삭제가 필요한 곳에 아주 많이 사용되고 있습니다. 키를 사용하여 데이터를 검색하는 곳에 적절합니다. 상수 시간 복잡도는 시간이 생명이고 고성능 데이터 오퍼레이션이 필요한 곳에 아주 용이하죠.
대용량의 데이터에도 성능이 뛰어나 AI 프로그래밍에서 자주 사용이 됩니다.
기계학습에서도 해시 테이블은 대용량의 특성 데이터를 인덱싱 및 훈련을 거친 모델을 제작하는데 사용이 됩니다. 알고리즘의 성능에도 영향을 줍니다. k-nearest neighbors를 계산하는 시나리오에서는 이전에 저장된 계산된 거리 값을 바로 해시 테이블에서 가져올 수 있죠. 결과적으로 알고리즘의 성능이 개선됩니다.
아래의 예제는 파이썬으로 해시 테이블을 구현합니다:
감사합니다
참고:
