코루틴과 Task에 대한 내용을 발행했었는데 이 부분은 사실 asyncio에 대한 총정리 글에 포함되는 내용이었던 관계로, asyncio 에서 사용되는 세 가지 대기 가능 객체인 Task, Future, Coroutine 의 차이에 대해서 설명하는 내용으로 수정합니다.
asyncio는 비동기 처리를 위해 비동기 코루틴을 만들고 이를 스케줄링하여 실행하는 기능을 중심으로 구성되어 있다. 그런데 관련 함수를 찾아보면 어떤 것은 코루틴, 또 어떤 것은 Task나 Future로 표현하며 섞어 쓰는 것 같기도 해서 혼란스러운 점이 있다. 이 글에서는 코루틴과 asyncio.Task, asyncio.Future 가 각각 어떻게 다른지 살펴보도록 하겠다.
더 보기 »Task, Future, Coroutine참고 : http://en.wikipedia.org/wiki/Permutation#Generation_in_lexicographic_order 사전식 순열 생성 함수 어떤 원소들의 순열을 구하는 많은 알고리듬이 있다. 파이썬의 itertools 모듈은 순열, 조합 생성을 하는 permutations(), combinations() 등의 함수를 제공한다. 이 블로그에서도 이 외에 특정한 집합에 대해 N 번째 순열을 구하는 문제도 다뤄본 적이 있다. 오늘은 특정한 수열이 주어졌을 때, 해당 수열의 원소들로 구성되는 사전식 순열에서 다음 번 순열을 구하는 문제를 생각해보자. 사전식 순열이란 특정 집합의 원소들로 이루어진 모든 순열을 정렬하여 순차적으로 나타내는 순열을 말하는 것이다. 예를 들어 [1,2,3,4]는 오름차순으로 정리되어 있으므로 사전식 순열에서는… 더 보기 »사전식 순열의 다음 항 구하기 (파이썬)
코딩도장에서 흥미로운 문제를 하나 봤는데, 어떤 문자열에서 짝수번째로 등장한 숫자만 *로 치환하는 문제였다.문제의 출처가 정규식 관련 사이트인 것 같은데, 원본 주소는 링크가 깨진관계로… 예를 들자면 a1b2c3d4~e5f_6 과 같은 문자열이 있을 때 이중 숫자는 1, 2, 3, 4, 5, 6인데 그 중에서 짝수 번째로 등장하는 숫자만 *로 치환하는 것이다. 파이썬 구현은 매우 쉬운데…. def unvailEveryOtherDigits(str): s = [] occ = 0 for c in str: if c in "0123456789": c += 1 if c % 2 == 0: s.append('*') else: s.append(c)… 더 보기 »정규식으로 짝수번째 숫자만 치환하기
셸 정렬은 정렬 방법의 원리로만 보자면 “분할 증분 정렬”(diminishing incremental sort)이라고도 불리는 방법이며, 굉장히 오래된 정렬 알고리듬 중 하나이다. 이 정렬 방법은 삽입 정렬을 근간으로 하면서 삽입 정렬의 성능을 간단한 아이디어로부터 크게 증가시키는 방법이다.
삽입 정렬은 왼쪽에 있는 원소부터, 그 원소가 이동할 수 있는 ‘가장 왼쪽 자리’에 그 값을 삽입하여 정렬해 나가는 방식이다. 이 때 ‘삽입’을 위한 공간을 만들기 위해 원래자리부터 삽입될 자리 사이의 값들이 하나씩 오른쪽으로 이동해야 한다. 따라서 삽입 정렬은 어떤 원소가 이동해야 할 거리가 크면 클수록 효율이 떨어지며 배열이 반대로 정렬되어 있는 경우가 이에 해당할 것이다.
더 보기 »셸 정렬 (Shell Sort)기본적으로 모든 파이썬의 객체는 내부에 속성의 이름과 값을 담는 사전 객체를 하나씩 포함한다. 이는 __dict__라는 특별한 속성으로 정해져있다. 따라서 파이썬의 객체는 내부의 사전을 이용하여 속성들을 저장할 수 있고, 사전은 변경가능한(mutable) 키-값 쌍이기 때문에 런타임에 객체 인스턴스에 새로운 속성을 추가하는 것이 가능하다. 더 보기 »(파이썬) 고정 속성 클래스를 통해 메모리 최적화하기
병합정렬은 기초적인 정렬 알고리듬 중에서 널리 알려진 알고리듬 중 하나이며, 대표적인 분정복 알고리듬의 예인 동시에 재귀 알고리듬의 좋은 예이다. 이름에 ‘병합'(merge)이 들어가는 이유는 배열을 2개 혹은 그 이상의 작은 조각으로 나누고 각각의 조각을 정렬한 다음, 각 조각의 앞에서부터 가장 작은 값을 순서대로 골라서 정렬된 결과를 생성하기 때문이다.
원래의 배열을 쪼갠 각각의 조각 역시 똑같은 병합 정렬을 이용해서 정렬하는 재귀적인 동작을 수행한다. 재귀적 알고리듬의 수행 과정을 복잡하고 어렵게 여기는 사람들이 있는데, 입력과 결과에 집중하는 방식으로 바라보면 오히려 더욱 명료하고 간단하다는 것을 알 수 있다.
더 보기 »병합정렬동적 프로그래밍은 세부 계산으로 나뉘어지는 하나의 큰 문제를 세부 계산 결과를 미리 구해서 저장한 후 큰 계산의 결과를 빠르게 도출해내는 문제해결 기법이다.(이름과는 달리 프로그래밍 테크닉은 아니다.) 흔히 피보나치 수열을 계산할 때 memoization도 동적 프로그래밍의 범주로 볼 수 있다. 더 보기 »동적계획법
사실 이 포스팅은 순열을 만드는 방법에 대한 매우 비효율적인 접근에 대한 글입니다. 효율적인 순열/조합 생성 코드는 이 글을 참고하세요.
순열을 만드는 가장 간단한 방법으로는 특정 원소를 하나씩 뺀 후 배열의 나머지를 순열한 각 결과에 빼냈던 원소를 앞에 붙여준 결과를 모으는 방법이 있다. 대략의 코드는 다음과 같다.
def rec_perm(iterable):
if len(iterable) == 1:
return [list(iterable)]
result = []
for i in range(len(iterable)):
head = iterable[i]
tail = iterable[:i] + iterable[i+1:]
result += [[head] + x for x in rec_perm(tail)]
return result
이 알고리듬의 가장 큰 문제는 한 번에 모든 순열을 다 생성해서 그 리스트를 만환한다는 말이다. 만약 원소가 100개라면?1 메모리 부족으로 컴퓨터가 뻗을 수 있다. 물론 10개 미만의 연속열에 대해서는 나름 나쁘지 않은 성능을 낼 수 있다.
더 보기 »순열생성로직연구애플은 Swift가 파이썬보다 몇 십배 빠르다고 주장하고 있는데, 실질적으로는 파이썬이 더 빠른 것 같이 느껴지는 (심지어 pypy도 아니고) 경우가 너무나 많다. 물론 “어떤 언어가 더 빠르냐”는 질문만큼 바보같은 것도 없긴한데, 개인적으로는 애플이 말하는 것과 반대인 것 같은 체감이 많아서 한 번 확인해보았다. 더 보기 »Swift는 정말 파이썬보다 빠를까?
파이썬 기본 모듈인 itertools는 리스트와 같은 반복 가능한 객체에 대한 여러 연산을 위한 함수를 제공하는데, 특정한 원소들로 만들 수 있는 순열이나 조합을 구하는 함수들도 이 모듈에 포함되어 있다. 특정한 원소를 가지고 만들 수 있는 모든 순열은 itertools.permutations() 함수로, 모든 조합은 itertools.combinations() 함수로 만들 수 있다. 그 외에 중복을 포함하는 조합등을 생성하는 함수가 제공된다.
아주아주 예전에는 순열/조합을 생성하는 함수를 구현하는 것이 간단한 작업이 아니었는데, 제너레이터에서 다른 제너레이터로 결과 생성을 위임하는 yield from 문법이 생긴 이후에는 이를 아주 간단히 구현할 수가 있게 되었다. 그래서 오늘은 제너레이터를 이용해서 주어진 리스트나 튜플에서 순열 및 조합을 생성하는 제너레이터를 만드는 방법을 소개하고자 한다.