조합을 구하는 파이썬 내장함수가 있지만 (from itertools import combination) 이 함수는 리스트 조합의 결과를 반환합니다.

from itertools import combinations 



lists = [1,2,3] 
a = list(combinations(lists, 2)) 
print(list(a)) 


# [(1, 2), (1, 3), (2, 3)]


따라서 단순히 개수를 확인할 때 사용하기에는 적합하지 않습니다. 


이러한 이유로 아래와 같이 단순 개수만 반환하는 로직을 구현했습니다.

import operator as op
from functools import reduce


def nCr(n, r):
    if n < 1 or r < 0 or n < r:
        raise ValueError
    r = min(r, n-r)
    numerator = reduce(op.mul, range(n, n-r, -1), 1)
    denominator = reduce(op.mul, range(1, r+1), 1)
    return numerator // denominator

print(nCr(3, 2))


# 3


해당 로직에서 min(r, n-r)을 사용한 이유는  nCr(n,r)과 nCr(n, n-r)은 동일하기 때문에 좀 더 속도를 빨리 하고자 들어간 로직입니다. 

reduce()에서 op.mul을 사용한 이유는 https://brownbears.tistory.com/458 에 작성했습니다.

저작자표시

'언어 > 파이썬 & 장고' 카테고리의 다른 글

[Python] 조합(combination) 개수 계산하기  (0) 2019.10.13
[Python] operator 모듈 사용해서 연산 처리 속도 빠르게 하기  (0) 2019.10.13
[Python] functools 모듈의 reduce 함수 사용하기  (0) 2019.10.13
[Python] 함수 및 코드 실행시간 측정하기 (timeit 모듈 사용법)  (0) 2019.10.05
[Python] 소인수 분해, 약수 구하기  (0) 2019.09.29
[Python] 최대공약수, 최소공배수, N개의 최소공배수  (0) 2019.09.22

파이썬에서 문자열을 더하거나 숫자를 곱하는 등의 코딩을 할 때 아래와 같이 연산자를 사용하게 됩니다.

result = 'a' + 'b'
result2 = 4 * 5

여기서 파이썬 내부적으로 operator 모듈을 호출하여 처리를 한 다음 사용자에게 반환하게 됩니다. 


만약 속도가 정말 중요한 프로그램에서 연산처리를 조금이나마 빠르게 하려면 operator 모듈을 사용하면 됩니다.


아래는 100만번 반복문을 실행하면서 각 값을 곱하는 예제로 수행속도를 확인한 코드입니다.

from functools import reduce
import operator
import timeit


def test1():
    return reduce(operator.mul, range(1000000))

def test2():
    return reduce(lambda x,y: x*y, range(1000000))

def test3():
    def xy(x, y):
        return x*y
    return reduce(xy, range(1000000))

def xy2(x, y):
    return x*y
def test4():
    return reduce(xy2, range(1000000))

t1 = timeit.timeit('test1()', setup='from __main__ import test1', number=1)
t2 = timeit.timeit('test2()', setup='from __main__ import test2', number=1)
t3 = timeit.timeit('test3()', setup='from __main__ import test3', number=1)
t4 = timeit.timeit('test4()', setup='from __main__ import test4, xy2', number=1)

print(t1)
print(t2)
print(t3)
print(t4)


# 0.07717441299610073
# 0.1284205199990538
# 0.12985249999474036
# 0.1294196250019013


결과를 보면 operator 모듈의 mul을 사용해 100만번 곱한 결과가 약 60%정도 빠른 것으로 보여집니다. 

요약

속도 처리가 아주 중요한 프로그램일 경우, 연산 로직을 짤 때, operator 모듈을 사용하자

저작자표시

'언어 > 파이썬 & 장고' 카테고리의 다른 글

