====== 코드 작성 가이드 ====== ===== 기본 가이드 ===== * 기본적으로는 [[https://google.github.io/styleguide/pyguide.html|Google Python Style Guide]]와 [[https://www.python.org/dev/peps/pep-0008/|PEP 8 -- Style Guide for Python Code]]를 따른다 * 두 규칙이 충돌나는 부분이 있다면 Google Python Style Guide를 따른다. * 포매팅은 Black을 사용하고 pylint로 체크한다. * [[ps:Formatter]] 참고 * Google Python Style Guide에는 커스텀 버전 pylintrc 파일을 링크해두고 이것을 사용하라고 하는데, Style guide의 본문과 다르게 인덴트가 2-space로 지정되어 있다 (-_-;). Google의 내부 코딩 스타일 가이드와, 외부 공개용 스타일 가이드와의 차이때문에 꼬인것 같은데.. 외부용 가이드를 따르기로 했으니까.. pylintrc를 4-space로 고쳐서 사용한다 * ++ [폐지된 과거 가이드 (~2022/10)] | * Google Python Style Guide 에 따라서, [[https://github.com/google/yapf/|YAPF]]를 이용해서 포매팅을 시키고, pylint로 체크한다. * yapf는 내장된 구글 스타일을 지정해서 사용된다. (--style google 옵션을 붙여서 사용한다) * yapf는 assignment operator을 지원하지 않는다.. 이부분은 수동으로 처리하자 * 포맷팅이 마음에 안드는 부분들도 있긴 한데.. 그냥 시키는 대로 하자. 괜히 사소한 것에 집착해서 바꾸려고 시간을 쓰는것보다는 좀 불편해도 참는게 시간을 아끼는 길이다..(?) * 예를 들면, inner function을 정의할때, 그 위에 blank line을 한줄 추가한다. 불필요해보이고 거슬리지만 그냥 두도록 하겠다 ++ ===== 버전 ===== * BOJ기준으로 지원되는 가장 최신 버전을 쓴다. 2022년 10월 기준으로 v3.10을 쓴다. * Pypy로 내야 한다던가 할때는 지원 안되는 문법들을 수정해서 내자. 번거롭지만 빈번하지 않아서 감수할만 하다 * 파이썬의 새 메이저 버전은 10월경에 릴리즈된다. 보통 BOJ에는 다음해 1월쯤에 업데이트되곤 했다. * ++ [폐지된 과거 가이드 (~2022/10)] | * Python 3.8에서 지원되는 문법을 사용한다. (대표적으로 assignment expression) * BOJ에는 3.9에서 지원되는 문법도 사용 가능하다. (대표적으로는 graphlib) * 2020-11-16 기준, [[https://www.acmicpc.net/help/language|BOJ는 Python 3.8.2를]], 프로그래머스는 Python 3.8.5를, [[https://support.leetcode.com/hc/en-us/articles/360011833974-What-are-the-environments-for-the-programming-languages-|LeetCode는 Python 3.8 (+SortedContainer) 을]] 사용한다 * => 2021-01-08 기준, [[https://www.acmicpc.net/help/language|BOJ]]는 Python 3.9.0을 사용한다 ++ ===== 제출 언어 - Python or PyPy ===== * **[장점]** * 일반적으로 PyPy으로 제출하면 Python보다 빠른 수행시간을 얻을수 있다. Python으로 시간초과가 나는 코드도 PyPy로 제출하여 통과될 수 있다. * **[단점]** * PyPy보다는 Python으로 제출된 코드가 훨씬 더 많은데, PyPy로 제출하면 다른 코드들과의 시간 비교가 어렵다. * PyPy에서 지원하는 Python 버전은 최신 Python 버전보다 살짝 낮다. * **[결정]** * 기본적으로는 Python3으로 제출한다. Python으로 시간초과가 나는 경우에만 PyPy3으로 제출한다. ===== 기본 코드 구조 ===== * DocString / 메인함수 / 메인함수 호출부분 의 순서로 이루어진다 * 메인 함수는 => 입력 / 처리 / 출력의 순서로 처리된다. * 의무는 아니다. 한줄을 입력받으면서 바로 처리해서 출력하는 것이 편하다면 그렇게 해도 된다. * 입력은 * 주어지는 모든 값을 읽어서 변수에 그대로 저장하는 것을 기본으로 한다. * 그 입력값이 문제 푸는데 필요 없더라도 그냥 입력받는다 * 변수를 전혀 안쓸 경우에는 #pylint disable 을 써서 린트 경고를 무시한다 * 입력값을 변환해서 처리해야 하는 경우 (예를 들면 소팅), 변환 작업은 입력단계가 아닌 처리단계에서 하자. * 입력 크기에 따라서 input과 sys.stdin.readline 중 한가지를 사용한다. * 1000줄 이상이면 sys.stdin.readline, 1000줄 미만이면 input. * 입력을 받는 변수명은 문제에서 주어진 변수명을 따른다. 한글자. 대문자도 허용 * 변수명이 문제에 없으면 적당하게 지어서 쓴다. * 튜플로 받아야 할때에는 a_and_b 형태의 입력도 허용한다 * 입력을 받을때에는 2중 list comprehension을 허용한다. (구글 스타일 가이드에서는 금지되어 있지만 입력부분에서만 예외적으로 허용) * matrix = [[int(x) for x in input().split] for _ in range(n)] 과 같은 용법 * 기본적인 형태들 * 정수 N 을 입력받기 * N = int(input()) * 정수 N, M 을 입력받기 * N, M = [int(x) for x in input().split()] * 한줄에 주어지는 정수 배열 A를 입력받기 * A = [int(x) for x in input().split()] * N줄로 주어지는 정수 배열 A 를 입력받기 * A = [int(input()) for _ in range(N)] * N줄로 주어지는 정수 배열 A와 B를 입력받기 (i번째 줄에 A[i]와 B[i]가 들어옴) * A_and_B = [[int(x) for x in input().split] for _ in range(N)] * 가능하면 이쪽을 선호한다. * A, B = zip(*([int(x) for x in input().split] for _ in range(N))) * 필요에 따라 사용할수 있지만, 더 느리다. * 이 형식으로 30만줄을 입력받는 9938번 문제 기준으로 약 200ms 차이. * 특정 문자가 나올때까지 계속 입력받기 * while (line := input()) != 'X': ... * 파일 끝까지 입력받기 * for line in sys.stdin: ... * 처리는 ... * 출력은 ... ===== 입출력 ===== * 기본적으로는 input()과 print() 을 쓴다. * 입력이 크면 (대략 1000줄 이상) 이면 유의미한 속도 저하가 발생하므로 sys.stdin.readline()를 쓴다. 이 경우에 input으로는 통과가 안되는 경우도 많다. * input = sys.stdin.readline 이런식으로 단축해서 쓰지 말고, 그냥 우직하게 sys.stdin.readline()을 다 쓴다. * 줄수가 많은 것이 아니라, 한줄에 많은 글자가 있는 경우는 input()를 써도 느리지 않다. * os.read 등을 쓰면 좀더 빨라지는것 같기도 하지만 굳이 거기까지 할 필요는.. * 리스트에 담긴 내용을 여러줄에 걸쳐서 출력해야 하는 경우 print(*l, sep='\n') 으로 쓰자. * 출력해야할 줄 수가 크고 (10000줄 이상), 출력해야 할 내용이 문자열이라면, 출력할 내용을 스트링으로 만들어서 한번에 출력하자. * print('\n'.join(l)) 을 쓴다. * 여전히 간단하고, 좀더 빠르다 * 출력해야할 줄 수가 크더라도, 출력해야 할 내용이 정수라면 그냥 print(*l, sep='\n')를 쓴다. * 굳이 쓴다면 print('\n'.join(f'{x}' for x in l)) 를 쓰는 것이 가장 빠르지만, 코드가 복잡해보이고 이것때문에 AC/TLE가 걸리는 경우는 거의 없다. * 비슷한 맥락으로 다음과 같은 것들이 있지만, 이것들은 약간 더 느리다 * print(''.join(f'{x}\n' for x in l)) * print('\n'.join(str(x) for x in l)) * sys.stdout.writelines(f'{x}\n' for x in l) * 테스트. BOJ 15649번 기준 (아웃풋 약 4만개) * [[https://www.acmicpc.net/source/24243918|176ms]] - print(*p), (p가 int 튜플) * [[https://www.acmicpc.net/source/24244109|152ms]] - print(*p), (p가 스트링 튜플) * [[https://www.acmicpc.net/source/24244097|160ms]] - print(' '.join([str(x) for x in p])) (p가 int 튜플) * [[https://www.acmicpc.net/source/24243945|92ms]] - print(' '.join(p)) (p가 스트링 튜플) * 성능 테스트를 위해서 더 출력 줄수가 큰 문제가 필요하다면 [[ps:problems:boj:2751]] 으로 테스트하자. 1,000,000 개의 정수를 출력하는 문제이다. * sys.stdout.write는 print와 속도 차이가 별로 없으니 신경쓰지 말자. * [[https://www.acmicpc.net/blog/view/57|출력 속도 비교 - BOJ]] ===== DocString ===== * '''가 아니라 """를 쓴다! ==== 파일레벨 ==== * 일정한 포맷으로 모든 코드에 붙인다. * 이런 식으로 쓴다 * """Solution code for "BOJ 1932. 정수 삼각형". - Problem link: https://www.acmicpc.net/problem/1932 - Solution link: http://www.teferi.net/ps/problems/boj/1932 """ ==== 클래스/함수레벨 ==== * 라이브러리 코드에서는 1-line summary는 필수. 그 이상은 필요하면 쓰는걸로 하자. 1 line summary 에서 빈줄을 한칸 넣은 다음에 작성. * 일반 코드에서는 생략해도 상관 없다. * 1-line summary를 쓸때는 일반적으로는 클래스는 명사형, 함수는 imperative-style 형태의 동사절로 쓴다 * imperative-style ("""Fetch rows from a Bigtable.""") (PEP-257에 호환) * descriptive-style ("""Fetches rows from a Bigtable.""") ===== Type annotation ===== * 라이브러리 함수/클래스에는 필수적으로 붙인다 * 나머지 경우는 필요할 때에만 붙인다. * 구체적 사용법 * typing모듈과 collections.abc모듈 두 군데에서 모두 가져올수 있는 타입은 collections.abc모듈을 사용 * 제너레이터에 대해서는 리턴 타입을 Generator[T,None,None] 가 아닌 Iterable[T] Iterator[T]로 써주자 * [[https://docs.python.org/3/library/typing.html#typing.Generator]] 에서는 Iterable과 Iterator 두가지를 다 허용하고 있다. 다른 코드에서 Iterable을 쓰는 경우가 더 많으니 여기도 Iterable로 통일하자 * Iterable과 Iterator 둘다 가능하지만, 제너레이터에 next를 바로 적용하는 경우가 있는데, 이때 타입체커를 통과시키기 위해서는 Iterator이어야 한다. * Union[X,Y] 대신에 X|Y 로 쓴다. Optional[X]도 X|None 로 쓴다 ===== Assignment Expression ===== * https://www.python.org/dev/peps/pep-0572/ * 매우 편리하다. 사용하자 * 가끔 BOJ에서 테스트용으로 Pypy로 제출해야 할 경우가 있는데. BOJ의 Pypy 버전은 Python 3.7.4에 대응되어서, Python 3.8부터 도입된 이 기능을 인식 못한다. 그래서 런타임 에러가 나므로 깜빡하지 말자 ===== 예외처리 ===== * 파이썬은 공식적으로 [[https://devblogs.microsoft.com/python/idiomatic-python-eafp-versus-lbyl/|EAFP 스타일을 권장]]한다. 그것에 따르자 * 나쁜 코드 * if "key" in dict_: value += dict_["key"] * 좋은 코드 * try: value += dict_["key"] except KeyError: pass ===== 재귀함수 ===== * 파이썬은 재귀 깊이 제한을 넘어가면 예외가 발생한다. 보통 이 기본값은 1000으로 잡혀있고, 그보다 더 늘리고 싶으면 sys.setrecursion 을 사용할수 있기는 하지만, 실제로 얼마까지 처리가 가능할지는 플랫폼에 따라 다르다. * 가급적이면 sys.setrecursion 사용을 자제하자. 이 말은 가급적이면 재귀 대신에 반복문으로 코딩하도록 한다는 의미이다. * 상황별 분류 * DFS / 백트래킹 * teflib의 DFS 함수는 반복문으로 구현되어 있다. 이것을 그래프 탐색 / 트리 탐색 / 백트래킹(상태공간 트리에서의 탐색) 등에 모두 사용하자 * top-down DP * 코드가 매우 지저분해지거나 비효율적이 되는 상황이 아니라면 bottom-up 으로 처리하자. * 분할 정복 * 데이터를 항상 절반으로 나누는 경우는 뎁스가 로그스케일이 되므로 리밋을 넘기지 않는다. 그래서 그냥 재귀로 구현해도 상관 없다. (예: 머지소트) * 한쪽으로 치우쳐져서 나눠질수 있는 경우에는 역시 반복문으로 바꿔서 작성하자 * 그 외에도 데이터 사이즈 제한이 작아서, 재귀로 구현해도 뎁스가 1000 이하로 들어오는 문제들은, 상황에 따라 재귀로 구현해도 된다, ===== Inner function ===== * 구글 코딩 스타일의 관련 내용은 * 함수를 encapsulation 하는 용도로는 사용 금지 * 부모스코프의 변수를 클로징 하는 용도로는 허용 * 하지만, main 함수 안에 정의된 변수를 인자로 넘기기 싫다고, main 함수 안에 inner function을 만드는 것은 아무리 생각해도 나쁜짓인것 같다. * 이렇게 사용하기로 했다. * main 함수 안에서는 inner function을 정의하지 않는다. * 외부에 함수를 만들고, 번거로워도 인자들을 모두 넘겨주자. * 직접 호출이 아니라, 함수 인자로 함수를 넘겨줘야 해서 인자 갯수를 맞춰줘야 하는 경우에는 functools.partial 데코레이터를 사용하자 * 인자가 엄청 많은 재귀함수 같은 경우.. 외부에 non-rec 함수를 선언하고, 그 안에서 rec 함수를 inner function으로 선언하는것은 허용 ===== libray 코드 ===== * 라이브러리 코드에서는 속도를 위해서 가독성을 조금 더 포기하는 것을 허용한다. * 함수/클래스에 type annotation을 필수적으로 붙인다 * Docstring을 가급적 붙인다. * 첫줄에 요약. 그 아랫줄에 상세를 적는 스타일을 따른다. => import inliner 가 첫줄만 남기고 지워준다 ===== 네이밍 가이드 ===== ==== 일반적 ==== * "Number of foos" 를 표현하는 변수는 foo_count. num_foo 보다 오해의 소지가 적다. foo_cnt 는 단어의 중간 글자를 생략하지 말라는 Google style guide에 위배된다. * half-open interval 을 표현하는 변수 이름은 [beg, end) 로 통일한다. 다시 말해, 변수명이 beg, end로 되어 있다면 beg은 포함되고, end는 포함이 안된다는 의미이다. * 다른 형태의 범위 표현은 일반적으로 closed interval 를 표현한다. [first, last], [front, back], [left, right] * list나 set의 이름은 끝에 s를 붙여서 복수형으로 써준다. * 앞에 들어간 변수명이 약자여도 그냥 일반 명사인것처럼 s를 붙여준다 * index를 ind로 줄여서 썼을때, index의 리스트는 inds 로 쓴다. * position을 pos로 줄여서 쓸때, position의 리스트는 poses 로 쓴다 * set인지 list인지 표기가 필요할때는 xxx_set, xxx_list 로 쓴다 * ABC를 XYZ로 매핑하는 맵(딕셔너리)의 이름은 abc_to_xyz대신 xyz_by_abc를 사용하자. 변환하는 함수명도 convert_abc_to_xyz 보다는 create_xyz_from_abc 이런식으로. * 2차원 좌표계의 좌표를 표현할때 * 2d 그리드에서 셀의 좌표는 r,c로 표현한다 (r,c)에 해당하는 좌표는 pos 로 표현 * 2d 좌표평면의 좌표는 x,y 로 쓰자. (x,y)에 해당하는 좌표는 coords 로 표현 * 좌표평면과 그리드의 구분은, 음수 좌표를 허용하느냐 등의 차이도 있기는 하지만, 기본적으로는 아래로 내려갈때 r 또는 y값이 증가하느냐 감소하느냐의 차이로 구분한다. * 그래프에서 경로를 찾을 때, 시작 노드와 끝 노드는 source와 dest로 이름짓자. * 기각된 후보들: start/end, from/to, src/tgt, sink, target, ... * 반댓말 쌍 정리 (일반적인 통용되는 기준이 있는것은 아니지만, 내적 일관성을 위해서) * beg/end - half-open interval * first/last - closed interval * left/right - closed interval * source/dest - 탐색의 시작점과 끝점 * start/finish - 시간의 범위 * init/target - 상태의 초기값과 마지막값 * ... * 섞어서 쓰지 말자!! (start/end, start/dest, source/target 등등) * 재귀함수의 이름은 뒤에 _rec를 붙이도록 하자. 예) def dfs_rec() * 사용되지 않는 값을 저장하기 위해서 변수명으로 _ 를 사용한다 * 불리언 변수의 네이밍 * 상태를 표시하는 용도로 사용될때, 기본형은 is_XXX 이다 * is_reachable, is_visited, ... * 주어를 같이 써줘야 하는 경우에는 문장형으로 네이밍한다 * foo_is_enabled (O), is_foo_enabled (X) * 행동을 지정하는 용도로 사용될때 (보통은 함수 파라메터로 들어올 경우) 에도 가능하면 상태 표시로 써주자. * XX상태이면 YY로 동작해야 하는 경우, use_YY 대신에 is_XX를 쓰는게 좋다는 말.. * 행동 방식을 상태 표시로 표현하기 힘들 경우에는 imperative-style의 동사절으로 쓰는것 허용. * include_top_node (O), should_include_top_node (X), includes_top_node (X) * 함수 이름 * imperative-style의 동사절로 쓰자. * 동사는 상황에 따라서 적절히 만들면 되지만, 딱 떠오르는게 없으면 대충 아래에서 고르자 * 리턴값을 비용이 거의 안드는 방식으로 찾을수 있으면 (단순 테이블룩업 등), get_foo() * 주어진 범위 안에서 답을 찾아서 리턴하는 경우, find_foo() * 주어진 파라메터를 가지고 계산해서 답을 구해서 리턴하는 경우, compute_foo() * calc_foo 도 흔히 쓰이지만 compute로 통일하자 * 주어진 파라메터를 가지고 복잡한 구조의 데이터를 만들어 리턴하는 경우, create_foo() * 불리언 값을 리턴하는 함수는 is_foo() ==== PS 특화 ==== * 문제를 풀기 위한 함수를 main 밖으로 빼야 할 경우, 그 함수의 이름은 간단히 solve()로 쓰자. * 입력 처리 로직과 풀이 로직을 분리할 때, 풀이 로직을 재귀함수로 짜야 할때 등등 * 문제의 답을 저장하는 변수는 간단히 answer 로 쓰자. * 프로그래머스에서 기본적으로 쓰이는 변수명. 기각된 후보들: ans, result, res, ... * 특정 자료구조를 표현하는 변수는 자료구조 이름으로 표현하는 것이 간편하다 * stack => stack or st * queue => queue or q * deque => deq * graph => graph * tree => tree * heap => heap * disjoint set => dsu * fenwick tree => fenwick * segment tree => segtree * order statistic tree => ost * dp 결과를 저장하는 배열이나 테이블 이름은 dp로 하자 * 2차원 이상의 dp에서, 가장 최근의 행만 저장해도 충분한 경우가 있다. 예를 들어 dp[n][i] = f(dp[n-1][i], dp[n-1][i-1]) 이면 최근 두 행에 대한 배열 두개만 필요하다. 이럴때는 dp_cur, dp_prev로 한다. * 그래프에서는 대부분 * for v in graph[u] 의 꼴로 변수명을 쓸것이다 * 드물게 for successors in graph: 의 형태로 변수명을 쓸 때가 있다 * 문제의 입력값을 저장할 때에는, 문제 설명에서 제시되는 변수명을 그대로 쓴다. 대문자인 경우에는 그냥 대문자로 쓴다. * 다른 스타일 가이드의 원칙과 위배되기는 한다.. * 그러나 다른 의미있는 이름으로 변수명을 새로 만드는것 보다, 그냥 문제에 주어진 이름을 쓰는게 가장 직관적이고 이해하기 쉽다. * 대문자를 썼다고 상수로 오해받을 여지도 적다 * 입력받는 값은 모두 변수에 저장한다. 풀이에서 실제로 사용되지 않는 값, 또는 따로 변수에 저장하지 않고 바로 처리가 가능한 값도, 그냥 우선 변수에 저장해놓고 안쓰든가 다른 처리를 하든가 한다. 그게 덜 헷갈린다. * 안쓰는 변수는 옆에 # pylint: disable=unused-variable 를 적어서 lint warning을 서프레스하자. === 기타 === * LeetCode에서는 가이드에서와는 달리 메소드 이름으로 snake_case가 아닌 camelCase를 사용한다. LeetCode에 작성할 때는 일관성을 위해 새로운 메소드도 camelCase로 만든다. ===== 스타일 가이드에 있지만 잘 까먹는 것들 ===== * import는 패키지와 모듈에만 사용. 클래스나 함수단위로 import하지 않음. * 코드가 길어지고 속도도 살짝 더 느리지만 큰 차이 아니니 이렇게 하자. * from XX import YY 로 임포트한다고 해서 그냥 import 하는 라인들과 따로 그룹으로 묶지 않는다 * 이런식으로 같은 그룹으로 묶고 같이 정렬해서 import 한다 * from collection.abc import Iterable import sys from typing import TypeVar ===== 기타 코딩 스타일 ===== * 리스트에 += 보다 append와 extend를 사용 ([[https://gist.github.com/mekarpeles/3408081|약간 더 빠르다]]) * l += [x] 대신 l.append(x) * l += [x, y] 대신 l.extend([x,y]) * 튜플 or 리스트를 소팅할때, n번째 원소를 기준으로 할때는, 키로 lambda가 아닌 operator.itemgetter을 쓰자. * 좀 더 명확하고 (이건 의견이 갈릴수도..) 약간 더 빠르다. 그리고 [[https://docs.python.org/ko/3/howto/sorting.html#operator-module-functions|파이썬 공식 문서에서 추천]]하는 방법이다. * 비슷하게, namedTuple를 소팅할때는 operator.attrgetter를 사용 * 타입 체킹은 isinstance(var, some_type) 으로 한다 type(var) is some_type 보다 약간 빠르고, 상속된 타입을 체크할 수 있는 장점이 있다. * 4-space 인덴트를 넣은 블럭이 윗줄과 구분이 잘 안될때, 인덴트를 추가한다 * 이런상황이다 * if (condition1 and condition2): statement * [[https://www.python.org/dev/peps/pep-0008/#indentation|PEP8]]에서는 그냥 두기, 커멘트 넣기, 인덴트 추가하기 등의 해결책을 소개하지만 특정한 방식을 추천하지는 않는다 * [[https://www.flake8rules.com/rules/E129.html|Flake8]] 은 이것을 anti-pattern으로 간주하고 에러를 낸다. 인덴트 추가하기를 best practice로 소개한다 * yapf에서도 인덴트를 추가하는 식으로 처리한다. * 줄바꿈은 이항연산자 뒤에서 한다. * [[https://www.python.org/dev/peps/pep-0008/#should-a-line-break-before-or-after-a-binary-operator|PEP8]]에서는 새로운 코드들은 이항연산자의 **앞**에서 줄바꿈하기를 권장한다. * 나도 이항연산자의 **앞**에서 줄바꿈하는 것이 더 보기 좋다는 데에 동의한다. * 하지만 YAPF는 이항연산자의 **뒤**에서 줄바꿈을 강제한다. 그냥 그렇게 두자.. * 함수가 예외적인 상황에 놓였을 때에는 (위상정렬을 해야 하는데 주어진 그래프에 사이클이 있다든가..) return None이 아니라, 예외를 명시적으로 raise하도록 하자 * 예외를 따로 만들 필요는 없다. built-in중에서 선택하자. (아마도 대부분 ValueError) * 리스트에서 인접한 원소 두개씩을 갖고 뭘 해야 하는 경우 * (1) for i in range(1, len(l)): x, y = l[i-1], l[i] * => 기본적이지만, 안 예쁘다 * (2) for x, y in zip(l, l[1:]): * => 예쁘지만, 리스트를 복사해서 새로 만들어야 해서 비효율적 * (3) iterable, copied = itertools.tee(lst); next(copied); for x, y in zip(iterable, copied): * => 가장 효율적이지만 길다. * python 3.10부터 추가되는 [[https://docs.python.org/3.10/library/itertools.html?highlight=pairwise#itertools.pairwise|pairwise]]도 이런식으로 구현될듯 * (4) prev = l[0]; [-prev + (prev := x) for x in l[1:]] * 신박한데.. 제약이 있어서 못쓸수도 있다. * ==> 상황에 따라서 (2)나 (3)을 섞어 쓰자. 물론 python 3.10이 나오면 pairwise로 갈아탄다. * [[https://stackoverflow.com/questions/2400840/python-finding-differences-between-elements-of-a-list|관련 스레드]] * 전역 변수를 로컬 스코프에 다시 선언하는 최적화 * 한줄 요약: 마이크로 최적화는 하지 않는다. 이것도 마찬가지. * 파이썬에서는 로컬 스코프를 접근하는 것이 전역 스코프에 접근하는 것보다 빠르기 때문에, 최적화를 위해서 똑같은 변수/함수를 로컬 스코프에 다시 선언하는 경우가 있다. * "int = int" hack 라는 이름으로 [https://www.pypy.org/performance.html#micro-tuning-tips|PyPy 공식 다큐먼트]]에도 소개되어있다. 소개된 맥락은 Python에서는 유의미하지만 PyPy에서는 필요없다는 내용이긴 하지만.. * 이것은 실행속도를 살짝 줄여주기는 한다. [[ps:problems:boj:19580]] 문제는 최대 100만번의 sys.stdin.readline() 호출과, 최대 50만번의 heapq.heappop(), heapq.heappush() 호출이 필요한 문제이다. * 이 문제를 그냥 sys와 heapq를 import 하고 sys.stdin.readline()와 heapq.heappop()를 호출하도록 구현한 것을 베이스라인으로 두었다. * 이제 from heapq import heappop 으로 임포트하고, rl=sys.stdin.readline 을 글로벌에 선언해서 rl()과 heappop()로 호출하자 100ms 정도가 단축되었다. * rl = sys.stdin.readline 와 hpop = heapq.heappop 을 로컬에 선언해서 rl()과 hpop()으로 호출하자 다시 50ms 정도가 단축되었다.. * 로컬스코프과 글로벌스코프에서의 차이는 총 200만번정도를 호출해도 50ms정도밖에 차이를 안내주는것 같다 * 하지만 실행 속도 단축은 미미하다. 사용하지 말자. * 구조화된 클래스를 사용할때에는 dataclass를 쓰자 * 선택지로는 collections.namedtuple, typing.namedtuple, dataclass, 그냥 dict, 그냥 클래스, 등등이 있다. * 불가능한 경우를 제외하고는 dataclass에 slots를 켜서 사용하는 것을 기본으로 하자. 해셔블해야 하다면 frozen을 켜면 된다. * "You should avoid collections.namedtuple unless you specifically want to define a tuple" ==== 기타 코딩 스타일 (PS 특화) ==== * '무한대'는 float('inf')를 사용한다. * 상수로 정의해서 쓰자. * INF = float('inf') * 임의의 큰 값, 예를 들면 987654321이나 1e9 보다 의미가 분명하다. * math.inf도 동일하지만, math 모듈을 import 해야 하는 것이 불편하다. * 결과값을 얼마로 나눈 나머지를 출력하게 하는 문제에서의 '얼마'는 상수로 정의해서 쓴다. * MOD = 1_000_000_007 * 필요한 경우 main()함수의 첫줄에 %%sys.setrecursionlimit(10**9)%% 를 적는다. * 기본값은 1000이므로, 재귀로 풀어야 하는 웬만한 문제에서는 저 값을 새로 세팅해야 한다. 문제마다 다른 값을 적용할 필요 없이 항상 일괄적으로 %%10**9%%로 적도록 하자. ===== Idiom ===== * count_if : Iterable에서 condition을 만족하는 원소의 갯수 * 가능한 후보들 * 1) len([x for x in iterable if cond(x)]) * 2) sum(1 for x in iterable if cond(x)) * 3) sum(cond(x) for x in iterable) * 직관적인것은 1번>2번>3번 순이다. 하지만 1번은 리스트를 전부 만들어야 하니 효율성이 좀 떨어질것 같고. 2번이나 3번은 사실 둘다 비슷한데, 2번을 쓰는 코드를 더 많이 접했던 기억이고 더 익숙하다. 그리고 2번이 3번보다 좀더 빠르다 * 그러므로 2번 방식으로 쓰자. * find_first : condition을 만족하는 첫번째 원소 * next(x for x in iterable if cond(x)) * Chunking data into equal-sized groups * n = 3 x = range(n ** 2), xn = list(zip(*[iter(x)] * n)) * 출처: https://www.python.org/dev/peps/pep-0618/ * Number of element in iterable * count_if에서 condition이 따로 없는 경우이기는 하다 * 가능한 후보들 * 1) len(list(iterable)) * 2) counter = itertools.count() deque(zip(iterable, counter), maxlen=0) return next(counter) * 3) sum(1 for _ in iterable) * [[https://stackoverflow.com/questions/3345785/getting-number-of-elements-in-an-iterator-in-python|여기]] 에 따르면, 놀랍게도 리스트를 새로 만드는 1번이 가장 빠르다고 한다. 그러나 메모리 소비가 클것으로 예측된다. 메모리가 절약될것으로 생각되는 2번과 3번은 2번이 빠르다고 한다. 요약하면 아래와 같은데.. * 1) 속도 빠름 / 코드 짧음 / 메모리 많음 * 2) 속도 빠름 / 코드 복잡 / 메모리 적음 * 3) 속도 덜빠름 / 코드 짧음 / 메모리 적음 * 2번은 코드가 너무 길어서 탈락. 속도의 1번이냐 메모리의 3번이냐인데, 속도 차이가 그렇게 크지 않을것이라 생각해서 3번을 쓰기로 했다. count_if 의 idiom과도 일관성이 있다는 것도 장점,