Python : List 와 Set의 탐색 속도 차이

Set은 List보다 더 빠른 탐색 속도를 가진다.

그 이유는 내부적인 데이터 구조와 탐색 알고리즘의 차이 때문이다.

 

1. 데이터 구조:

• Set은 해시 테이블(Hash Table)로 구현되어 있다. 해시 테이블은 값에 대한 고유한 해시 코드를 계산하고, 해당 해시 코드를 기반으로 값을 저장하고 검색한다. 따라서 Set은 중복된 값을 허용하지 않으며, 값에 상수 시간 (O(1)) 으로 접근할 수 있다.
• List는 배열(Array)로 구현되어 있다. 배열은 각 요소가 인덱스로 직접 접근되므로 인덱스를 알면 상수 시간 (O(1)) 에 해당 요소에 접근할 수 있다. 그러나 List에서 값을 검색하기 위해서는 전체 리스트를 순회해야 하므로 최악의 경우 선형 시간 (O(N)) 이 걸릴 수 있다.

 

2. 탐색 알고리즘:

• Set에서 값의 존재 여부를 확인하는 연산은 내부적으로 해시 함수와 버킷(bucket)을 사용하여 상수 시간 (O(1)) 안에 처리된다.
• List에서 값의 존재 여부를 확인하기 위해서는 순차적인 비교 연산을 수행해야 한다. 따라서 최악의 경우 리스트의 모든 요소를 순회해야 하므로 선형 시간 (O(n))이 소요된다. 반면, Set은 내부적인 데이터 구조와 탐색 알고리즘을 통해 중복을 제거하고 빠른 탐색 속도를 제공할 수 있다.

 

대신 Set은 순서가 보장되지 않으며, 인덱스 기반 접근이 불가능하기 때문에 특정 위치의 요소에 바로 접근하는 용도보다는 멤버십(Membership) 확인( = 존재유무확인 ) 등을 위한 용도로 주로 사용된다.