[Python] 조합(combination) 개수 계산하기  (0) 2019.10.13
[Python] operator 모듈 사용해서 연산 처리 속도 빠르게 하기  (0) 2019.10.13
[Python] functools 모듈의 reduce 함수 사용하기  (0) 2019.10.13
[Python] 함수 및 코드 실행시간 측정하기 (timeit 모듈 사용법)  (0) 2019.10.05
[Python] 소인수 분해, 약수 구하기  (0) 2019.09.29
[Python] 최대공약수, 최소공배수, N개의 최소공배수  (0) 2019.09.22

reduce 함수는 아래와 같은 파라미터를 받고 있습니다.

reduce(function, iterable, initializer=None)

첫 번째 파라미터는 함수가 들어가게 됩니다. 따라서 람다일 수도 있고 정의해놓은 함수가 될 수도 있습니다. 두 번째 파라미터는 계산을 하고자 하는 리스트가 들어가게 됩니다. 


아래는 reduce()의 예제입니다.

from functools import reduce


result = reduce(lambda x, y: x+y, [1, 2, 3, 4, 5])
# ((((1+2)+3)+4)+5)
print(result)

# 15


위 예제는 1,2,3,4,5 값을 전부 더한 결과를 반환합니다. 여기서 초기값 100이 존재한다고 하면 아래와 같이 reduce()에 세번째 파라미터를 지정하면 됩니다.

from functools import reduce


result = reduce(lambda x, y: x+y, [1, 2, 3, 4, 5], 100)
print(result)

# 115


reduce()는 입력 받은 컨테이너 타입(iterable)을 지정한 함수에 따라 계산한 후, 단일 값으로 결과를 반환합니다.


reduce()를 사용하여 최댓값을 구할 수 있습니다.

from functools import reduce


func = lambda a, b: a if (a > b) else b
result = reduce(func, [1, 100, 2, 55])

print(result)

# 100


저작자표시

'언어 > 파이썬 & 장고' 카테고리의 다른 글

[Python] 조합(combination) 개수 계산하기  (0) 2019.10.13
[Python] operator 모듈 사용해서 연산 처리 속도 빠르게 하기  (0) 2019.10.13
[Python] functools 모듈의 reduce 함수 사용하기  (0) 2019.10.13
[Python] 함수 및 코드 실행시간 측정하기 (timeit 모듈 사용법)  (0) 2019.10.05
[Python] 소인수 분해, 약수 구하기  (0) 2019.09.29
[Python] 최대공약수, 최소공배수, N개의 최소공배수  (0) 2019.09.22

파이썬에서는 timeit 모듈을 제공하고 있고 이 모듈을 사용하여 특정 프로젝트의 전체 실행시간이 아닌 특정 함수나 코드의 실행시간을 측정하는 방법을 소개합니다.timeit.timeit()

timeit.timeit(stmt='pass', setup='pass', timer=<default timer>, number=1000000, globals=None)

timeit 함수의 파라미터는 아래와 같습니다.

  • stmt: 실행측정할 코드 및 함수
  • setup: stmt를 실행하기 위해 사전에 필요한 코드나 함수를 선언. setup의 실행 시간은 전체 측정 실행 시간에서 제외됨
  • timer: Timer 인스턴스
  • number: 선언한 stmt의 수행 횟수. 선언하지 않으면 기본값으로 1000000번이 실행됨

예제

먼저 사용 방법 예제는 아래와 같습니다.

import timeit


t1 = timeit.timeit('"-".join(str(n) for n in range(100))', number=10000)
print(t1)


# 0.3018611848820001


위 코드를 설명하자면 반복문을 100번 돌면서 '0-1-2-.....-99' 의 문자열을 만드는 행동을 10000번 실행하는 시간을 측정합니다.

아래와 같이 콜러블을 파이썬 인터페이스로 전달할 수도 있습니다.

import timeit




t1 = timeit.timeit(lambda: "-".join(map(str, range(100))), number=10000)
print(t1)

# 0.19665591977536678


위 방법은 timeit 내부에 직접적으로 선언하여 실행하는 방법입니다. 보통 코드를 작성하게 되면 함수로 만들기 때문에 아래와 같이 선언하여 수행시간을 측정할 수 있습니다.

