[Python] list 와 set의 탐색 속도 차이

# 숫자카드

N = int(input()) # 가진 카드 수
cards = list(map(int,input().split())) # 가진 카드들 - 1) list타입으로 탐색 - 시간초과
cards = set(map(int,input().split())) # 가진 카드들 - 2) set타입으로 탐색 - 464ms
M = int(input()) # 확인 카드 수
checks = list(map(int,input().split())) # 확인 카드들

print(' '.join('1' if check in cards else '0' for check in checks))

전체코드

# https://www.acmicpc.net/problem/10815
# 숫자카드
# 실버5

'''
문제
숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 가지고 있는지 아닌지를 구하는 프로그램을 작성하시오.

입력
첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다. 두 숫자 카드에 같은 수가 적혀있는 경우는 없다.

셋째 줄에는 M(1 ≤ M ≤ 500,000)이 주어진다. 넷째 줄에는 상근이가 가지고 있는 숫자 카드인지 아닌지를 구해야 할 M개의 정수가 주어지며, 이 수는 공백으로 구분되어져 있다. 이 수도 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다

출력
첫째 줄에 입력으로 주어진 M개의 수에 대해서, 각 수가 적힌 숫자 카드를 상근이가 가지고 있으면 1을, 아니면 0을 공백으로 구분해 출력한다.

예제 입력 1 
5
6 3 2 10 -10
8
10 9 -5 2 3 4 5 -10
예제 출력 1 
1 0 0 1 1 0 0 1
'''

# 카드는 모두 유니크

# 초기 - 이진탐색 - 목표값(해당카드 숫자)탐색
# 112912KB 2976ms 745B
import sys
input = sys.stdin.readline
'''

N = int(input()) # 가진 카드 수
cards = list(map(int,input().split())) # 가진 카드들
M = int(input()) # 확인 카드 수
checks = list(map(int,input().split())) # 확인 카드들
'''
N = 5
cards = [6, 3, 2, 10, -10]
M = 8
checks = [10, 9, -5, 2,3, 4, 5, -10]

cards.sort() # 이진탐색 전 정렬
answer = []

for check in checks:
    s = start = 0 # 최소 index 
    e = end = N-1 # 최대 index
    while s <= e:
        mid = (s + e)//2 # 목표인덱스
        if cards[mid] > check: # 목표숫자보다 크다면 인덱스 낮추기
            e = mid - 1
        elif cards[mid] <= check: # 목표숫자보다 작다면 인덱스 높이기
            s = mid + 1

    answer.append('1' if cards[e] == check else '0') # 판별결과 저장
print(' '.join(answer))


# 풀이(1) - set - 탐색속도 더 빠름
# 125204KB 664ms 312B
import sys
input = sys.stdin.readline

N = int(input()) # 가진 카드 수
cards = set(map(int,input().split())) # 가진 카드들
M = int(input()) # 확인 카드 수
checks = list(map(int,input().split())) # 확인 카드들

for check in checks:
    print(1,end=" ") if check in cards else print(0,end=" ") 


# 풀이(2) - set+join  - 탐색속도 더 빠름
# 125640KB 464ms 297B
import sys
input = sys.stdin.readline

N = int(input()) # 가진 카드 수
cards = set(map(int,input().split())) # 가진 카드들
M = int(input()) # 확인 카드 수
checks = list(map(int,input().split())) # 확인 카드들

print(' '.join('1' if check in cards else '0' for check in checks))

issue

코딩테스트 문제를 푸는 중, 유니크한 요소를 갖는 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) 확인(=존재유무확인) 등을 위한 용도로 주로 사용됩니다.

-by 뤼튼-

결론

타입	데이터 구조 구현	탐색 알고리즘	용도	특징
Set	Hash Table	해시 함수&버킷	포함여부만 확인할 경우	중복값 제거 요소 오름차순 정렬 index 접근 불가
List	Array	완전탐색	index 접근 필요할 경우	index 접근 가능

해당 값이 그룹에 존재하는가 확인하는 '멤버십(Membership) 확인' 의 경우에는 set이 더 유리하다.

<정적배열과 동적배열>

일반적으로 Array는 정적 배열(Static array)을 의미하며
연속된 메모리 공간에 동일한 타입과 크기의 요소들을 저장하여, index탐색에 유리한 점이 있다.

하지만 Python에서의 List는 동적 배열(Dynamic array)로, 다양한 타입과 크기의 요소들을 저장하며 index탐색도 가능하다. 단, 요소의 삽입/삭제 등 추가 작업을 위해 별도의 메모리 할당 및 복사 작업을 필요로 하므로 정적 배열보다는 메모리 접근이 느릴 수 있다.

참고1 참고2