강의로 돌아가기
황태식

코드 performance 질문입니다.

index 함수에서 start parameter를 늘려가며 검색하는 방법이
slicing한 리스트에서 검색 후 이전 리스트 length를 더하는 것보다 나은 퍼포먼스를 보인다고 할 수 있나요?

작성중인 코드―solution.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def solution(L,x):
    checklist = L[:]
    res = []
    if x not in checklist:
        if len(res) ==0:
            res.append(-1)
    else:
        res_index=-1
        while True:
            try:
                res_index = checklist.index(x,res_index+1)
                res.append(res_index)
            except ValueError:
                break
    return res
1 개의 답변
이시윤

결론부터 말씀드린다면, 그렇지 않습니다.

위에 소개하신 알고리즘이 슬라이싱한 리스트에서 검색한 후 이전 리스트 길이를 더하는 것 과 (거의) 동일한 동작을 이룹니다. 즉, 코드의 시간적 성능 측면에서 차이가 없다고 보는 것이 타당합니다.

그런데, 알고리즘 외적인 측면에서 위 코드에 대한 언급을 조금 한다면, LL 4-6 은 좋지 않습니다. if x not in checklist: 의 조건을 검사하기 위해서는 Python 에서 내부적으로 checklist 라는 리스트를 한 번 처음부터 끝까지 scan 해야 합니다. (리스트가 원소의 크기에 따라 정렬되어 있다고 가정할 수 없으므로, 선형 탐색 을 할 수밖에 없는 상황입니다.) 이 검사의 실행 시간은 리스트 checklist 의 길이에 비례합니다. 결과적으로, 그 뒤 LL 7- 에서는 else 인 경우에만 실행하므로 성능 측면에서는 또다시 큰 차이를 만들지 못하지만, 논리적으로 좋은 구조는 if len(res) == 0:while 순환문 (LL 9-) 보다 뒤에 있는 것이 좋겠습니다. 만약 xchecklist 안에 없음이 처음에 (순환문 실행 이전에) 밝혀진다면 len(res) == 0 은 당연할 거구요.

또 한 가지 첨언하자면, 코드의 효율성을 논할 때에는 크게 두 가지의 측면이 있습니다. 그것들은:
(1) 알고리즘의 복잡도
(2) 코드의 구현 효율성
인데, (1) 을 훨씬 중요하게 생각합니다. 알고리즘의 복잡도는 제 6강에서 기초적으로 다루고 있습니다만, 기본적으로 입력의 크기가 증가하면 알고리즘의 실행 시간은 얼마나 빠르게 증가하느냐 를 따집니다. 예를 들어 입력 크기에 비례한다든지, 크기의 제곱 또는 세제곱에 비례한다든지, 로그 (log) 관계로 증가한다든지, 하는 것입니다. 한편, (2) 는 복잡도가 같더라도 코드를 어떻게 작성하느냐에 따라서 실행 시간에는 차이가 생길 수 있음을 얘기하는데, 이것은 같은 알고리즘을 코드로 구현한다고 하더라도 시간/공간 측면에서 더 좋거나 더 안좋은 서로 다른 코드가 존재할 수 있기 때문입니다.

다시 처음으로 돌아간다면, 위에 보인 코드는 (1) 과 (2) 의 두 측면 모두에서 최적 복잡도를 가지는 알고리즘이며 (실행시간은 리스트의 길이에 비례 - 문제 자체가 이보다 낮은 복잡도의 알고리즘이 존재하지 않는 성질을 가지고 있음), 그것은 슬라이싱을 이용하는 방법 과 동일한 성질입니다.

  • 황태식
    답변 감사합니다. 알고리즘을 많이 공부해야 할 필요성을 느꼈습니다. 황태식 2018.10.25 10:41
답변 쓰기
이 입력폼은 마크다운 문법을 지원합니다. 마크다운 가이드 를 참고하세요.