N*N, N**2, pow(N, 2), math.pow(N,2)

이전에 재밌는 문제를 풀었다. 관련 내용은 아래 포스팅 참고.

1828. Queries on Number of Points Inside a Circle

 

사실 이 문제는 문제 자체가 주는 의미도 있지만, Python을 알고리즘 문제 해결에 사용하는 사람들은 한 번쯤은 생각해볼 부분이 있다.

바로 거듭제곱 연산이다.

 

Python에선 거듭제곱 연산을 할 수 있는 몇 가지 방법이 존재하고 표현을 다양하게 한다면 기본적으로 4가지가 있는 것으로 알고 있다.

1. N * N
2. N ** 2
3. pow(N, 2)
4. math.pow(N, 2)

이 4가지는 모두 N이라는 값을 제곱한 결과를 반환한다.

 

위에 있는 문제는 2차원 좌표평면의 두 점 사이의 거리를 구하는 것이 필요하고, 이때 유클리드 거리를 구하는 공식을 이용하는데 거듭제곱이 사용된다.

 

1. N * N

from typing import *


class Solution:
    def countPoints(self, points: List[List[int]], queries: List[List[int]]) -> List[int]:
        answer = []

        for query in queries:
            cx, cy, length = query
            temp = 0
            for point in points:
                x, y = point
                if (cx - x) * (cx - x) + (cy - y) * (cy - y) <= length * length:
                    temp += 1
            answer.append(temp)

        return answer

아래쪽에 if로 시작하는 라인에서 거듭제곱을 사용하고 있다.

N * N의 형태로 거듭제곱을 구현했다.

 

2. N ** 2

 if (cx - x) ** 2 + (cy - y) ** 2 <= length ** 2:

1번 코드에서 if 문만 위와 같이 변경하고 제출했는데 시간이 거의 3배 차이가 난다.

 

3. pow(N, 2)

if pow((cx - x),2) + pow((cy - y), 2) <= length ** 2:

마찬가지로 if문만 위와 같이 변경했다. 시간은 2번과 비슷하다.

 

4. math.pow(N, 2)

from math import pow
if pow((cx - x),2) + pow((cy - y), 2) <= length ** 2:

math 모듈의 pow를 이용해서 제출했다.

2, 3번보단 확실히 시간이 줄었지만 1번보단 여전히 2배 이상 느리다.

 

Why?

내부 구현 방법이 달라서 그렇다.

 

• 1번 방법은 정말로 두 개의 값을 산술 연산으로 곱하는 것이어서 A * B 하는 것과 다름이 없다. 단순 곱셈을 하는 것이다.
• 2번 방법은 3번 방법과 거의 동일한 방법이다.
  • 거의 동일한 방법이라고 표현한 것은 명령어 단계가 2번이 3번보다 한 단계 더 적기 때문이다.
  • 한 단계가 적어서 그런지 2번이 좀 더 빠르긴 하다.
• 3번 방법은 Python에 built-in 함수인 pow를 호출해서 사용한다.
  • 모든 것이 PyObject라는 객체로 되어있는 Python에서 pow를 호출하면 해당 Object에 내장되어 있는 매직 메서드인 __pow__를 호출해서 연산을 하게 된다.
  • 타입을 유지한다. 예를 들어 N이 정수라면 pow(N, 2)도 정수다.
• 4번 방법은 math 모듈의 pow를 호출해서 사용한다.
  • math 모듈은 내부에 c로 구현되어있다.
  • 그리고 입력된 값이 우선 float 형태로 캐스팅된 후 c의 연산 법으로 계산된다.
  • 위와 같은 특징으로 정수의 거듭제곱을 해도 실수로 반환된다. 그래서 math.pow를 사용하고 정수 값처럼 사용하려면 타입 캐스팅이 필요하다.

pow는 기존 입력값의 타입을 유지, math.pow는 무시하고 실수로 반환한다

결론

• 분명히 사용 방법에 따라서 속도 차이가 있고, 코드 자체도 다르기 때문에 가독성도 다르다.
• 상대적으로 차이가 나는 것이지 일반적인 적당한 크기의 수의 거듭제곱 연산은 어떤 방법을 사용해도 이것 때문에 병목이 일어날 가능성은 매우 적다.
• 추가적으로 pow(a, b, c)라는 built-in 메서드는 a를 b번 곱하고 c로 모듈로 연산을 한다. 만약에 거듭제곱하고 모듈로 연산을 해야 하는 경우는 이걸 사용하자. 이게 math.pow(a, b) % c 보다 빠르다. pow(a, b, c)는 pow(a, b)를 다 하고 모듈로 연산하는 게 아니라 덜 곱해도 결과를 반환할 수 있도록 구현되어 있기 때문이다.

 

이전에 알고리즘 공부할 때 pow를 써서 TLE가 났던 걸 N * N으로 바꿨더니 통과했던 적이 있어서 굉장히 황당했었던 적이 있는데, 황당한 게 아니라 내부 구현이 다르기 때문에 차이가 날 수밖에 없었던 것. 그때 기억이 나서 한번 정리해본다. 

 

아무튼 곱셈, 나눗셈은 필요한 경우에만 하도록 하는 것이 좋다. 덧셈, 뺄셈에 비해서 굉장히 비싼 연산이다...

 

관련해서 깊은 이해를 원한다면 아래 링크를 참고.

Difference between the built-in pow() and math.pow() for floats, in Python?

 

Exponentials in python: x**y vs math.pow(x, y)

 

Python의 큰 정수 표현법 1

3편까지 있는 걸로 알고 있다.