Project Euler # 645 — Python에서 Monte-Carlo 시뮬레이션 속도 향상

Question

Q645를 해결하려고합니다. 내 코드에 사용 된 논리가 적절 해 보이지만 코드 자체는이 질문에 필요한 많은 수에 비해 너무 느립니다. 내 코드의 성능을 향상시키기위한 제안을 요청할 수 있습니까?

질문은 링크와 같습니다. https://projecteuler.net/problem=645

내 Python 코드는 다음과 같습니다.

def Exp(D):
    day_list = [0]*D
    num_emperor = 0
    while all((d == 1 for d in day_list)) == False:
        #the birthday of the emperors are independent and uniformly distributed throughout the D days of the year
        bday = np.random.randint(0,D)
        day_list[bday] = 1
        num_emperor+=1
        #indices of d in day_list where d == 0
        zero_ind = (i for i,v in enumerate(day_list) if v == 0)
        for ind in zero_ind:
            try:
                if day_list[ind-1] and day_list[ind+1] == 1:
                    day_list[ind] = 1
            except IndexError:
                if ind == 0:
                    if day_list[-1] and day_list[1] == 1:
                        day_list[0] = 1
                elif ind == len(day_list)-1:
                    if day_list[len(day_list)-2] and day_list[0] == 1:
                        day_list[len(day_list)-1] = 1
    return num_emperor

def my_mean(values):
    n = 0
    summ = 0.0
    for value in values:
        summ += value
        n += 1
    return summ/n

def monte_carlo(iters, D):
    iter = 0
    n_emperor = 0
    while iter < iters:
        n_emperor = Exp(D)
        yield n_emperor
        iter += 1

avg_n_emperor = my_mean(monte_carlo(iters,D))
print(avg_n_emperor)

그리고 내 논리는 다음과 같습니다.

Exp (D) 함수 내의 day_list의 경우 , 여기서 D 는 1 년의 일 수, 0은 휴일 없음을 의미하고 1은 휴일을 의미합니다. 시작하는 휴일이 없기 때문에 처음에 day_list 는 모두 0 입니다 .

임의의 날 ( d )을 휴일로 정의하는 규칙은 다음과 같습니다.

1. 현재 황제의 통치가 시작될 때, 그의 생일은 그해부터 휴일로 선언됩니다.

2. d 일 전후가 모두 공휴일이면 d 도 공휴일이됩니다.

그런 다음 질문에 명시된 규칙을 구현하여 점차적으로 day_list에 휴일 (일)을 추가합니다 . 후 num_emperor의 황제의 숫자, 모든 날 ( D )에 day_list는 1이 될 것 즉, 모든 일이 휴일이 될 것이다 . 이것은 Exp (D) 함수 의 while_loop를 종료하고 필요한 황제의 수를 계산 하는 지점 입니다. 모든 날이 휴일이되는 데 필요한 평균 황제 수 ( avg_n_emperor )를 구하기 위해 monte-carlo 방법을 적용합니다.

내 현재 코드의 경우 시간은 다음과 같습니다.

avg_n_emperor = my_mean(monte_carlo(iters=100000,D=5)) #6-7 seconds

avg_n_emperor = my_mean(monte_carlo(iters=1000000,D=5)) #about 62 seconds

시간이 걸리는 시간이 약 증가합니다. iters 와 선형 적으로 .

하나,

avg_n_emperor = my_mean(monte_carlo(iters=1000,D=365)) #about 68 seconds

이미 약 68 초가 걸리며 D = 10000을 요구합니다. 아니 말할 것도 iters (질문에서 요구하는) 소수점 포인트 이후 4 자리 숫자 내에서 정확하다고 대답에 필요한이 너무 1000000보다 훨씬 더 큰 것 ...

내 코드 속도를 높이기위한 제안을 주시면 감사하겠습니다! :)

Answer 1

Code Review에 오신 것을 환영합니다. 읽기 쉽고 이해하기 쉬운 멋진 구현.