import timeit


def test():
    return "-".join(str(n) for n in range(100))

t1 = timeit.timeit('test()', setup='from __main__ import test', number=10000)
print(t1)


# 0.3343123300001025


만약 해당 함수를 1번만 실행한 시간을 측정하려면 number의 값을 1로 주면 됩니다.

import timeit


def test():
    return "-".join(str(n) for n in range(100))

t1 = timeit.timeit('test()', setup='from __main__ import test', number=1)
print(t1)


# 5.377409979701042e-05

timeit.repeat(stmt='pass', setup='pass', timer=<default timer>, repeat=5, number=1000000, globals=None)

repeat함수는 repeat 파라미터를 제외하고 timeit함수와 동일한 파라미터를 갖고 있습니다.

  • stmt: 실행측정할 코드 및 함수
  • setup: stmt를 실행하기 위해 사전에 필요한 코드나 함수를 선언. setup의 실행 시간은 전체 측정 실행 시간에서 제외됨
  • timer: Timer 인스턴스
  • number: 선언한 stmt의 수행 횟수. 선언하지 않으면 기본값으로 1000000번이 실행됨
  • repeat: timeit()함수를 반복으로 호출 할 수. 선언하지 않으면 기본값으로 5번이 실행

repeat()은 결과가 repeat 파라미터에서 지정한 수만큼의 크기를 갖는 리스트를 반환합니다. repeat() 함수는 파라미터에서 지정한 내용대로 반복하여 결과를 리스트로 내보내 줍니다. 실행시간은 측정할 때마다 동일하지 않고 계속 다르기 때문에 repeat()을 사용하여 평균 측정시간을 낼 때 사용하기 좋습니다.

예제

위 함수를 10번 반복하여 수행시간을 확인하는 예제입니다.

import timeit

def test():
    return "-".join(str(n) for n in range(100))

t1 = timeit.repeat('test()', setup='from __main__ import test', number=1, repeat=10)
print(t1)


# [4.4689979404211044e-05, 3.570702392607927e-05, 0.00010638800449669361, 7.007492240518332e-05, 6.197404582053423e-05, 4.9708993174135685e-05, 6.294203922152519e-05, 4.0619983337819576e-05, 3.496196586638689e-05, 3.409304190427065e-05]


아래는 10000번 실행하는 함수를 2번 반복하여 나온 결과 예제입니다.

import timeit

def test():
    return "-".join(str(n) for n in range(100))

t1 = timeit.repeat('test()', setup='from __main__ import test', number=10000, repeat=2)
print(t1)


# [0.3301916840719059, 0.3387007679557428]

timeit.Timer(stmt='pass', setup='pass', timer=<timer function>, globals=None)

Timer 클래스는 timeit 모듈에서 사용되는 공통 클래스 입니다. 위에서 설명한 것처럼 단일 건으로 사용할 수도 있지만 Timer() 클래스에 선언한 다음, timeit()과 repeat()을 여러번 사용할 수 있습니다.

timeit(number=1000000)

위 Timer 클래스를 선언하고 timeit()함수에 실행 횟수만 지정하여 사용할 수 있습니다. 이 방법을 사용하면 여분의 함수 호출로 인해 타이밍 오버헤드가 약간 더 커집니다. 

기본적으로, timeit()은 시간 측정 중에 가비지 컬렉터 기능을 일시적으로 끕니다. 이 방법의 장점은 독립적인 시간 측정이 더 잘 비교될 수 있다는 것입니다. 단점은 가비지 컬렉터가 측정되는 함수의 성능에서 중요한 요소가 될 수 있다는 것입니다.

단점을 해결하기 위해서 가비지 컬렉터를 setup 문자열의 첫 번째 문장에서 다시 활성화할 수 있습니다.

timeit.Timer('for i in range(10): oct(i)', 'gc.enable()').timeit()


예제

import timeit


