====== Python ======

===== 몰랐던 문법과 팁들 =====

  * and와 or 는 True/False 가 아니라 마지막으로 이밸류에이트된 값을 돌려준다 ([[https://docs.python.org/3/reference/expressions.html#boolean-operations|링크]])
    * JS에서 흔히 쓰듯이, (x if x else default) 와 같은 식을 (x or default)로 줄여 쓸수 있다. 딱히 안티패턴도 아닌듯 하다.
  * int형 변수의 빌트인 메소드인 bit_length()는 부호와 선행 0을 제외하고, 이진수로 정수를 나타내는 데 필요한 비트 수를 돌려줍니다. ([[https://docs.python.org/ko/3/library/stdtypes.html#int.bit_length|링크]])
    * <code> 
>>> n = -37
>>> bin(n)
'-0b100101'
>>> n.bit_length()
6
</code>
  * enumerate에는 옵셔널한 두번째 인자 start가 있다. 두번째 인자를 주어서 enumerate(l, 5) 으로 쓰면 (5, l[0]), (6, l[1]), ...이런식으로 이터레이트한다
  * round 함수가 반올림을 하는 방법은 소수부가 0.5이상이면 올림하는 것이 아니라, '가장 가까운 정수값을 리턴' 하는 것이다. 소수부가 0.5일 때는 가장 가까운 짝수로 맞추기 때문에 예상과 달리 내림을 하는 경우도 있다!
    * ([[https://docs.python.org/ko/3/library/functions.html#round]])
    * x를 2로 나눈 값을 반올림 하고 싶은 경우, 원하는 대로 동작하지 않는 round(x/2) 대신 sum(divmod(x,2))로 쓰면 깔끔하다
  * python의 %%{정수}//{정수}%% 는 나눠진 실수값을 floor 한 결과를 돌려준다. 음수일 경우에 c언어와 다른 결과를 낸다.
    * %%-5 // 3 == -2 이라는 뜻%%
    * %%c의 나눗셈과 동일한 결과를 얻고 싶으면 x//y 대신에 int(x/y)을 쓰면 된다.%%
  * 나눈 값에 ceil을 해야 할 경우. 원칙적으로는 math.ceil(x/y) 이지만, 실수 연산을 해야 돼서 속도가 느리다
    * %%동일한 값을 얻기 위해서는 -(x // -y) 를 쓰거나, (x + y - 1) // y 을 쓸 수 있다. 전자는 위에 언급한 c와 다른 python의 // 계산 방법에 의존하기 때문에 후자보다 덜 직관적이다..%%
  * 파이썬의 자체 정수형은 이미 큰 수의 곱셈에 대해서 빠르게 동작하도록 구현되어있지만, 더욱 빠른 곱셈이 필요하면, decimal.Decimal로 변환해서 사용하면 된다. 
    * [[ps:고속 푸리에 변환]]과 [[ps:problems:boj:13277|큰 수 곱셈]] 참고 

  * type 힌트를 줄 때 자신의 타입을 레퍼해야 하는 경우를 처리 못하는 문제가 있다. 대표적으로 이렇게 쓰면 에러가 난다
    * <dkpr py> 
@dataclasses.dataclass
class Node:
    value: int
    left: Node
    right: Node
</dkpr>
    * 해결하려면 __future__,annotations 을 임포트한다
      * <dkpr py>from __future__ import annotations</dkpr>
    * 3.10부터는 디폴트로 처리될 것이라고 한다.
  * NamedTuple은 collections.NamedTuple와 typing.NamedTuple 두가지가 있다. typing.NamedTuple이 새로 추가된 거고 기능이 더 유용하니 이걸 쓰자.
  * 사소한 속도 비교..
    * for-loop 이랑 break를 쓰는것이 all()을 쓰는것보다 빠르다
      * https://stackoverflow.com/questions/49576180/all-vs-for-loop-with-break-performance
    * 비트 연산을 통한 곱하기 나누기는 빠르지 않다  
      * https://stackoverflow.com/questions/37053379/times-two-faster-than-bit-shift-for-python-3-x-integers
        * %%2를 곱할때는 그냥 x*2가 x<<1보다 빠르다. 2로 나눌때는 x>>1이 x//2보다 빠르다%%
      * https://stackoverflow.com/questions/54047100/why-are-bitwise-operators-slower-than-multiplication-division-modulo
        * %%x*8, x//8, x%8 이 x<<3, x>>3, x%7 보다 빠르다%%
  * x=y=z 형태의 assignment의 수행 순서는 c언어와 다르다. c언어에서는 대입연산자가 대입된 값을 결과로 내어주는 원리라서 x=(y=z)순서로 계산되지만, 파이썬에서는 맨 우측에 있는 값을 왼쪽값부터 순서대로 대입한다. 즉 x=z 를 수행하고, y=z를 수행하는 순서.
    * 링크드리스트 같은 것 짜다가 이것때문에 버그나면 찾기 정말 힘들다 ㅜ
    * [[https://docs.python.org/3/reference/simple_stmts.html#assignment-statements]]
  * 아이템들을 0,..,n 으로 매핑하기
    * 예를들어 names = ['abc', 'def', 'cc', 'dd'] 이런 리스트가 있을때, 저 아이템들을 0,1,2,3으로 매핑하는 테이블을 만들고 싶음
    * names가 미리 다 주어져있다면.. id_by_name = {x:i for i, x in enumerate(set(names))} 으로 만들수 있다
    * names가 계속 추가되는 상황이라면.. id_by_name = collections.defaultdict(itertools.count().__next__) 으로 만드는 기발한 방법이 있다.
 

===== 속도 최적화 vs 예쁜 코드 =====
  * **기존에 속도에 관해서 언급한 부분들은 Python 3.11 이후에는 맞지 않을 수 있으니 무시할 것. 결정 자체는 바뀌지 않는다**
    * [[Python 코드 수행시간]]
  * 파이썬에는 시간이 오래 걸릴것처럼 안보이는데 실제로는 시간이 많이 걸리는 부분들이 있다. 
  * 이런 것들을 어떤 방식으로 쓸지 정리해보자. 경우에 따라서는 가독성을 위해서 일부러 속도가 더 느린 쪽을 선택하는 것도 필요하다
  * Type annotation => 쓴다.
    * 단순히 타입 어노테이션을 쓰는것만으로 수행시간이 좀 늘어날수 있다.
    * 타입 어노테이션을 쓰기 위해 collection.abc나 typing을 임포트하게 된다면 더 많은 추가시간이 걸린다. 
      * [[Python 코드 수행시간#타입 어노테이션]]
    * 하지만 그래봐야 최대 200ms 정도이다. 이 시간를 아끼자고 타입 어노테이션을 안쓰는 것은 아닌듯 하다. 라이브러리에서는 항상쓰고, 그 외에도 필요하면 쓰자.
  * TypeAlias => 쓴다
    * 우선 Type annotation을 사용한다는 전제이다. 복잡한 타입에 대한 alias 변수를 만들때, 그 변수의 타입에 TypeAlias 표기를 해주느냐의 여부이다.
    * TypeAlias를 붙여주기 위해서는 typing을 반드시 import해줘야 하므로 100ms 가량의 추가시간이 걸린다.
    * 아주 흔히 쓰이는 Graph 타입 역시 Graph: TypeAlias = Sequence[Collection[int]] 으로 쓰여지게 되므로, dfs,bfs 등등 모든 graph 관련 문제의 수행시간이 100ms 가량 길어진다..
    * 하지만 그래봐야 인풋크기에 비례해서 커지는것도 아니고, 감수할만 하다. 라이브러리에서는 항상쓰고, 그 외에도 필요하면 쓰자.
  * List
    * l.pop() 와 del l[-1] 의 속도차이는 거의 없다 => l.pop()를 사용하자.
    * l.append(x)와 l += [x]  => l.append()를 사용.
    * l.extend([1,2,3])과 l += [1,2,3] 의 속도차이는 거의 없다. => l.extend() 를 사용하자
  * Set 
    * |=, &=, -=, ^= 대신에 update, intersection_update, difference_update, symmetric_difference_update를 사용하자. (List와 일관성을 유지하기 위해서)
  * Tuple
    * 리스트를 튜플로 바꿀때 => tuple(l) 을 쓰자
      * tuple(l) vs (*l,) 인데.. 가독성은 비슷하고, 속도는 tuple(l)이 3배정도 빠르다. (l의 길이가 작으면 거의 무의미한 차이이기는 하다)
  * functools.reduce => 사용하지 않는다.
    * 합을 구할때는 sum(), 곱을 구할때는 math.prod() 를 쓰면 된다.
    * 그 외의 경우(예를 들면 xor) 에는 functools.reduce(operator.xor, nums) 보다 그냥 루프를 돌면서 계산하는게 속도가 좀더 빠르다. 그렇다고 functools.reduce를 쓰는것이 루프를 쓰는것보다 딱히 엄청 컴팩트한것도 아니다. 그냥 루프를 쓰자
      * 11868 문제에서 reduce는 104ms, 루프는 64ms가 걸렸다
  * %% ** 연산자 => 쓸 일이 별로 없다 %%
    * 제곱근의 정수부 => math.isqrt 를 쓴다
      * %%int(n**0.5)와 math.isqrt(n) 중에서 선택. 속도 차이는 별로 신경 안써도 된다. 적어도 100,000번 이상은 이 계산을 해야 속도 차이가 미세하게 나는데 (isqrt쪽이 20%정도 빠르다) 그런 경우는 별로 없었기에.. 그냥 보기에 예쁜걸로 하자. math.isqrt(n)이 좀더 의도를 명확히 하는 느낌이니 이쪽으로 사용하자 (import math가 번거롭지만 감수하자)%%
    * 제곱근 => 역시 math.sqrt 를 쓴다
      * %%n**0.5와 math.sqrt(n) 의 차이인데.. 우선 이경우는 n**0.5쪽이 미세하게 빠르다. 하지만 일관성을 위해 math.sqrt(n)을 쓰자.%%
    * 제곱 => x*x를 쓴다
      * %% x**2 보다 x*x 가 많이 빠르다. 연산이 한번 더 들어가서 (a-b)**2 꼴이 되더라도 (a-b)*(a-b)가 더 빠르다. %%
    * n승 => 필요하면 써야지..
      * 이때는 필요하면 쓰겠지만.. n이 커지면 보통 모듈러를 취해야 할 경우가 많을텐데. 그러면 아마 pow(x, n, MOD)를 쓰게되지 않을까.. 
  * enumerate
    * 일반적인 경우 => 당연히 가능한 사용한다.
    * zip과 함께 쓸 경우 => 사용하지 않는다
      * enumerate(zip(list1, list2)) 이런식으로 쓰고 싶을때가 가끔 있는데. 그때는 그냥
        * for i, (x1, x2) in enumerate(zip(list1, list2)): ...    이것보다는
        * for i, x1, x2 in zip(range(n), list1, list2)): ...     이거를 쓴다.
        * 코드도 짧고 속도도 후자가 빠르다. ([[https://www.acmicpc.net/source/49155672|전자 코드]] 1508ms vs [[https://www.acmicpc.net/source/49155840|후자 코드]] 1200ms)
  * itertools.count  
    * c++에서의 for(int i=1; cond(i); ++i) {doSomething();} 에 대응되는 용법으로 사용되는 경우. => 사용한다
      * 이 경우에 파이썬에서 대체가능한 후보는 크게 3가지이다
        * itertools.takewhile 같은 방법은 후보에도 껴줄수 없다;
      * 1) while-loop
        * <dkpr py>
i = 1
while cond(i):
  do_something()
  i +=1
</dkpr>
      * 2) for-loop with range
        * <dkpr py>
for i in range(MAX):
  if not cond(i):
    break
  do_something()
</dkpr>  
      * 3) for-loop with itertools.count
        * <dkpr py>
for i in itertools.count():
  if not cond(i):
    break
  do_something()
</dkpr>  
      * 속도 측면에서는 2,3,1 순으로 빨랐다.
      * 코드의 예쁜정도에는 장단점이 있다.
        * (1)은 변수를 루프 밖에서 선언해야 한다는 점. do_something()에 해당되는 부분이 길어지면 루프변수를 증가시키는 부분이 루프 초기화 부분과 멀어져서 눈에 잘 안띈다는점이 감점 요인이다.
        * (2)는 MAX에 해당하는 값을 로직마다 다르게 잡아줘야 하고, 때로는 그값을 잡는게 어려울수도 있다는 점. 코드만 봐서는, MAX값에 도달하기 전에 반드시 종료조건을 만족하는 i가 등장한다는 것이 드러나지 않는다는 점이 감점요인.
          * MAX를 sys.maxsize 나 뭔가 무한대의 느낌을 주는 값으로 일정하게 쓰는 방식으로 위의 단점들을 커버할수 있긴 한데.. 그러면 다른 단점들이 생긴다;;
        * (3)은.. itertools.count가 좀 생소하게 보일수 있다는 점과, import하는게 귀찮다는 점이 감점요인.
      * 종합한 결론: (3)을 쓰자. 그래도 이게 제일 의도를 명확하게 드러내준다. (2)에 비해 속도가 느린것을 감수할정도로.
         * MAX에 도달해서 끝나는 상황이 가능한 경우.. 즉, cond(i)가 i<X and f(i) 이런식인 경우에는 당연히 range를 쓴다
         * cond가 루프변수에 무관한 상황에서, 루프가 몇번 돌았는지 확인하는게 주된 목적인 경우에는 억지로 카운트 변수로 for루프를 돌리는것보다 그냥 while 루프를 쓰는게 맞다.
           * <dkpr py>
count = 0
while cond():
  count += 1
  do_something()
</dkpr>
  * divmod => 여간해서는 쓰지 말자.
    * %%놀랍게도 // 와 % 을 각각 하는것보다 느리다. (펑션콜 오버헤드때문에). n이 매우 커지면 divmod쪽이 빨라진다고 한다%%
      * https://stackoverflow.com/questions/30079879/is-divmod-faster-than-using-the-and-operators
    * 이것을 쓰는 쪽이 가독성이 매우 좋아질 경우에만 쓰도록 하자. 그런데 그런 경우는 거의 못봤다..
  * class
    * %%__slots__%% => 사용하자
      * 자주 접근하는 멤버변수라면 접근 속도면에서 이득이 있고, 메모리도 줄어든다고 하고, 안쓸 이유가 없다.
    * xxx = self.xxx 트릭 => 비사용
      * 어트리뷰트 룩업 시간을 줄이기 위한 트릭인데.. slots를 사용한 상태라면 속도면에서 큰 이득이 없다.
  * 삼항연산자
    * a if cond else b => 이 형태로 쓴다.
    * (b,a)[cond] 는 보기에 매우 불편하다.
  * map, filter => 기본적으로 비사용
    * 기본원칙은 list comprehension / generator expression으로 통일하는것.
    * map을 쓰기 위해서 lambda 함수를 만들어야 하는 경우에는 원칙에 예외가 없다.
    * lambda없이 사용할 때에는, map이 더 빠른 경우가 있기는 하다.. => 라이브러리 코드에서만 허용하자. 
      * 예를 들면 dot-product를 구할때에 map 버전이 빠르다. [[ps:problems:boj:1533]] 기준, 472ms vs 788ms.
        * sum(map(operator.mul, x_vec, y_vec))    => 가장 빠르다
        * sum(x*y for x,y in zip(x_vec, y_vec)) 
        * sum([x*y for x,y in zip(x_vec, y_vec)]) => 가장 느리다
  * functools.cache => 사용하자
    * Top-down으로 재귀적으로 DP를 계산할때 메모이제이션을 간단하게 처리해주는 데코레이터이다.
    * 그냥 dict를 이용해서 table을 직접 만들어서 메모이제이션을 처리해주면 조금 더 빠르기는 한데.. 그렇게 큰 차이는 안난다.
      * [[ps:problems:boj:17613]]기준으로 268ms vs 296ms (python 3.11)
    * 속도차이가 크지 않고, 코드가 많이 깔끔해지므로 라이브러리를 사용하자.
  * min, max => 가급적 사용
    * 인자가 두개인 경우에는 if문과 비교연산자로 바꿀수 있고, 인자로 iterable가 들어오는 경우에는 for loop으로 바꿀수 있다.
    * 두경우 다 min 함수를 안쓰고 구현하는 쪽이 더 빠르다. 하지만 함수를 쓰는편이 코드상으로는 당연히 더 컴팩트하다
    * 기본적으로는 웬만하면 min 함수를 사용하는 것으로 한다.
    * a = min(a, b) 와 같은 코드의 경우 if b<a: a= b 로 풀어쓰는 쪽이 속도가 상당히 빠르다. 이 부분이 많이 반복된다면 if문으로 써도 된다. 라이브러리 코드에서도 이경우에는 if를 쓰자.
      * 횟수가 10만번만 되어도..
    * m = min(a,b) 같은 경우에도 m = a if a<b else b 로 풀어쓰는 쪽이 속도가 꽤 빠르다. 이 부분이 많이 반복된다면 if문으로 써도 된다. 라이브러리 코드에서도 이경우에는 if를 쓰자.
    * 리스트에서 최솟값을 찾는 m=min(l) 같은 경우는 웬만하면 이대로 쓰자
    * 리스트의 원소에서 변형된 값의 최솟값을 찾을때에는 min을 쓰는 것에도 몇가지 방법이 있다.
      * 1) min(f(x) for x in l)
      * 2) min([f(x) for x in l])
      * 3) f(min(l, key=f))
      * f가 깔끔하게 나오는지 람다함수로 만들어줘야 하는지에 따라 다르기는 한데..
      * 그냥 튜플의 리스트들에서, 각 튜플의 x번째 값들중 최솟값을 찾는것 같은 경우에는
        * 그냥 루프를 직접 짜는게 제일 빠르고, 그 다음은 min(l, key=operator.itemgetter(1))[1], min([y for x,y,z in l]), min(y for x,y,z in l) 순으로 빠르다

  * consider using in 
    * [[https://pylint.readthedocs.io/en/latest/user_guide/messages/refactor/consider-using-in.html]]
    * 예쁜 코드: a in (x, y) 또는 a in {x, y}
    * 빠른 코드: a == x or a == y 
    * 결정
      * a == x or a == y 
      * pylint 는 디폴트로 서프레션시키자.
      * {x, y, z}가 픽스되어있고, 원소가 3개 이상이면 in을 쓰는 쪽이 빠르다. 이때는 a in s 를 쓰자




===== idiom =====
  * 두개의 정렬된 리스트를 머지하기
    * <dkpr py>
merged_list = list1 + list2
merged_list.sort()
</dkpr>
    * 원래 머지를 위해서 제공되는 라이브러리함수는 heapq.merge이다.
      * 여러 리스트를 병합할수 있고, 이터레이터를 리턴해준다. 여러 리스트를 힙에 저장해서 갖고 있기 때문에, 리스트가 2개밖에 없을때에는 투머치다..
    * 그냥 리스트 두개를 합친 다음에 정렬하는 것이 더욱 빠르다
      * 파이썬의 timsort가 이렇게 거의 정렬된 데이터에 대해서는 O(n)에 가깝게 동작하기 때문이다
      * [[https://earthly.dev/blog/python-timsort-merge/]]에 따르면 합친 리스트의 길이가 100만 이하라면 그냥 소트를 쓰라고 한다

===== 버전별 추가 피쳐 =====
  * v3.8
    * Assignment expression
    * f'{expr=}'
    * pow(x, -1, mod)
    * math.perm, math.comb
    * math.isqrt

  * v3.9
    * graphlib
    * @cache

  * v3.10
    * Structural Pattern Matching
    * Advanced Type Hint
      * list[int] style (= typing.List[int])
      * int | str style (= typing.Union[int, str]) 
    * zip(..., strict=x)
    * bisect.bisect(..., key=x)
    * itertools.pairwise
    * @dataclasses.dataclass(..., slots=xxx)

  * v3.11
    * Faster python이 적용됨
    * Self 타입