Proyek Euler # 645 - percepat simulasi Monte-Carlo dengan Python

Question

Saya mencoba menyelesaikan Q645. Meskipun logika yang digunakan untuk kode saya tampaknya sesuai, kode itu sendiri terlalu lambat untuk jumlah besar yang diperlukan dalam pertanyaan ini. Bolehkah saya meminta saran untuk meningkatkan kinerja kode saya?

Pertanyaannya seperti di link: https://projecteuler.net/problem=645

Kode Python saya adalah sebagai berikut:

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)

Dan logika saya adalah sebagai berikut:

Untuk day_list di dalam fungsi Exp (D) , di mana D adalah jumlah hari dalam setahun, nol berarti tidak ada hari libur, dan satu berarti hari libur. Awalnya day_list semuanya nol karena tidak ada hari libur untuk memulai .

Aturan mendefinisikan hari acak ( d ) sebagai hari libur adalah sebagai berikut:

1. Pada awal masa pemerintahan Kaisar saat ini, hari lahirnya dinyatakan sebagai hari libur mulai tahun itu dan seterusnya.

2. Jika hari sebelum dan sesudah hari d adalah hari libur, maka d juga menjadi hari libur.

Saya kemudian kemudian menerapkan aturan yang dinyatakan untuk pertanyaan tersebut, untuk secara bertahap menambahkan hari libur (satu) ke dalam day_list . Setelah num_emperor jumlah kaisar, semua hari ( d ) di day_list akan menjadi 1, artinya semua hari akan menjadi hari libur . Ini adalah titik untuk keluar dari fungsi while_loop di Exp (D) dan menghitung jumlah kaisar yang dibutuhkan. Untuk mendapatkan jumlah rata-rata kaisar yang dibutuhkan untuk semua hari untuk menjadi hari libur ( avg_n_emperor ), saya kemudian menerapkan metode monte-carlo.

Untuk kode saya saat ini, waktu yang dibutuhkan adalah sebagai berikut:

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

di mana waktu membutuhkan peningkatan kira-kira. linier dengan iter .

Namun,

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

sudah membutuhkan waktu sekitar 68 detik, dan pertanyaannya menanyakan D = 10000. Belum lagi iter yang diperlukan agar jawaban akurat dalam 4 digit setelah koma desimal (seperti yang disyaratkan oleh pertanyaan) akan jauh lebih besar dari 1000000 juga ...

Setiap saran untuk mempercepat kode saya akan sangat dihargai! :)

Answer 1

Selamat datang di Review Kode. Implementasinya bagus, mudah dibaca dan dimengerti.

Optimasi

Ada beberapa operasi "mahal" yang dapat disederhanakan. Di bawah ini saya mengomentari bagian yang relevan:

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

Oleh \$O(D)\$Maksud saya, dalam kasus terburuk, operasi semacam itu akan Dberulang kali, di mana Djumlah hari.

Kondisi dalam while loop dapat disederhanakan dengan memeriksa apakah jumlah hari libur <hari:

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

Optimasi kedua adalah menghindari loop dalam. Setelah ulang tahun baru dihitung, cukup dengan "melihat-lihat" pada hari tertentu itu:

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

The %mencegah operator untuk meluap array, sehingga Anda tidak perlu pengecualian menangkap.

Menjalankan rata-rata:

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

Mengenai gayanya, @Peilonrayz sudah memberikan ulasan yang sangat bagus.

Answer 2

Pertama-tama, buat kode Anda menjadi sedikit lebih bersih:

• Anda bisa menggunakan statistics.meandaripada membuat my_mean.

• Anda harus menggunakan forloop daripada while loop in monte_carlo.

• Anda tidak perlu melakukan penugasan n_emperersama sekali dalam fungsi tersebut.

• Expdan Dseharusnya lower_snake_case. Ini karena mereka adalah fungsi dan variabel.

• Anda harus memberi spasi di sekitar semua operator.

• Harus ada spasi setelah koma.

• Anda harus memiliki beberapa nama yang lebih baik, day_listbisa saja days, Dbisa juga seperti days, summbisa total, itersbisa amounts.

• Anda bisa menggunakan all(day_list)daripada all((d == 1 for d in day_list)).

• Jangan gunakan ==untuk membandingkan dengan lajang seperti False. Akan lebih baik jika Anda malah menggunakan not.

• Ini tidak memeriksa apakah kedua nilai adalah 1 ia memeriksa apakah yang pertama benar dan yang kedua adalah satu. Ini berarti jika Anda mengatur day_list[index - 1]ke dua, itu masih benar.

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

  Untuk memastikan keduanya sama dengan yang harus Anda gunakan:

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

  Di sini saya hanya akan memeriksa apakah mereka benar.

• Anda tidak perlu if ind == 0:seolah-olah ind0 maka ind - 1akan -1.

• Anda bisa menggunakan (ind + 1) % len(days)untuk menghilangkan kebutuhan 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)))

Sekarang kodenya bagus dan kecil, kita dapat fokus pada apa yang menyebabkan masalah kinerja.

1. Berikut ini anyberjalan di \$O(n)\$waktu dimana \$n\$adalah panjang days. Ini berarti kasus terburuk itu akan berjalan berapa pun hari yang panjang setiap kali Anda menyebutnya.

   not all(days)
   

   Kita dapat melakukan lebih baik dari itu dengan menambahkan variabel dalam kenaikan itu setiap kali kita mengubah 0 menjadi 1. Kita kemudian dapat membandingkannya days_in_yearuntuk melihat apakah daftarnya penuh. Ini akan berjalan di \$O(1)\$ waktu menyebabkan penghematan yang signifikan.

2. Jika seorang kaisar baru lahir pada hari libur yang sudah ada maka tidak ada hari libur tambahan yang akan dibuat.

3. Saat kaisar baru lahir, Anda tidak perlu memeriksa apakah setiap nol dapat diubah, Anda hanya perlu mencentang dua. Ini akan memotong yang lain \$O(n)\$operasi untuk \$O(1)\$.
   Katakanlah kita memiliki yang berikut ini sebagai days:

   0123456
   1000010
   

   Jika ulang tahun baru adalah:

   • 6 - Karena 5 dan 0 sama-sama sudah 1s, tidak ada hari libur tambahan yang dapat dibuat.

   • 3 - Karena 4 adalah 0 dan 5 adalah 1, 4 bisa menjadi 1. Karena 2 adalah 0 tetapi 1 adalah 0 maka 3 tidak bisa menjadi 1.

     Ini tidak bisa menyebar ke luar.

Answer 3

Secara realistis, ulasan saya harus "Itu tidak akan berhasil, Anda tidak akan mendapatkan akurasi yang dibutuhkan dengan eksperimen seperti itu. Anda memerlukan pendekatan yang berbeda" .

Tapi inilah simulasi waktu O (D). Alih-alih berpotensi menghasilkan ulang tahun yang sudah terjadi berulang kali, saya fokus hanya pada hari ulang tahun baru . Artinya, saya mengocok semua kemungkinan ulang tahun di awal, dan kemudian saya hanya menjalaninya. Tentu saja itu berarti saya tidak bisa begitu saja emperors += 1. Sebagai gantinya, saya menambahkan jumlah kaisar baru yang diharapkan yang dibutuhkan untuk merayakan ulang tahun baru.

Dengan 1000 simulasi, laptop saya membutuhkan waktu 0.6 detik untuk D = 365, 1.8 detik untuk D = 1000, atau 19 detik untuk 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. Coba saja emperor += 1caranya juga, yang memakan waktu sekitar 1,35, 4,1, dan 62 detik:

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