def test():
    return "-".join(str(n) for n in range(100))

timer = timeit.Timer('test()', setup='from __main__ import test')
t1 = timer.timeit(number=10000)

print(t1)


# 0.3503948861034587

repeat(repeat=5, number=1000000)

timeit.repeat()함수와 동일한 동작을 합니다.

예제

import timeit


def test():
    return "-".join(str(n) for n in range(100))

timer = timeit.Timer('test()', setup='from __main__ import test')
t1 = timer.repeat(number=10000, repeat=2)

print(t1)


# [0.3324198810150847, 0.32754432293586433]

autorange(callback=None)

timeit()를 호출하는 횟수를 자동으로 결정합니다. 이 함수는 총 시간이 0.2초 이상이 될 때까지 timeit()을 반복적으로 호출하고, 최종 (루프 수, 해당 루프 수에 소요된 시간)을 반환하는 함수입니다. 실행 시간이 적어도 0.2초가 될 때까지 1, 2, 5, 10, 20, 50 ... 로 루프 수를 증가시키면서 timeit()을 호출합니다. callback이 주어지고 None이 아니면, 시도 다음에 두 개의 인자로 호출합니다: callback(number, time_taken).

예제

import timeit
def test():
    return "-".join(str(n) for n in range(100))

timer = timeit.Timer('test()', setup='from __main__ import test')
t1 = timer.autorange()

print(t1)

# (10000, 0.4110312530538067)


해당 함수는 사용하지 않아서 정확히는............

저작자표시

'언어 > 파이썬 & 장고' 카테고리의 다른 글

[Python] operator 모듈 사용해서 연산 처리 속도 빠르게 하기  (0) 2019.10.13
[Python] functools 모듈의 reduce 함수 사용하기  (0) 2019.10.13
[Python] 함수 및 코드 실행시간 측정하기 (timeit 모듈 사용법)  (0) 2019.10.05
[Python] 소인수 분해, 약수 구하기  (0) 2019.09.29
[Python] 최대공약수, 최소공배수, N개의 최소공배수  (0) 2019.09.22
[Python] 순열, 조합, 곱집합  (0) 2019.09.21

소인수 분해

