[Python] "100000000000000000 in range(100000000000000001)"이 0.1초 이상 걸린다고 생각하면 들어오세요.

[※ 주의 ※] 아래를 이해하지 않고 이 글을 볼 경우, 이해가 되지 않는 부분이 있을 수 있습니다.

 

1. [Python] for문의 친구 range에 관한 모든 것

---

다음 코드를 살펴보자. 과연 이 코드를 실행하는데 얼마나 시간이 걸릴까? (앞의 숫자는 $10^{16}$, 뒤의 숫자는 $10^{16}+1$)이다.

 

print(10000000000000000 in range(100000000000000001))

 

range에 대하여 알고있다면, 이 값을 출력하면 True가 나온다는 것은 자명하다. 근데, 실제로 실행하면 얼마나 걸릴까? range문은 0부터 시작하는거니까 $10^{16}$ 까지면 정말 오래 걸릴거라 생각하기 쉽다.

 

헐! 직접 실행하여보면, 0.1초도 안되는 시간 안에 실행되는 것을 확인할 수 있다.

 

생각해보자. 애초에 실행이 되기 전에 메모리가 부족하지 않을까? 또 실행이 된다고 해도 저 많은 정수를 생성하는데 긴 시간이 걸리지 않나?

 

range에 대한 오해를 풀어보자. 왜 이게 짧은 시간 안에 가능한거지?

range에 대한 오해를 풀어보자.

---

1. Range는 Generator가 아니다.

많은 사람들이 착각하는 것 중 하나가 range는 generator의 일종이라는 것이다. for문과 붙어다니니까 range는 하나씩 원소를 내보내는 generator라는 착각을 하기 쉽다.

 

틀렸다. range는 iterator의 종류가 아니다.

 

다음과 같은 코드를 작성하고, 실행하면 다음과 같은 결과를 얻을 수 있다.

 

some_range = range(3)
print(list(some_range))
# [0, 1, 2]
print(list(some_range))
# [0, 1, 2]

 

첫 번째 print와 두 번째 print가 같은 list를 반환하는 것을 확인할 수 있다. 만약 generator의 일종이었다면, 두 번째 print에서는 빈 list가 나왔어야 한다.

---

2. Range는 Sequence다.

range에 관한 다른 포스팅을 읽었다면, range는 sequence라는 말을 기억할 것이다. 구체적으로는, 그때그때마다 sequence를 생성한다는 것이다.

 

무슨 말이냐면, range($10^{16}$)를 한다고 진짜 0부터 $10^{16}$를 한 번에 만들지 않고, 동적으로 만든다는 것이다. 0, 1, 2 ... $10^{16}$를 iteration이 진행되면서 만든다는 것이다.

 

그럼, $10^{16}$ in range($10^{16}+1$)는 언제 검사한다는 것인가?

 

사실, 'a in range(b)'를 할 때 in 은 안에 있는지 검사하는 것이 아닌, 계산을 통해 알아낸다.

 

계산 과정을 간단히 구현하여 보자. 직접 range를 new_range로 구현하여 계산 과정을 작성하면 다음과 같이 작성할 수 있다.

 

class new_range:
    def __init__(self, start, stop = None, step = 1):
        if stop is None:
            start, stop = 0, start
        self.start = start
        self.stop = stop
        self.step = step
 
        if step < 0:
            low, high, step = stop, start, -step
        else:
            low, high = start, stop
 
        self.length = 0 if low > high else ((high-low-1) // step) + 1
    
    def __contains__(self, item):
        if self.step < 0:
            if not (self.stop < item and item <= self.start):
                return False
        
        else:
            if not (self.start <= item and item < self.stop):
                return False
        return (item - self.start) % self.step == 0

 

 위와 같은 계산과정(__contains__ => in)을 거치면, 굳이 range 안의 모든 원소를 만들지 않아도 안에 원소가 포함되어 있는지 검사할 수 있다.

 

위 계산과정을 살펴보면, 거의 상수 시간 ~ 로그 시간 안에 처리할 수 있다는 것을 확인할 수 있다. 나머지 연산 부분이 가장 오래 걸리는 부분이기에, 이 부분에 따라 성능이 결정된다고 예상할 수 있다.

 

다만 간단히 구현한 것이기에, 실제 range에서의 구현과는 조금 다를 수 있다.

---

간단히 정리하자면, "100000000000000000 in range(100000000000000001)"은 range가 직접 큰 수 모두 만들지 않고 동적으로 원소를 생성하고, in을 검사할 때는 계산을 활용하기에 매우 빠른 시간안에 확인할 수 있다고 할 수 있겠다.

 

도움이 되었다면 지나가는 길에 하트 하나 눌러주세요, 양질의 글을 쓰는데 하나의 동기부여가 됩니다😍

지적이나 오타 수정 댓글 환영합니다!!