최적화

단순화 할 수있는 "비용이 많이 드는"작업이 있습니다. 아래에서 관련 부분에 대해 설명했습니다.

def Exp(D):
    # the method "all" takes O(D)
    while all((d == 1 for d in day_list)) == False:
        # O(D)
        zero_ind = (i for i,v in enumerate(day_list) if v == 0) 
        # O(D)
        for ind in zero_ind:
            # Here there are only O(1) operations
    return num_emperor

으로 \$O(D)\$최악의 경우 이러한 작업은 D시간 을 반복 하며, 여기서는 D일 수입니다.

휴일 수가 <일인지 확인하여 while 루프의 조건을 단순화 할 수 있습니다.

def Exp(D):
    holidays = 0
    while holidays < D:
        # increment holidays 
    return num_emperor

두 번째 최적화는 내부 루프를 피하는 것입니다. 새 생일이 계산되면 특정 날짜를 "둘러보기"로 충분합니다.

def Exp(D):
    # ..
    while holidays < D:
        bday = np.random.randint(0,D)
        # Increment holidays only if birthday is not in a holiday
        if day_list[bday] == 0:
            holidays += 1
        day_list[bday] = 1
        num_emperor+=1

        yesterday = (bday - 1) % D
        day_before_yesterday = (bday - 2) % D
        if day_list[day_before_yesterday] == 1 and day_list[yesterday] == 0:
            day_list[yesterday] = 1
            holidays += 1

        tomorrow = (bday + 1) % D
        day_after_tomorrow = (bday + 2) % D
        if day_list[day_after_tomorrow] == 1 and day_list[tomorrow] == 0:
            day_list[tomorrow] = 1
            holidays += 1
    return num_emperor

%당신은 캐치 예외 필요가 없습니다 운영자 방지는, 배열을 오버플로합니다.

평균 실행 :

avg_n_emperor = my_mean(monte_carlo(iters=1000,D=365))
# Output: 1173.786
# Running time: around 2 seconds

스타일과 관련하여 @Peilonrayz는 이미 훌륭한 리뷰를 제공했습니다.

Answer 2

먼저 코드를 좀 더 깔끔하게 만들 수 있습니다.

• statistics.mean대신 사용할 수 있습니다 my_mean.

• 에서 forwhile 루프보다는 루프를 사용해야합니다 monte_carlo.

• n_emperer함수에서 전혀 할당 할 필요가 없습니다 .

• Exp하고 D있어야한다 lower_snake_case. 이것은 함수와 변수이기 때문입니다.

• 모든 연산자 주위에 공백을 두어야합니다.

• 쉼표 뒤에 공백이 있어야합니다.

• 당신은 더 좋은 이름이 있어야 day_list단지 수 days, D또한 같은 될 수있다 days, summ할 수있다 total, iters할 수있다 amounts.

• all(day_list)대신 사용할 수 있습니다 all((d == 1 for d in day_list)).

• ==같은 싱글 톤과 비교하는 데 사용하지 마십시오 False. 대신 사용하는 것이 좋습니다 not.

• 두 값이 모두 1인지 확인하지 않고 첫 번째 값이 진실이고 두 번째 값이 1인지 확인합니다. 이것은 day_list[index - 1]2로 설정해도 여전히 사실임을 의미합니다.

  day_list[ind - 1] and day_list[ind + 1] == 1
  

  둘 다 당신이 사용하는 것과 같은지 확인하려면 :

  day_list[ind - 1] == 1 and day_list[ind + 1] == 1
  

  여기서는 대신 그들이 진실인지 확인합니다.

• 당신은 필요하지 않은 if ind == 0:것처럼 ind0 다음 ind - 1될 것입니다 -1.

• 를 사용 (ind + 1) % len(days)하여 elif index == len(days)-1:.

import random
import statistics


