에라토스테네스의 체는 $O(nlog(logn))$의 시간 복잡도를 가지는 알고리즘으로, 효율적으로 소수(Prime Number)를 구할 수 있다. 소수: 1과 자기 자신 만을 약수로 가지는 수 아이디어는 간단하다. 자연수 N이 있을 때, N의 배수는 소수가 아니다. 소수는 1과 자기 자신만을 약수로 가지는데, N의 배수는 N을 약수로 가지기 때문이다. 소수의 정의를 생각해 보면 당연한 이야기이다. 1 ~ 100까지의 수가 있는 표를 만들자. 그리고 만약 소수가 아니라면 표에서 값을 지운다. 0과 1은 소수가 아니다. 0 1 2 3 4 5 6 7 8 ... 2는 소수이다. 하지만 2의 배수는 소수가 아니다. 따라서 4, 6, 8 ... 등은 지운다. 0 1 2 3 4 5 6 7 8 ... 3은 소수이다. ..
PySet은 아주 유용한 자료구조이다. 이를 Go로 Go스럽게 구현하기 위해 CPython의 소스코드와 golang 소스코드를 살펴보았다. set과 map이 뒤에서 어떻게 작동하는지를 살펴보고 가장 합리적인 방법으로 집합을 구현해보려 한다. 문제 Python에는 집합이라는 아주 유용한 구조가 있다. set 객체는 크게 2가지 역할이 있는데, 중복 값을 제거하는 것과 빠르게 값을 탐색하는 것이다. n = [1, 3, 3, 5, 6, 3, 8] n = set(n) print(n) # {1, 3, 5, 6, 8} has_three = (3 in n) print(has_three) # True 하지만 Go는 set을 제공하지 않는다. 따라서 set과 유사하게 작동하는 객체를 만들어보려 한다. 그런데 Go를 곁들..
Python은 느리다. 그렇기 때문에 Python에 대한 이해도에 따라 코드의 성능이 크게 차이 날 수 있다. 이 번 글에서는 Python의 속도를 향상할 수 있는 방법에 대해 적어보려 한다. 이 글은 각각의 개념에 대해 상세하게 설명하지 않는다. 대신 왜 성능에 문제가 발생하고, 어떻게 해결할 수 있는지에 초점을 두고 작성하였다. JIT 활용 내장 함수 활용 Generator로 메모리 아끼기 for / while보다 빠른 반복 dictionary와 set으로 조회 내장 모듈의 자료구조 빠르게 문자열 합치기 빠른 입출력 global 참조 피하기 dot 줄이기 불필요한 연산, 호출 줄이기 Python은 간결하고 명확한 코드 작성을 지향한다. 위 방법 중 일부 표현은 파이썬스럽(Pythonic)지 않을 수 ..
자료의 공간 확보: Slice, Map에 cap 설정하기 빠른 입력: 입력 방식 변경으로 속도 17x 이상 향상 문자열 합치기: Builder를 이용해 속도 71x 이상 향상 정규 표현식: 직접 구현으로 속도 2.6x 이상 향상 함수 인라인 ( < v1.17) 자료의 공간 확보 s := make([]int, 100) // 슬라이스, len: 100, cap: 100 s[i] = val // 값 대입 s := make([]int, 0, 100) // 슬라이스, len: 0, cap: 100 s = append(s, val) // 값 대입 Slice를 생성할 때, 해당 Slice에 저장될 값의 범위를 알 수 있다면 미리 메모리에 공간을 확보하는 것이 유리하다. make는 slice의 형식을 입력받은 후, l..