리스트 요소의 중복 제거에는 set 을 사용하자

중복 값이 들어가 있는 정수 배열이 있다고 가정합니다. 이 정수 배열에서 중복 값을 제거할 때는 망설임없이 set을 사용하는 것이 코드의 길이로도, 속도로도 가장 효율적입니다.

예제 코드를 보겠습니다.

number_list = [1,2,3,4,5,5,6,7]
unique_number_list = list(set(number_list))

그렇다면 유니크한 값을 가진 정부 배열들이 존재하고, 각 리스트의 원소들이 서로 중복되지 않도록 편집하기 위해서는 어떻게 해야 할까요? 아래와 같은 코드로 구현할 수 있습니다.

a_list = [1,2,3,4,5]
b_list = [5,6,7,8,9]

unique_a_list = [v for v in a_list if v not in b_list]
unique_b_list = [v for v in b_list if v not in a_list]

위의 두 정수 배열에는 공통으로 5라는 값이 들어가 있으며, 위의 처리의 결과로 각 리스트에 5라는 값이 제거됩니다.

그러나 이 경우, 리스트 컴프리헨션을 사용하여 중복을 제거하는 방식은, 각 요소에 대해서 중복 여부를 확인해야 합니다. 이 과정에서 리스트 요소를 하나씩 비교하게 되며, 이는 시간복잡도 측면에서 비효율적입니다.

위의 연산에서 사용되는 in 연산은 리스트의 길이가 m 일 때 O(m)의 시간복잡도를 갖게 됩니다. 따라서, a_list 와 b_list 의 모든 요소를 검사해야 하는 것의 시간복잡도는 O(n*m)이 됩니다.

set을 사용한다면?

결과적으로 set 을 사용하여 차집합을 구하는 것이 리스트 컴프리헨션을 사용하여 중복을 제거하는 것보다 효율적입니다.

set은 중복을 제거하는데 왜 효율적일까?

set은 내부적으로 해시 테이블 기반의 연산을 하기 때문에 빠릅니다. 그렇기 때문에 평균적으로 O(1)의 시간복잡도로 요소의 포함 여부를 검사하여 중복을 제거할 수 있습니다.

a_list = [1,2,3,4,5]
b_list = [5,6,7,8,9]

a_set = set(a_list)
b_set = set(b_list)

a_list = list(a_set - b_set)
b_list = list(b_set - a_set)

위 코드에서 set의 차집합 연산은 O(n)의 시간 복잡도를 가집니다. 이는 리스트의 요소 수에 비례하며, 리스트 컴프리헨션보다 훨씬 더 효율적입니다.

따라서 대규모 데이터셋에서 중복을 제거하기 위해서는 set 을 사용한 방법이 훨씬 더 효율적입니다.