Projekt Euler # 645 - Beschleunigen Sie die Monte-Carlo-Simulation in Python

Question

Ich versuche Q645 zu lösen. Während die für meinen Code verwendete Logik angemessen zu sein scheint, ist der Code selbst viel zu langsam für die große Anzahl, die in dieser Frage benötigt wird. Darf ich um Vorschläge bitten, um die Leistung meines Codes zu verbessern?

Die Frage ist wie im Link: https://projecteuler.net/problem=645

Mein Python-Code lautet wie folgt:

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)

Und meine Logik lautet wie folgt:

Für die day_list innerhalb der Exp (D) -Funktion, wobei D die Anzahl der Tage in einem Jahr ist, bedeuten Nullen keinen Feiertag und Einsen Feiertag. Anfangs besteht die day_list nur aus Nullen, da zunächst kein Feiertag vorhanden ist .

Die Regeln zum Definieren eines zufälligen Tages ( d ) als Feiertag lauten wie folgt:

1. Zu Beginn der Regierungszeit des heutigen Kaisers wird sein Geburtstag ab diesem Jahr zum Feiertag erklärt.

2. Wenn sowohl der Tag vor als auch nach einem Tag d Feiertage sind, wird d auch zu einem Feiertag.

Anschließend implementiere ich die für die Frage angegebenen Regeln, um Feiertage (Einsen) schrittweise in die day_list aufzunehmen . Nach num_emperor Anzahl der Kaiser alle Tage ( d ) in day_list wird 1 werden, dh alle Tage Urlaub zu machen . Dies ist der Punkt, an dem Sie die while_loop-Funktion in Exp (D) beenden und die Anzahl der erforderlichen Kaiser zählen können. Um die durchschnittliche Anzahl von Kaisern zu erhalten, die für alle Tage erforderlich sind, um Feiertage zu werden ( avg_n_emperor ), wende ich dann die Monte-Carlo-Methode an.

Für meinen aktuellen Code dauert die Zeit wie folgt:

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

in der die Zeit dauert erhöhen ca. linear mit den iters .

Jedoch,

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

dauert bereits ca. 68 Sekunden und die Frage lautet D = 10000. Ganz zu schweigen davon, dass die Punkte, die erforderlich sind, damit die Antwort innerhalb von 4 Stellen nach den Dezimalstellen (wie in der Frage gefordert) genau ist, auch viel größer als 1000000 sind ...

Alle Vorschläge, um meinen Code zu beschleunigen, wären willkommen! :) :)

Answer 1

Willkommen bei Code Review. Gute Implementierung, leicht zu lesen und zu verstehen.

Optimierung

Es gibt einige "teure" Operationen, die vereinfacht werden können. Unten habe ich die relevanten Teile kommentiert:

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

Von \$O(D)\$Ich meine, dass im schlimmsten Fall eine solche Operation die DZeiten wiederholt , wobei Ddie Anzahl der Tage ist.

Die Bedingung in der while-Schleife kann vereinfacht werden, indem überprüft wird, ob die Anzahl der Feiertage <Tage beträgt:

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

Die zweite Optimierung besteht darin, die inneren Schleifen zu vermeiden. Sobald der neue Geburtstag berechnet wurde, reicht es aus, sich an diesem bestimmten Tag umzuschauen:

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

Der %Operator verhindert, dass das Array überläuft, sodass Sie keine Ausnahmen abfangen müssen.

Laufen der Durchschnitt:

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

In Bezug auf den Stil hat @Peilonrayz bereits eine hervorragende Bewertung abgegeben.

Answer 2

Lassen Sie uns zunächst Ihren Code ein wenig sauberer machen:

• Sie können verwenden, statistics.meananstatt zu machen my_mean.

• Sie sollten eine forSchleife anstelle einer while-Schleife verwenden monte_carlo.

• Sie müssen n_empererin der Funktion überhaupt keine Zuweisung vornehmen.

• Expund Dsollte sein lower_snake_case. Dies ist, wie sie Funktionen und Variablen sind.