소인수 분해를 하기 위해선 이전에 정리한 에라토스테네스의 체 방식을 사용한 소수 구하기를 사용하여 변형하는 것이 좋습니다. (https://brownbears.tistory.com/445)


아래는 특정 값이 주어졌을 때, 소인수 분해를 한 예시입니다.

import math


def get_primes(n):
    # 구하고자 하는 수만큼 True를 갖는 리스트 생성
    is_primes = [True] * n
    # n의 최대 약수가 sqrt(n) 이하이므로 계산한 후, 소숫점이 있을 경우 올림으로 최대 반복 횟수 계산
    max_length = math.ceil(math.sqrt(n))

    for i in range(2, max_length):
        # True일 경우, 소수
        if is_primes[i]:
            # i이후 i의 배수들을 지워나감
            for j in range(i + i, n, i):
                is_primes[j] = False

    # 리스트의 True로 남아 있는 인덱스(소수)를 추출
    return [i for i in range(2, n) if is_primes[i]]




def get_factorization(num):
    factors = []
    for prime in get_primes(num):
        count = 0
        while num % prime == 0:
            num /= prime
            count += 1
        if count > 0:
            factors.append((prime, count))

get_factorization(12)


# [(2, 2), (3, 1)]

약수 구하기

소인수 분해를 사용해 구하는 방법, 단순하게 1부터 주어진 수까지 구하는 방법이 있습니다. 소인수 분해를 사용해 구하는 방법은 위의 코드를 사용하기 때문에 단순히 구하는 방법보다 어렵습니다.


아래는 단순하지만 효과적인 방법으로 만든 예제입니다.

import math



def get_divisor(num):
    divisors = []
    length = int(math.sqrt(num)) + 1
    
    for i in range(1, length):
        if num % i == 0:
            divisors.append(i)
            divisors.append(num//i)

    divisors.sort()
    return divisors

print(get_divisor(90))

# [1, 2, 3, 5, 6, 9, 10, 15, 18, 30, 45, 90]


에라토스체네스의 체와 같이 주어진 수만큼 반복문을 진행할 필요없이 10^2 > 90 이므로 11보다 작은 수만큼 나누면 결과를 얻을 수 있습니다.

약수 개수 구하기

약수의 개수는 소인수 분해와 위의 약수 구한 예제 코드로 구할 수 있습니다.


두 코드의 수행속도를 비교한 예제 입니다.

import math
import timeit

## 약수 개수 구한 코드
def get_divisor(num):
    divisors = []
    length = int(math.sqrt(num)) + 1
    for i in range(1, length):
        if num % i == 0:
            divisors.append(i)
            divisors.append(num//i)

    divisors.sort()
    return divisors

## 소인수 분해를 위한 코드
def get_primes(n):
    # 구하고자 하는 수만큼 True를 갖는 리스트 생성
    is_primes = [True] * n
    # n의 최대 약수가 sqrt(n) 이하이므로 계산한 후, 소숫점이 있을 경우 올림으로 최대 반복 횟수 계산
    max_length = math.ceil(math.sqrt(n))

    for i in range(2, max_length):
        # True일 경우, 소수
        if is_primes[i]:
            # i이후 i의 배수들을 지워나감
            for j in range(i + i, n, i):
                is_primes[j] = False

    # 리스트의 True로 남아 있는 인덱스(소수)를 추출
    return [i for i in range(2, n) if is_primes[i]]

def get_factorization(num):
    factors = []
    for prime in get_primes(num):
        count = 0
        while num % prime == 0:
            num /= prime
            count += 1
        if count > 0:
            factors.append((prime, count))

    return factors

def get_divisor_cnt(num):

    divisor_length = 1
    for factor in get_factorization(num):
        divisor_length *= factor[1] + 1

    return divisor_length

# 12의 약수 개수 실행속도
t1 = timeit.timeit('len(get_divisor(12))', setup="from __main__ import get_divisor", number=1)
t2 = timeit.timeit('get_divisor_cnt(12)', setup="from __main__ import get_divisor_cnt", number=1)


# 2.378108911216259e-05
# 7.567903958261013e-05


# 1000000의 약수 개수 실행속도
t1 = timeit.timeit('len(get_divisor(1000000))', setup="from __main__ import get_divisor", number=1)
t2 = timeit.timeit('get_divisor_cnt(1000000)', setup="from __main__ import get_divisor_cnt", number=1)

# 0.00011199899017810822
# 0.267205539974384


약수 개수를 구하는 속도는 소인수 분해를 통해 구하는 것보다 단순하게 약수를 구하는 것이 훨씬 빠른 것으로 확인이 됩니다.

요약

소인수 분해를 구하는 것이 아닌, 약수를 구하는 문제라면 굳이 소인수 분해를 할 필요가 없다.

저작자표시

'언어 > 파이썬 & 장고' 카테고리의 다른 글

[Python] functools 모듈의 reduce 함수 사용하기  (0) 2019.10.13
[Python] 함수 및 코드 실행시간 측정하기 (timeit 모듈 사용법)  (0) 2019.10.05
[Python] 소인수 분해, 약수 구하기  (0) 2019.09.29
[Python] 최대공약수, 최소공배수, N개의 최소공배수  (0) 2019.09.22
[Python] 순열, 조합, 곱집합  (0) 2019.09.21
[Python] 리스트 slice, pop, del 성능 비교 및 사용방법  (0) 2019.09.21

최대공약수 (Greatest Common Divisor)

최대공약수는 주어진 두 수 x, y에서 x의 약수이면서 y의 약수인 수 중 최대값을 의미합니다. 최대공약수를 구하는 간단한 방법은 1에서 x와 y 중 작은 값의 범위에서 공약수(둘 모두 나머지가 0)를 모두 구한 다음 이 수들 중 최대값을 구하는 방법입니다. 1부터 x 또는 y 중 작은 값까지 반복하며 값을 구할 수 있지만 유클리드 호제법(Euclidean algorithm)을 이용하면 간단하게 계산이 됩니다.

유클리드 호제법의 공식은 다음과 같습니다.

  1. 최대공약수를 구하는 함수를 gcd(x,y)라고 가정
  2. x % y = 0이라면 gcd(x, y) = y가 성립
  3. x % y != 0이라면 gcd(x, y) = gcd(x, x % y)가 성립
  4. 2번이 될 때까지 2~3번을 반복

예를 들어, 1071과 1029의 최대공약수를 유클리드 호제법을 활용해 계산하면 다음과 같습니다.

  1. 1071은 1029로 딱 나눠지지 않기 때문에 1071을 1029로 나눈 나머지를 구함 -> 42
  2. 1029는 42로 딱 나눠지지 않기 때문에 1029를 42로 나눈 나머지를 구함 -> 21
  3. 42는 21로 나눠짐
  4. 최대공약수는 21


이를 파이썬 코드로 짜면 아래와 같습니다.

def gcd(x, y):
   # y가 0이 될 때까지 반복
   while y:
       # y를 x에 대입
       # x를 y로 나눈 나머지를 y에 대입
       x, y = y, x % y
   return x


print(gcd(1071, 1029))


# 21


파이썬에서는 이를 구현할 필요없이 내장함수 math 모듈에서 기능을 제공해주고 있습니다.

from math import gcd




print(gcd(1071, 1029))


# 21


fractions 모듈의 math는 삭제예정이니 math 모듈을 사용하는 것이 좋습니다.

최소공배수 (Least Common Multiple)

최소공배수는 x와 y의 공통된 배수 가운데 최소값을 의미합니다. 더 쉽게 말해서, 최소공배수는 주어진 수인 x,y의 곱에서 x,y의 최대공약수를 나누어 준 것과 같습니다. 즉, 유클리드 호제법을 사용해 최대공약수를 구한 다음, x와 y의 곱한 값을 나눠주면 최소공배수를 구할 수 있습니다.


아래는 파이썬에서 제공해주는 내장함수 gcd를 사용해 최소공배수를 구한 예제입니다.

from math import gcd

def lcm(x, y):
   return x * y // gcd(x,y)

print(lcm(1071, 1029))


# 52479


파이썬에서 // 연산자는 나눈 값의 몫을 반환합니다.


N개의 최소공배수

최소공배수는 2개의 수를 대상으로 실행하기 때문에 주어진 수가 3개 이상일 때, 막막해 보이지만 해결방법은 간단합니다. 먼저 2개의 수에 대해 최소공배수를 구한 다음, 그 값과 계산하지 않은 값들 중 1개를 선택해 다시 최소공배수를 구합니다. 이렇게 모든 수에 대해 최소공배수를 구하면 N개의 최소공배수를 구할 수 있습니다.


아래는 파이썬 코드입니다.

from math import gcd


def solution(arr):
    def lcm(x, y):
        return x * y // gcd(x, y)

    while True:
        arr.append(lcm(arr.pop(), arr.pop()))
        if len(arr) == 1:
            return arr[0]


print(solution([2, 6, 8, 14]))

# 168


저작자표시

'언어 > 파이썬 & 장고' 카테고리의 다른 글

[Python] 함수 및 코드 실행시간 측정하기 (timeit 모듈 사용법)  (0) 2019.10.05
[Python] 소인수 분해, 약수 구하기  (0) 2019.09.29
[Python] 최대공약수, 최소공배수, N개의 최소공배수  (0) 2019.09.22
[Python] 순열, 조합, 곱집합  (0) 2019.09.21
[Python] 리스트 slice, pop, del 성능 비교 및 사용방법  (0) 2019.09.21
[Python] 행렬의 곱셈  (0) 2019.09.12

+ Random Posts