전체 글
-
해시 테이블(해시 맵)자료구조 2021. 1. 22. 01:09
정의 - 해시 테이블 또는 해시 맵은 키를 값에 매핑할 수 있는 구조인, 연관 배열 ADT를 구현 하는 자료구조이다. 특징 - 대부분의 연산이 분할 상환 분석에 따른 시간 복잡도가 O(1)이기 때문에 데이터 양과 관계없이 빠른 성능 기대 가능 해시함수 - 임의 크기 데이터를 고정 크기 값으로 매핑하는데 사용할 수 있는 함수 - 사용되는곳: 체크섬, 손실 압축, 무작위화 함수, 암호 위 그림은 해시 함수를 통해 키가 해시 값을 변경되는 과정을 도식화 한것이다. 이처럼 해시 테이블을 인덱싱하기 위해서 해시 함수를 사용하는 것을 해싱이라고 한다. 여러 해시함수들 중에서 단순하고 널리쓰이는 정수형 해싱 기법인 모듈 연산을 이용한 나눗셈 방식 하나만 살펴보자. 수식은 아래와 같다. H(x) = x mod m 여기..
-
파이썬은 왜 느릴까?언어/파이썬 2021. 1. 21. 18:05
파이썬이 왜 느린지 얘기할 때 가장 많이 듣는 얘기는 전역 인터프리터 락 즉, Global Interpreter Lock(GIL)이 아닐까 싶다. 파이썬 최초의 공식 구현체인 CPython은 개발 초기에 번거로운 동시성 관리를 편리하게 하고 Thread-safe하지 않은 CPython의 메모리 관리를 쉽게 하기 위해, GIL로 파이썬 객체에 대한 접근을 제한하는 형태로 설계했다. GIL은 하나의 스레드가 자원을 독점하는 형태로 실행된다. 지금 생각하면 정말 좋지 않은 형태이지만 CPython 개발이 시작된 것이 1994년이었으니, CPU가 하나던 당시에는 충분히 그런 선택을 할 만했고, GIL 디자인에는 아무런 문제가 없었다. 지금처럼 멀티코어가 당연한 세상에서, 하나의 스레드가 자원을 독점하는 형태로 ..
-
우선순위 큐언어/파이썬 2021. 1. 21. 17:55
우선순위 큐는 큐 또는 스택과 같은 추상 자료형과 유사하지만 추가로 각 요소의 '우선순위'와 연관되어 있다. 스택은 가장 나중에 삽입된 요소를 먼저 추출(LIFO), 큐는 가장 먼저 삽입된 요소를 먼저 추출(FIFO) 한다. 그러나 이와 달리 우선 순위 큐는 어떠한 특정 조건에따라 우선순위가 가장 높은 요소가 추출되는 자료형이다. 대표적으로 최댓값 추출을 들 수 있는데, 예를 들어 큐에 [1, 4, 5, 3, 2,] 가 들어 있고 최댓값을 추출하는 우선순위 큐가 있다고 가정하자 이 경우 항상 남아 있는 요소들의 최댓값이 우선순위에 따라 5, 4, 3, 2, 1 순으로 추출 된다. 이는 정렬 알고리즘을 사용하면 우선순위 큐를 만들 수있다는 의미이기도 하다. n개의 요소를 결정하는데 S(n)의 시간이 소요된..
-
yield언어/파이썬 2021. 1. 20. 00:11
yield 키워드를 알기위해서는 Generator 를 이해해야 한다. Generator는 Iterator를 생성해주는 함수이다. Iterator는 클래스에 __iter__, __next__ 메소드를 구현해야 하지만 제너레이터는 함수안에서 yield라는 키워드만 사용하면 끝이다. 함수 안에서 yield를 사용하면 함수는 제너레이터가 되며 yield에는 값(변수)을 지정한다. 그렇다면 Generator는 왜 사용할까? 만약 숫자 1억개를 만들어내 계산하는 프로그램을 작성한다고 하자., 이경우 제너레이터가 없다면 메모리 어딘가에 만들어낸 숫자 1억 개를 보관하고 있어야 한다. 그러나 제너레이터를 이용하면 단순히 제너레이터만 생성해두고 필요할때 언제든 숫자를 만들어 낼 수 있다. 만약 1억개중 100개 정도만 ..
-
원형 큐(Circular Queue)언어/파이썬 2021. 1. 18. 23:26
원형큐는 FIFO 구조를 지닌다는 점에서 기존의 큐와 동일하다. 그러나 마지막 위치가 시작위치와 연결되는 원형 구조를 띠기 때문에 링 버퍼 라고도 부른다. 기존의 큐는 공간이 꽉 차게 되면 더 이상 요소를 추가할 수 없었다. 심지어 앞쪽에 요소들이 deQueue()로 모두 빠져서 충분한 공간이 남게 돼도 그쪽으로는 추가할 수 있는 방법이 없다. 그래서 앞쪽에 공간이 남아 있다면 이 그림처럼 동그랗게 연결해 앞쪽으로 추가할 수 있도록 재활용 가능한 구조가 바로 원형 큐이다. 원형큐의 삽입과 삭제 원리는 위의 그림과 같다. 동작하는 원리는 투 포인터와도 비슷하다. 마지막 위치와 시작 위치를 연결하는 원형 구조를 만들고, 요소의 시작점과 끝점을 따라 투 포인터가 움직인다. 그림 처럼 enQueue()를 하게 ..
-
파라미터로 *(star)와 **(double star) 는 어떤 의미 일까?언어/파이썬 2021. 1. 18. 16:39
가끔 함수의 파라미터로 *와 ** 가 붙어있거나 list등을 인자로 넣어 줄때 function(*some_list) 같이 써있는 것을 볼 수 있다. 이것은 어떤 의미를 나타내는 것일까? 파이썬에서 *는 언팩(unpack)이다. 즉 시퀀스 언팩킹 연산자로 말 그대로 시퀀스를 풀어헤치는 연산자를 뜻하며, 주로 튜플이나 리스트를 언패킹하는데 사용한다. **는 키/값 페어를 언패킹하는 연산자 이다. 매개변수 *args 는 입력을 튜플로 변환하여 모두 받는다. 매개변수 **kwargs는 입력으로 사전형과 같은 key ,value와 같은 형태만을 입력으로 받는다. 파라미터의 변수를 모든것을 사전형처럼 받는다. *args나 **kwargs 모두 일반 파라미터와 혼용해서 사용할 수 있다. 또한 아래와 같은 방법으로도 ..
-
Pytorch에서는 왜 항상 optimizer.zero_grad()를 해줄까?머신러닝 및 딥러닝 2021. 1. 17. 19:06
바로 질문에 대한 답을 말씀드리자면 "Pytorch에서는 gradients값들을 추후에 backward를 해줄때 계속 더해주기 때문"에 우리는 항상 backpropagation을 하기전에 gradients를 zero로 만들어주고 시작을 해야합니다. 이렇게 gradients을 더해주는 방식은 RNN을 학습시킬때 매우 편리한 방식입니다. 따라서 매번 loss.backward()를 호출할때 초기설정은 매번 gradient를 더해주는 것으로 설정되어있습니다. 그렇기 때문에 학습 loop를 돌때 이상적으로 학습이 이루어지기 위해선 한번의 학습이 완료되어지면(즉, Iteration이 한번 끝나면) gradients를 항상 0으로 만들어 주어야 합니다. 만약 gradients를 0으로 초기화해주지 않으면 gradie..
-
Batch Normalization은 왜 사용하는 것일까?머신러닝 및 딥러닝 2021. 1. 17. 16:03
1. training을 빠르게 해준다. 처음 그대로 입력을 넣으면 height의 경우는 분포의 범위가 상당히 조그마하기 때문에 age에 비해 상당히 가파른 것을 알 수 있다. 이 경우 가장 optimal한 point로 가기위해서는 상당히 미세하게 조정해야 하는 것을 알 수 있다. 하지만 height와 age의 평균이 0 이고 분산이 1인 분포로 만들게 되면 age와 hegiht의 분포가 비슷해지기 때문에 더 큰 lr을 가지고도 학습을 진행해도 optimal값에 들어가는데 지장이 없어서 이 경우 더 빠르게 수렴한 다라는것을 직관적으로 알 수 있다. 2. 초기 가중치의 중요도를 낮춘다. 앞서 설명했던 예시 처럼 데이터의 분포가 비슷하니 optimal 한 값에 더욱 잘 찾아가고 이 말은 학습이 더 원활하게 되..