백준에서 정렬 문제를 풀다가 궁금한 점이 생겼다.
https://www.acmicpc.net/problem/1181
1181번: 단어 정렬
첫째 줄에 단어의 개수 N이 주어진다. (1 ≤ N ≤ 20,000) 둘째 줄부터 N개의 줄에 걸쳐 알파벳 소문자로 이루어진 단어가 한 줄에 하나씩 주어진다. 주어지는 문자열의 길이는 50을 넘지 않는다.
www.acmicpc.net
풀던 문제는 이 문제다.
어렵지 않은 정렬 문제다.
근데 내가 5달 전에 파이썬으로 푼 코드와 오늘 파이썬으로 푼 코드의 길이가 비슷한데 시간차이가 많이 났다.
그래서 처음에는 set.add() 로 아이템 개수만큼 추가하기 vs 리스트에 담아둔 걸 set 으로 감싸서 리스트 객체로부터 set 객체 만들기
이 방법 차이로 시간이 많이 차이 나는 줄 알았다.
근데 알고보니 빠른 입출력 적용을 안해서 시간 차이가 난거였다 🤣
5달 전에 set.add() 로 원소를 추가해서 제출한 코드 (빠른 입출력 x)
리스트에 모든 입력값을 넣고 set() 으로 감싸서 중복을 제거한 코드
빠른 입출력을 적용하고 set.add() 로 원소를 추가해서 제출한 코드
결론, 시간 차이는 크게 없다더라..
비록 오해에서 시작했지만 그래도 찾아보면서 파이썬이라는 언어의 내부까지 살펴본건 이번이 처음이라 좋은 기회라고 생각해서 정리해보기로 했다.
그리고 이 문제가 아니더라도 옛날에 문제를 풀 때 set.add() 때문에 내가 예상한 시간보다 엄청 긴 시간이 걸려서 문제를 푼 기억이 났다.
그때는 set.add() 가 O(1) 은 맞는데 상수시간이 크다 정도로만 이해하고 넘어갔던 것 같다.
사실 찾아보니 스택오버플로우에 이미 답이 있었다.
Performance comparison: insert vs build Python set operations
In python, is it faster to a) Build a set from a list of n items b) Insert n items into a set? I found this page (http://wiki.python.org/moin/TimeComplexity) but it did not have enough informatio...
stackoverflow.com
내가 답변을 보고 이해한 건
1. 시간 복잡도 이론 상으로는 두 방법 모두 n개의 아이템을 순회하므로 걸리는 시간이 O(n) 으로 똑같다.
2. list iterater 로 부터 set() 생성자로 생성하는 경우에는 C언어 레벨에서 순회가 끝난다.
3. 그런데 set.add() 메소드를 n번 반복 호출하는 경우에는 파이썬 레벨에서 함수를 호출하는 과정이 포함되어 있다.
내부적인 구현에서 함수 호출을 여러번 한다.
set 객체에 add 메소드가 있는지 점검하고, set_add 함수를 호출한다. 그리고 이 함수 내부에서 set_add_key 함수를 호출하면서 데이터를 추가한다고 한다. 이런 함수 콜 스택이 반복적으로 쌓이면서 시간 차이를 낸다고 한다.
내가 맞게 해석한거겠지..?
암튼 결론은 set.add() 를 반복적으로 하기 보다는
차라리 리스트로 다 만들고 나서 한번에 set 으로 변환해버리는게 조금 더 빠르다!
