Project Euler # 645 - tăng tốc mô phỏng Monte-Carlo bằng Python

Question

Tôi đang cố gắng giải quyết Q645. Mặc dù logic được sử dụng cho mã của tôi có vẻ phù hợp, nhưng bản thân mã quá chậm so với số lượng lớn được yêu cầu trong câu hỏi này. Tôi có thể yêu cầu (các) đề xuất để cải thiện hiệu suất mã của tôi không?

Câu hỏi như trong liên kết: https://projecteuler.net/problem=645

Mã Python của tôi như sau:

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)

Và logic của tôi là như sau:

Đối với danh sách ngày bên trong hàm Exp (D) , trong đó D là số ngày trong năm, các số không có nghĩa là không có ngày lễ và các số không có nghĩa là ngày nghỉ. Ban đầu, danh sách ngày là tất cả các số 0 vì không có ngày lễ nào bắt đầu .

Các quy tắc xác định một ngày ngẫu nhiên ( d ) là một ngày lễ như sau:

1. Vào đầu thời kỳ trị vì của Hoàng đế hiện tại, sinh nhật của ông được tuyên bố là một ngày lễ kể từ năm đó trở đi.

2. Nếu cả ngày trước và sau một ngày d là ngày nghỉ, thì ngày d cũng trở thành ngày nghỉ.

Sau đó, tôi thực hiện các quy tắc được nêu cho câu hỏi, để dần dần thêm các ngày lễ (cái) vào danh sách ngày . Sau num_emperor số hoàng đế, tất cả các ngày ( d ) trong day_list sẽ trở thành 1, tức là tất cả các ngày sẽ trở thành kỳ nghỉ . Đây là điểm để thoát khỏi while_loop trong hàm Exp (D) và đếm số lượng hoàng đế được yêu cầu. Để có được số lượng hoàng đế trung bình cần thiết cho tất cả các ngày trở thành ngày lễ ( avg_n_emporary ), tôi áp dụng phương pháp monte-carlo.

Đối với mã hiện tại của tôi, thời gian diễn ra như sau:

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

trong đó thời gian cần tăng lên khoảng. tuyến tính với iters .

Tuy nhiên,

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

đã mất khoảng 68 giây và câu hỏi đặt ra là D = 10000. Chưa kể rằng iters yêu cầu cho câu trả lời chính xác trong vòng 4 chữ số sau dấu thập phân (theo yêu cầu của câu hỏi) cũng sẽ lớn hơn nhiều so với 1000000 ...

Bất kỳ (các) đề xuất nào để tăng tốc mã của tôi sẽ được đánh giá cao! :)

Answer 1

Chào mừng bạn đến với Đánh giá mã. Cách thực hiện đẹp, dễ đọc và dễ hiểu.

Tối ưu hóa

Có một số hoạt động "tốn kém" có thể được đơn giản hóa. Dưới đây tôi nhận xét các phần có liên quan:

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

Bởi \$O(D)\$Ý tôi là trong trường hợp xấu nhất, hoạt động đó sẽ lặp lại Dthời gian, Dsố ngày ở đâu.

Điều kiện trong vòng lặp while có thể được đơn giản hóa bằng cách kiểm tra xem số ngày nghỉ có phải là <ngày không:

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

Tối ưu hóa thứ hai là tránh các vòng lặp bên trong. Khi sinh nhật mới đã được tính toán, chỉ cần "nhìn quanh" ngày cụ thể đó:

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

Các %ngăn chặn khai thác tràn mảng, do đó bạn không cần phải ngoại lệ bắt.

Chạy mức trung bình:

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

Về phong cách, @Peilonrayz đã cung cấp một đánh giá xuất sắc.

Answer 2

Trước hết hãy để mã của bạn gọn gàng hơn một chút:

• Bạn có thể sử dụng statistics.meanhơn là thực hiện my_mean.

• Bạn nên sử dụng một forvòng lặp hơn là một vòng lặp while trong monte_carlo.

• Bạn không cần phải gán gì n_emperercả trong hàm.

• Expvà Dnên được lower_snake_case. Đây là vì chúng là hàm và biến.

• Bạn nên đặt khoảng trắng xung quanh tất cả các toán tử.

