N*N, N**2, pow(N, 2), math.pow(N,2)
이전에 재밌는 문제를 풀었다. 관련 내용은 아래 포스팅 참고.
[1828. Queries on Number of Points Inside a Circle
Queries on Number of Points Inside a Circle - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. l..
doljae.tistory.com](https://doljae.tistory.com/199)
사실 이 문제는 문제 자체가 주는 의미도 있지만, Python을 알고리즘 문제 해결에 사용하는 사람들은 한 번쯤은 생각해볼 부분이 있다.
바로 거듭제곱 연산이다.
Python에선 거듭제곱 연산을 할 수 있는 몇 가지 방법이 존재하고 표현을 다양하게 한다면 기본적으로 4가지가 있는 것으로 알고 있다.
- N * N
- N ** 2
- pow(N, 2)
- 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?
Is there a difference in the results returned by Python's built-in pow(x, y) (no third argument) and the values returned by math.pow(), in the case of two float arguments. I am asking this question
stackoverflow.com](https://stackoverflow.com/questions/10282674/difference-between-the-built-in-pow-and-math-pow-for-floats-in-python)
[Exponentials in python: x**y vs math.pow(x, y)
Which one is more efficient using math.pow or the ** operator? When should I use one over the other? So far I know that x**y can return an int or a float if you use a decimal the function pow will ...
stackoverflow.com](https://stackoverflow.com/questions/20969773/exponentials-in-python-xy-vs-math-powx-y)
[Python의 큰 정수 표현법 1
개요 대부분의 프로그래밍 언어, 특히 거의 모든 저레벨 언어에는 정수형 크기에 제한이 있습니다. 대체로 바이트 단위로 끊어서 1바이트, 2바이트, 4바이트, 8바이트 정도의 정수형들을 사용할
www.secmem.org](https://www.secmem.org/blog/2019/06/16/python-biginteger/)
3편까지 있는 걸로 알고 있다.