Project Euler # 645 - Python'da Monte-Carlo simülasyonunu hızlandırın

Question

Q645'i çözmeye çalışıyorum. Kodum için kullanılan mantık uygun görünmekle birlikte, kodun kendisi bu soruda gereken büyük sayı için çok yavaş. Kodumun performansını iyileştirmek için öneri (ler) isteyebilir miyim?

Soru, bağlantıdaki gibidir: https://projecteuler.net/problem=645

Python kodum aşağıdaki gibidir:

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)

Ve mantığım şu:

İçin DAY_LIST içindeki Exp (D) işlevi, D bir yıl içinde gün sayısını ise, sıfır hiçbir tatil ve olanları ortalama tatil demek. Başlangıçta, başlangıçta tatil olmadığından day_list tamamen sıfırdır .

Rastgele bir günü ( d ) tatil olarak tanımlamanın kuralları aşağıdaki gibidir:

1. Mevcut imparatorun saltanatının başında, doğum günü o yıldan itibaren tatil ilan edilir.

2. Önce ve bir gün sonraki gün hem Eğer d sonra tatil vardır d de tatil olur.

Daha sonra, gün_listesine kademeli olarak tatilleri (tatilleri) eklemek için soru için belirtilen kuralları uyguluyorum . Sonra num_emperor imparatorların sayısı, bütün gün ( d cinsinden) DAY_LIST , 1 olacak yani tüm gün tatil olacak . Bu, Exp (D) işlevinde while_loop'tan çıkma ve gerekli imparator sayısını sayma noktasıdır . Tüm günlerin tatil olması için gereken ortalama imparator sayısını ( ort. Emperor ) elde etmek için, daha sonra monte carlo yöntemini uyguluyorum .

Mevcut kodum için süre aşağıdaki gibidir:

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

zamanın arttığı yakl. iters ile doğrusal olarak .

Ancak,

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

zaten yaklaşık 68 saniye sürüyor ve soru D = 10000 istiyor. Cevabın ondalık noktalardan sonraki 4 basamak içinde (sorunun gerektirdiği şekilde) doğru olması için gereken yönlendiricilerin de 1000000'den çok daha büyük olacağını belirtmiyorum bile ...

Kodumu hızlandırmak için herhangi bir öneri / öneriler memnuniyetle karşılanacaktır! :)

Answer 1

Kod İncelemesine hoş geldiniz. Güzel uygulama, okuması ve anlaması kolay.

Optimizasyon

Basitleştirilebilecek bazı "pahalı" işlemler vardır. Aşağıda ilgili kısımları yorumladım:

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

by \$O(D)\$Demek istediğim, en kötü durumda, bu tür bir işlem , gün sayısı Dnerede yinelenecek D.

While döngüsündeki koşul, tatil sayısının <gün olup olmadığı kontrol edilerek basitleştirilebilir:

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

İkinci optimizasyon, iç döngülerden kaçınmaktır. Yeni doğum günü hesaplandıktan sonra, o belirli gün "etrafa bakmak" yeterlidir:

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

%Eğer yakalamak istisnalar gerekmez böylece operatör önler, dizi taşmaya.

Ortalama koşmak:

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

Tarzla ilgili olarak, @Peilonrayz zaten mükemmel bir inceleme yaptı.

Answer 2

Öncelikle kodunuzun biraz daha temiz olmasını sağlayalım:

• statistics.meanMake yerine kullanabilirsiniz my_mean.

• Bir forwhile döngüsü yerine bir döngü kullanmalısınız monte_carlo.

• İşlevde n_empererhiç atama yapmanıza gerek yoktur .

• Expve Dolmalıdır lower_snake_case. Bu, işlevler ve değişkenler oldukları için.

• Tüm operatörlerin etrafına boşluk koymalısınız.

• Virgüllerden sonra boşluk bırakılmalıdır.

• Daha iyi isimlere sahip olmalısınız, day_listsadece olabilir days, Daynı zamanda olabilir days, summolabilir total, itersolabilir amounts.

• Bunun all(day_list)yerine kullanabilirsiniz all((d == 1 for d in day_list)).

• ==Gibi singletonları karşılaştırmak için kullanmayın False. Onun yerine kullanırsan daha iyi olur not.

• Bu, değerlerin her ikisinin de 1 olup olmadığını kontrol etmez, ilkinin doğru ve ikincisinin bir olup olmadığını kontrol eder. Bu day_list[index - 1], ikiye ayarlarsanız hala doğru olacağı anlamına gelir .

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

  Her ikisinin de kullanmanız gereken birine eşit olduğunu kontrol etmek için:

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

  Burada bunun yerine sadece doğru olup olmadıklarını kontrol ederim.

• 0mış if ind == 0:gibi ihtiyacınız yok ind, o ind - 1zaman olacak -1.

• İhtiyacı (ind + 1) % len(days)ortadan kaldırmak için sadece kullanabilirsiniz 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)))

Artık kod güzel ve küçük olduğuna göre, performans sorunlarına neden olan şeye odaklanabiliriz.

1. Aşağıdaki anyiçinde çalışır \$O(n)\$saat, nerede \$n\$uzunluğu days. Bu, uzun günler her çağırdığınızda çalışacağı en kötü durum anlamına gelir.

   not all(days)
   

   0'ı 1'e her değiştirdiğimizde bu artışlarla bir değişken ekleyerek bundan daha iyisini yapabiliriz. Daha sonra days_in_yearlistenin dolu olup olmadığını görmek için bunu ile karşılaştırabiliriz . Bu, \$O(1)\$ önemli bir tasarruf sağlayan zaman.

2. Zaten var olan bir tatilde yeni bir imparator doğarsa, o zaman ekstra tatil yapılmayacaktır.

3. Yeni bir imparator doğduğunda, her sıfırın değiştirilip değiştirilemeyeceğini kontrol etmeniz gerekmez, bunun yerine yalnızca ikisini kontrol etmeniz gerekir. Bu başka bir \$O(n)\$işlem için \$O(1)\$.
   Aşağıdakilere sahip olduğumuzu varsayalım days:

   0123456
   1000010
   

   Yeni doğum günü ise:

   • 6 - Hem 5 hem de 0 zaten 1 olduğundan, ek tatil yapılamaz.

   • 3 - 4 0 ve 5 1 olduğu için 4 1 olabilir. 2 0, 1 0 olduğu için 3 1 olamaz.

     Bu dışa doğru yayılamaz.

Answer 3

Gerçekçi olarak, benim incelemem "Bu işe yaramayacak, böyle bir deneyle gerekli doğruluğu elde edemezsiniz. Farklı bir yaklaşıma ihtiyacınız var" olmalıdır .

Ama işte O (D) zaman simülasyonu. Potansiyel olarak zaten oluşmuş doğum günlerini tekrar tekrar üretmek yerine, sadece yeni doğum günlerine odaklanıyorum . Yani, başlangıçta olası tüm doğum günlerini karıştırıyorum ve sonra onlardan geçiyorum. Elbette bu, yapamayacağım anlamına geliyor emperors += 1. Bunun yerine, yeni bir doğum gününe rastlamak için gereken yeni imparator sayısını ekliyorum.

1000 simülasyonla, dizüstü bilgisayarımın D = 365 için 0,6 saniye, D = 1000 için 1,8 saniye veya D = 10000 için 19 saniye sürüyor.

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. Aynı şekilde denedim emperor += 1, bunun yerine yaklaşık 1.35, 4.1 ve 62 saniye sürdü:

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