• Sie sollten Leerzeichen um alle Operatoren setzen.

• Nach Kommas sollte ein Leerzeichen stehen.

• Sie sollten einige bessere Namen haben, day_listkönnte einfach sein days, Dkönnte auch so etwas sein days, summkann sein total, iterskönnte sein amounts.

• Sie können nur verwenden, all(day_list)anstatt all((d == 1 for d in day_list)).

• Nicht verwenden ==, um mit Singletons wie zu vergleichen False. Es wäre besser, wenn Sie stattdessen verwenden not.

• Dies prüft nicht, ob beide Werte 1 sind, sondern ob der erste wahr und der zweite eins ist. Das heißt, wenn Sie day_list[index - 1]auf zwei setzen , ist es immer noch wahr.

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

  Um zu überprüfen, ob beide gleich einer sind, die Sie verwenden sollten:

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

  Hier würde ich stattdessen nur prüfen, ob sie wahr sind.

• Sie brauchen nicht, if ind == 0:als ob ind0 ist, dann ind - 1wird sein -1.

• Sie können nur verwenden (ind + 1) % len(days), um die Notwendigkeit für zu entfernen 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)))

Jetzt, da der Code nett und klein ist, können wir uns darauf konzentrieren, was Leistungsprobleme verursacht.

1. Folgendes anyläuft in \$O(n)\$Zeit, wo \$n\$ist die Länge von days. Dies bedeutet, dass es im schlimmsten Fall ausgeführt wird, obwohl jedes Mal, wenn Sie es anrufen, lange Tage vergehen.

   not all(days)
   

   Wir können es besser machen, indem wir jedes Mal, wenn wir eine 0 in eine 1 ändern, eine Variable in diesen Schritten hinzufügen. Wir können diese dann vergleichen, days_in_yearum festzustellen, ob die Liste voll ist. Dies wird in \ ausgeführt$O(1)\$ Zeit, die eine erhebliche Einsparung verursacht.

2. Wenn ein neuer Kaiser an einem bereits bestehenden Feiertag geboren wird, werden keine zusätzlichen Feiertage gemacht.

3. Wenn ein neuer Kaiser geboren wird, müssen Sie nicht prüfen, ob jede Null geändert werden kann, sondern nur zwei. Dies wird ein weiteres \ schneiden$O(n)\$Operation zu \$O(1)\$.
   Angenommen, wir haben Folgendes als days:

   0123456
   1000010
   

   Wenn der neue Geburtstag ist:

   • 6 - Da sowohl 5 als auch 0 bereits 1s sind, können keine zusätzlichen Feiertage gemacht werden.

   • 3 - Weil 4 eine 0 und 5 eine 1 ist, kann 4 eine 1 werden. Weil 2 eine 0 ist, aber 1 eine 0 ist, kann 3 keine 1 werden.

     Dies kann sich nicht nach außen ausbreiten.

Answer 3

Realistisch betrachtet , wäre meine Rezension sein : „Das wird nicht funktionieren, werden Sie nicht die erforderliche Genauigkeit mit einem solchen Versuch bekommen. Sie müssen einen anderen Ansatz“ .

Aber hier ist eine O (D) -Zeitsimulation. Anstatt potenziell bereits aufgetretene Geburtstage immer wieder zu generieren, konzentriere ich mich nur auf neue Geburtstage. Das heißt, ich mische zu Beginn alle möglichen Geburtstage und gehe sie dann einfach durch. Das heißt natürlich, ich kann es nicht einfach tun emperors += 1. Stattdessen füge ich die erwartete Anzahl neuer Kaiser hinzu, die benötigt werden, um auf einen neuen Geburtstag zu stoßen.

Bei 1000 Simulationen benötigt mein Laptop ungefähr 0,6 Sekunden für D = 365, 1,8 Sekunden für D = 1000 oder 19 Sekunden für 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. Ich habe es auch emperor += 1so versucht , das dauerte stattdessen ungefähr 1,35, 4,1 und 62 Sekunden:

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