python join 메서드 : string을 append 할 때 쓴다.

  python에서 string에 append를 할 때, list에 append를 하고, join 메서드를 쓰곤 합니다. (전 귀찮아서 +=을 쓰곤 했습니다.) 간단하게 알아보겠습니다.

 

---

 이 문서를 보시면 다음과 같이 정의가 되어 있습니다.

 

 iterable. 이는 반복될 수 있는 이라는 뜻을 가집니다. 그런데, 사실 이 블로그에서도 몇 번 이야기를 했습니다. 이터레이터. c++ STL 하면서 몇 번 언급을 했는데요. 순회 가능한 무언가라고 보시면 됩니다. 파이선에서는 dict, set, list와 같은 것들이 있습니다. 그러면 앞에 붙는 문자열이 어떤 역할을 하는지 보겠습니다.

 

 

 list li에 'A', 'B', 'C', 'D'가 있습니다. 2번째 줄에 '#'.join(li)가 있습니다. 결과값을 봅시다.

 

 

 A#B#C#D가 나옵니다.

 

 ''.join(li)를 하면 어떻게 나올까요?

 

 

 그냥 ABCD가 나옵니다. 조인 앞에 붙어 있는 str의 역할은 이터레이터를 돌면서 나온 요소들의 순서를 구분하기 위한 구분자 정도로 생각하시면 좋겠습니다. 그러면 이것을 어디에 써 먹을 수 있을까요? print를 10만번 해야 한다고 생각해 봅시다.

 

 

 그냥 10만번 print를 호출할 수도 있습니다.

 

 

 0.05초가 걸렸습니다. 이들을 한 번에 출력하면 어떨까요?

 

 

 구분자는 '\n'으로 해 봅시다.

 

 

 그러면, 0.023초밖에 걸리지 않음을 알 수 있습니다. 분명한 것은 동적 배열이니, 확장 연산과 같은 무거운 연산이 들어갔음에도 불구하고 print만 한 것보다는 확연히 낮은 수행시간을 보였습니다. 즉, 출력을 한번에 할 때 꽤 유용하게 쓰일 수 있습니다. append 연산을 할 때 쓰는 것도 고려해 볼 만 하고요.

 

 

---

 그러면, 이런 식으로 한 경우에, 시간 복잡도는 어떻게 될까요? 순회 (join하기 위한) 복잡도에, append 하기 위한 복잡도 2개를 고려하면 될 겁니다. 먼저, 파이선의 리스트는 동적 배열로 구성되어 있습니다. 그렇다는 이야기는 뒤에 추가하는 연산도 amortized O(1)이 보장된다는 이야기입니다.

 

 위 프로그램은 배열이 차지하고 있는 공간 크기가 바뀌었을 때에만 이전 size와 현재 size의 비율을 출력하는데요. wandbox에서 cpy 2.8과 cpy 3.8을 돌려보니 아래와 같이 나왔습니다.

 

 

 1.125. 1.5나 2보다는 작지만, 어찌 되었던 배율로 확장이 된다는 이야기입니다. 그러면, 공간 8이, 확장 되어서 공간 9가 된다는 것인데요. 1만큼의 space를 더 확장하기 위해서 어떤 일이 벌어졌나요?

 

 

 8만큼의 공간을 delete 합니다.

 

 

 그리고 새로운 공간 9만큼의 배열을 생성하고, 8만큼을 복사합니다. 삭제, 복사, 생성, 대입의 비용이 같다면, 1대입당, 25만큼의 비용을 소모합니다. 그렇지만, 25도 크지만, 어찌 되었던 상수입니다. 이것을 n회 반복해 봤자 O(n)입니다. 게다가, join은 순회 복잡도만 따지면 됩니다.

 

 list를 순회하는 데 드는 시간은 O(list 크기) 입니다. n개만큼 넣었으니 O(n)입니다. O(n) + O(n) = O(n)입니다. 실제로 그런지 확인해 보겠습니다.

 

 

 10만, 100만, 1000만번 'a'를 append 시켜 보겠습니다. 그리고 join 메서드를 이용해서 concat를 한 다음에 결과물의 len 값만 가지고 오도록 하겠습니다.

 

 

 그러면, 10만일 때 0.018초, 100만일 때 0.26초, 1000만일 때 2.6초가 걸렸다는 것을 알 수 있는데요. 10배 사이즈가 증가할 때 마다 수행시간이 대략 10배 정도 증가함을 볼 수 있습니다. 따라서, O(n) 이라고 봐도 무난합니다.