list vs set 멤버십 속도 차이 비교 (리스트 vs 집합 누가 빠를까?)

리스트에서 요소가 있는지 종종 확인하는(멤버십) 코드를 작성합니다.

nums = [1, 3, 5, 7, 9]
if 3 in nums:
	print('3 is in nums')

 

집합(set) 또한 멤버십 코드를 작성할 수 있습니다.

리스트와 동일하게 in 코드를 사용합니다.

 

그런데 궁금합니다.

누가 더 빠를까요????

 

리스트는 배열처럼 사용하기 때문에 직관적으로 집합보다 더 느릴 것 같네요.

 

결론적으로, 멤버십의 시간 복잡도는

리스트는 평균적으로 O(n), 집합은 O(1)의 시간 복잡도를 갖습니다.

 

집합 자료구조는 해싱 구조를 갖습니다. 이것이 리스트와 다르게 속도 차이를 가져 옵니다.

Set in Python 
can be defined as the collection of items. In Python, these are basically used to include membership testing and eliminating duplicate entries. The data structure used in this is Hashing, a popular technique to perform insertion, deletion and traversal in O(1) on average. The operations on Hash Table are some what similar to Linked List. Sets in python are unordered list with duplicate elements removed. 

출처 : https://www.geeksforgeeks.org/internal-working-of-set-in-python/

 

그래..집합이 더 빠른지는 알겠어..

그럼 얼마나 빠른거지??

 

테스트 코드 작성을 통해서 확인해 보겠습니다.

 

코드 설명:

- n개의 정수형 리스트를 생성

- 생성된 리스트를 랜덤하게 한 번 섞음

- 전체 샘플의 1/10의 샘플을 랜덤하게 멤버십 테스트를 수행

- 멤버십 테스트 수행에 걸린 시간을 출력

- 동일한 위 동작을 집합에도 적용하여 시간을 출력

import random
from datetime import datetime

def test_membership(nums):
    sample_count = len(nums) // 10
    samples = [random.randint(0, len(nums)) for _ in range(sample_count)]

    start_time = datetime.now()
    count = 0
    for n in samples:
        if n in nums:
            count += 1
    print(f'멤버 카운트 : {count}')

    elapsed_time = datetime.now() - start_time
    print(f'소요 시간 : {elapsed_time.microseconds:,} us')


if __name__ == "__main__":
    for sample_count in [1000, 3000, 5000, 10000, 30000, 50000]:
        print(f'\n총 샘플 수 : {sample_count}')
        nums = list(range(sample_count))
        random.shuffle(nums)

        print('list 멤버십 테스트')
        test_membership(nums)

        nums = set(nums)
        print('set 멤버십 테스트')
        test_membership(nums)

 

출력 결과:

- 1000개 이하의 샘플에서 멤버십 테스트는 리스트, 집합 모두 0에 가까운 시간이 발생 했습니다. 차이가 없다는 것이죠

- 3000개 샘플이 넘어가니 리스트는 3,003us가 걸리고, 집합은 0us가 소요되었습니다. 차이가 엄청 크게 나네요.

- 50000개 샘플이 넘어서야 집합은 1,002us 시간이 소요되네요.  이에 반해 리스트는 510,370us 소요 되었습니다. 단순히 산술적으로도 510배는 집합이 리스트보다 멤버십 테스트에서 월등한 성능을 보여줍니다.

총 샘플 수 : 1000
list 멤버십 테스트
멤버 카운트 : 99
소요 시간 : 0 us
set 멤버십 테스트
멤버 카운트 : 99
소요 시간 : 0 us

총 샘플 수 : 3000
list 멤버십 테스트
멤버 카운트 : 300
소요 시간 : 3,003 us
set 멤버십 테스트
멤버 카운트 : 300
소요 시간 : 0 us

총 샘플 수 : 5000
list 멤버십 테스트
멤버 카운트 : 500
소요 시간 : 10,009 us
set 멤버십 테스트
멤버 카운트 : 500
소요 시간 : 0 us

총 샘플 수 : 10000
list 멤버십 테스트
멤버 카운트 : 999
소요 시간 : 39,036 us
set 멤버십 테스트
멤버 카운트 : 1000
소요 시간 : 0 us

총 샘플 수 : 30000
list 멤버십 테스트
멤버 카운트 : 2999
소요 시간 : 413,375 us
set 멤버십 테스트
멤버 카운트 : 3000
소요 시간 : 0 us

총 샘플 수 : 50000
list 멤버십 테스트
멤버 카운트 : 5000
소요 시간 : 510,370 us
set 멤버십 테스트
멤버 카운트 : 5000
소요 시간 : 1,002 us

종료 코드 0(으)로 완료된 프로세스

 

 

결론,

- 데이터 수가 1000개 이하면 리스트든 집합이든 멤버십에 소요시간의 차이가 없다.

- 데이터 수가 많아지면 많아질수록 집합이 멈버십 테스트에 훨씬 빠른 속도를 보여준다.

- 데이터 수가 적으면 리스트, 많으면 집합을 사용하자.