Set 자료구조 비교 (c++, python)

알고리즘을 풀던 도중 c++에서 set은 데이터가 정렬되어 있으나 python의 set은 그렇지 않다는 사실을 발견했다.
왜 이러한 차이가 있는고 이러한 차이가 만들어내는 특징은 무엇이 있는지 알아보았습니다.

---

Set 자료구조란 무엇인가

우선 Set 자료구조에 대해 간단히 알아보고 가겠습니다.

 

위키에서는 다음과 같이 정의하고 있습니다.

In computer science, a set is an abstract data type that can store unique values, without any particular order.
It is a computerimplementation of the mathematical concept of a finite set.
Unlike most other collection types, rather than retrieving a specific element from a set, one typically tests a value for membership in a set.

 

번역해 보자면

컴퓨터 과학에서, Set은 유일한 값들이 특정한 순서에 관계없이 저장된 추상적인 데이터 타입입니다.
이는 유한 집합이라는 수학적인 개념을 컴퓨터에 구현한 것입니다.
다른 대부분의 collection 타입들과는 다르게 Set은 특정 요소의 값을 찾기보다

요소가 집합에 존재하는지 확인하는지 검사할 때 사용됩니다.

 

정의에 따르면 Set 자료구조는 데이터를 정렬할 필요가 없습니다.

#include <iostream>
#include <set>
using namespace std;

int main() {
	set<int> s;
	
	s.insert(1);
	s.insert(5);
	s.insert(3);
	s.insert(2);
	s.insert(4);
	
	for(auto iter = s.begin(); iter != s.end(); ++iter) {
		cout << *iter << ' ';
	}
	// 출력 값: 1 2 3 4 5
	return 0;
}

 

하지만 위 코드를 실행시켜 본다면 순서와 상관없이 자동으로 정렬되고 있다는 것을 알 수 있습니다. 

 

왜 C++에서는 데이터를 정렬해서 저장하고 있을까?

 

데이터를 삽입할 때마다 데이터를 정렬하는 행위는 추가적인 연산을 요구하기에 비효율적이라고 볼 수도 있습니다.

 

그럼에도 불구하고 이러한 방식을 취했다면 어떠한 이점이 있기 때문일 것입니다.

 

여기서 우리가 기억해야 할 점은 Set의 가장 중요한 특징이 모든 값이 중복 없이 유일(unique)하다는 것입니다.

따라서 Set에 데이터를 삽입할 때는 항상 중복된 값의 유무를 판단해야 합니다.

 

정렬되어 있지 않은 배열일 경우 특정 값의 유무를 판단하기 위해서 모든 데이터를 확인해야 하므로

O(n)만큼의 시간이 사용됩니다.

 

하지만 정렬되어 있다면 BinarySearch와 같은 알고리즘을 사용해 O(log n)만에 값의 유무를 판단할 수 있습니다.

 

따라서, 정렬된 데이터는 2가지의 이점을 줍니다.

1. 배열에서 특정 값을 빠르게 찾아낼 수 있다.
2. 1번을 활용하여 빠르게 중복 값을 확인할 수 있으므로 Set배열에 데이터를 보다 효과적으로 삽입할 수 있다.

C++ Set 자료구조 더 살펴보기

 

중복된 값의 존재 여부를 판단하는 것만으로 데이터 삽입은 끝나지는 않습니다.

새로운 값이 삽입된 후에도 정렬된 배열을 유지하려면 아래 두 가지 과정 중 한 가지를 사용해야 합니다.

• 순서에 맞는 위치를 찾아 값을 삽입한다.
• 무작위로 값을 추가한 후 순서에 맞춰 값을 정렬한다

단순 배열을 사용하고 있다면

1번의 경우 O(n)만큼의 시간 복잡도를 가지며

2번의 경우 O(n log n)만큼의 시간 복잡도를 가지게 됩니다.

 

하지만 우리가 Set 자료구조를 효과적으로 사용하기 위해서는 더 빠른 수행 시간 안에 값을 추가할 수 있어야 합니다.

 

C++에서는 2가지의 규칙을 가진 Tree구조를 사용해 수행 시간을 보장받고 있습니다.

1. 부모의 왼쪽 자식은 부모보다 작은 값들로 이루어져 있다.
2. 부모의 오른쪽 자식은 부모보다 큰 값들로 이루어져 있다.

 

C++ Set 자료구조 예시

 

위와 같은 자료구조를 통해 데이터 추가, 삭제, 검색에서 모두 트리의 높이만큼의 시간 안에 처리할 수 있게 됩니다.

 

하지만, 0 -> 10 -> 20 -> 30 -> 40 -> 50의 순서로 데이터가 추가된다면

 

아래와 같은 모양의 트리가 만들어져 트리의 높이 = 자료의 개수가 되어

결국 O(n)의 시간 복잡도를 가지게 됩니다.

Worst Case

 

 

이러한 문제는 주기적인 restructing을 통해 예방할 수 있습니다.

 

최대한 낮은 높이의 트리를 만들기 위해 가장 가운데에 위치한 값을 부모로 설정한다면

트리의 높이가 log n이 되므로 O(log n)만큼의 시간 복잡도를 기대할 수 있습니다.

 

실제 구조는 보다 성능이 좋은 B-Tree 자료구조를 사용하고 있습니다.

 

파이썬 Set은 효율적이지 못한 걸까?

 

파이썬 Set은 정렬되지 않았기 때문에 효율적이지 않는다는 생각을 하게 될 수 있습니다.

하지만 놀랍게도 파이썬 Set의 경우 평균적으로 C++ Set보다 빠른 O(1)의 시간 복잡도를 가지고 있습니다.

 

어떻게 이렇게 빠르게 작업을 수행할 수 있는 걸까요?

답은 Hash Table을 사용하기 때문입니다.

 

Hash Table이란 Hash Function을 활용하여 만든 자료구조로

데이터와 저장공간을 최대한 1:1에 가깝게 매칭하여 관리합니다.

 

이를 통해 데이터 추가/제거 및 검색을 가장 빠르게 할 수 있는 자료구조입니다.

 

하지만, Hash Table은 Hash Function에 따라 성능이 결정될 수 있습니다.

Hash Function의 성능이 좋지 않을 경우 O(n)의 시간을 요구할 수 있습니다.

 

또한, 저장 공간을 많이 사용해야지만 O(1)의 속도를 보장받을 수 있습니다.

이에 메모리 관리 측면에서는 효율적이지 못한다는 단점이 있습니다.

 

해시 테이블이란?

정리

C++ Set 자료구조와 같이 B-Tree로 이루어졌을 경우
최악의 경우에도 O(log n)을 기대해 볼 수 있으며, 메모리를 효율적으로 사용할 수 있습니다.

 

Python Set 자료구조와 같이 Hash Table로 이루어졌을 경우 O(1)이라는 굉장히 훌륭한 성능을 이용할 수 있지만,
최악의 경우 O(n)만큼의 시간을 사용하며, 메모리를 많이 사용하게 된다는 단점이 있습니다.

 

C++의 경우 unordered_set 라이브러리에 있는 unordered_set STL을 사용한다면 파이썬 Set과 같은 Hash Table 형태의 자료구조를 사용할 수 있으므로, 상황에 맞게 두 자료구조를 선택하여 사용하는 것이 바람직합니다.