• Phải có một khoảng trắng sau dấu phẩy.

• Bạn nên có một số tên tốt hơn day_listcó thể là days, Dcũng có thể là một cái gì đó như days, summcó thể được total, iterscó thể được amounts.

• Bạn chỉ có thể sử dụng all(day_list)hơn là all((d == 1 for d in day_list)).

• Không sử dụng ==để so sánh với singleton như thế nào False. Sẽ tốt hơn nếu bạn sử dụng thay thế not.

• Điều này không kiểm tra xem cả hai giá trị có phải là 1 hay không, nó sẽ kiểm tra xem giá trị đầu tiên là trung thực và giá trị thứ hai là một. Điều này có nghĩa là nếu bạn đặt day_list[index - 1]thành hai thì nó vẫn đúng.

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

  Để kiểm tra cả hai đều bằng nhau, bạn nên sử dụng:

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

  Ở đây thay vào đó tôi chỉ kiểm tra xem chúng có phải là sự thật hay không.

• Bạn không cần if ind == 0:như thể indlà 0 thì ind - 1sẽ có -1.

• Bạn chỉ có thể sử dụng (ind + 1) % len(days)để loại bỏ nhu cầu 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)))

Bây giờ mã đã đẹp và nhỏ, chúng ta có thể tập trung vào những gì đang gây ra các vấn đề về hiệu suất.

1. Phần sau anychạy trong \$O(n)\$thời gian, ở đâu \$n\$là chiều dài của days. Điều này có nghĩa là trong trường hợp xấu nhất, nó sẽ chạy trong một ngày dài mỗi lần bạn gọi.

   not all(days)
   

   Chúng ta có thể làm tốt hơn điều đó bằng cách thêm một biến với gia số đó mỗi khi chúng ta thay đổi từ 0 thành 1. Sau đó, chúng ta có thể so sánh với biến đó days_in_yearđể xem danh sách đã đầy chưa. Điều này sẽ chạy trong \$O(1)\$ tiết kiệm đáng kể thời gian.

2. Nếu một vị hoàng đế mới được sinh ra vào một ngày lễ đã có sẵn thì sẽ không có thêm ngày lễ nào.

3. Khi một hoàng đế mới được sinh ra, bạn không cần phải kiểm tra xem từng số 0 có thể thay đổi được hay không, thay vào đó bạn chỉ cần kiểm tra hai. Cái này sẽ cắt cái khác \$O(n)\$hoạt động với \$O(1)\$.
   Giả sử chúng ta có những thứ sau như days:

   0123456
   1000010
   

   Nếu sinh nhật mới là:

   • 6 - Vì cả số 5 và số 0 đều đã là số 1 nên không thể thực hiện thêm ngày nghỉ nào.

   • 3 - Vì 4 là 0 và 5 là 1 nên 4 có thể trở thành 1. Vì 2 là 0 nhưng 1 là 0 thì 3 không thể trở thành 1.

     Điều này không thể lan truyền ra bên ngoài.

Answer 3

Thực tế, bài đánh giá của tôi sẽ phải là "Điều đó sẽ không hoạt động, bạn sẽ không đạt được độ chính xác cần thiết với một thử nghiệm như vậy. Bạn cần một cách tiếp cận khác" .

Nhưng đây là một mô phỏng thời gian O (D). Thay vì có khả năng tạo ra các sinh nhật đã xảy ra lặp đi lặp lại, tôi chỉ tập trung vào các sinh nhật mới . Đó là, tôi xáo trộn tất cả các ngày sinh có thể có ngay từ đầu, và sau đó tôi lướt qua chúng. Tất nhiên điều đó có nghĩa là tôi không thể chỉ làm emperors += 1. Thay vào đó, tôi thêm số lượng hoàng đế mới dự kiến ​​cần thiết để đón sinh nhật mới.

Với 1000 mô phỏng, máy tính xách tay của tôi mất khoảng 0,6 giây cho D = 365, 1,8 giây cho D = 1000 hoặc 19 giây cho D = 10000.

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. Cũng chỉ thử emperor += 1theo cách này, thay vào đó mất khoảng 1,35, 4,1 và 62 giây:

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)))