def simulate(days_in_year):
    days = [0] * days_in_year
    emperors = 0
    while not all(days):
        days[random.randrange(len(days))] = 1
        emperors += 1
        for index, value in enumerate(days):
            if value:
                continue
            if days[index - 1] and days[(index + 1) % len(days)]:
                days[index] = 1
    return emperors


def monte_carlo(amount, days):
    for _ in range(amount):
        yield simulate(days)


print(statistics.mean(monte_carlo(amount, days)))

이제 코드가 훌륭하고 작으므로 성능 문제를 일으키는 원인에 집중할 수 있습니다.

1. 다음 any은 \ 에서 실행됩니다.$O(n)\$시간, \$n\$의 길이입니다 days. 이것은 당신이 그것을 부를 때마다 긴 일이 실행 되더라도 최악의 경우를 의미합니다.

   not all(days)
   

   0을 1로 변경할 때마다 증가하는 변수를 추가하여 그보다 더 잘 할 수 있습니다. 그런 다음이를 비교 days_in_year하여 목록이 가득 찼는 지 확인할 수 있습니다. 이것은 \ 에서 실행됩니다.$O(1)\$ 시간을 크게 절약 할 수 있습니다.

2. 이미 존재하는 휴일에 새로운 황제가 태어나면 추가 휴일이 만들어지지 않습니다.

3. 새로운 황제가 태어나면 각각의 0이 변경 될 수 있는지 확인할 필요가 없으며 대신 2 개만 확인하면됩니다. 이것은 다른 \$O(n)\$작업을 \$O(1)\$.
   다음과 같이 가정합니다 days.

   0123456
   1000010
   

   새 생일이 다음과 같은 경우 :

   • 6-5와 0은 모두 이미 1이기 때문에 추가 휴일을 만들 수 없습니다.

   • 3-4는 0이고 5는 1이므로 4는 1이 될 수 있습니다. 2는 0이지만 1은 0이므로 3은 1이 될 수 없습니다.

     이것은 외부로 전파 될 수 없습니다.

Answer 3

현실적으로 제 리뷰는 "그건 효과가 없을 것입니다. 그런 실험에서 필요한 정확도를 얻지 못할 것입니다. 다른 접근 방식이 필요합니다." 여야 합니다 .

하지만 여기 O (D) 시간 시뮬레이션이 있습니다. 잠재적으로 이미 발생한 생일을 반복해서 생성하는 대신 새 생일 에만 집중 합니다. 즉, 나는 처음에 가능한 모든 생일을 섞은 다음 그것들을 통과합니다. 물론 그것은 내가 할 수 없다는 것을 의미 emperors += 1합니다. 대신 새 생일을 맞이하는 데 필요한 예상 새 황제 수를 추가합니다.

1000 번의 시뮬레이션으로 D = 365의 경우 약 0.6 초, D = 1000의 경우 1.8 초, D = 10000의 경우 19 초가 걸립니다.

from random import sample
from statistics import mean

def Exp(D):
    emperors = 0
    holidays = set()
    for i, day in enumerate(sample(range(D), D)):
        emperors += D / (D - i)
        holidays.add(day)
        if (day + 2) % D in holidays:
            holidays.add((day + 1) % D)
        if (day - 2) % D in holidays:
            holidays.add((day - 1) % D)
        if len(holidays) == D:
            return emperors

print(mean(Exp(365) for _ in range(1000)))

Meh. 그냥 emperor += 11.35 초, 4.1 초, 62 초가 걸렸습니다.

from random import randrange
from statistics import mean

def Exp(D):
    emperors = 0
    holidays = set()
    while len(holidays) < D:
        emperors += 1
        day = randrange(D)
        if day not in holidays:
            holidays.add(day)
            if (day + 2) % D in holidays:
                holidays.add((day + 1) % D)
            if (day - 2) % D in holidays:
                holidays.add((day - 1) % D)
    return emperors

print(mean(Exp(365) for _ in range(1000)))