Projet Euler # 645 - Accélérer la simulation Monte-Carlo en Python

Question

J'essaye de résoudre Q645. Bien que la logique utilisée pour mon code semble appropriée, le code lui-même est beaucoup trop lent pour le grand nombre requis dans cette question. Puis-je demander des suggestions pour améliorer les performances de mon code?

La question est comme dans le lien: https://projecteuler.net/problem=645

Mon code Python est le suivant:

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)

Et ma logique est la suivante:

Pour la liste des jours dans la fonction Exp (D) , où D est le nombre de jours dans une année, les zéros signifient pas de vacances et les uns signifient vacances. Au départ, la liste des jours est entièrement composée de zéros car il n'y a pas de vacances au départ .

Les règles pour définir un jour aléatoire ( j ) comme jour férié sont les suivantes:

1. Au début du règne de l'empereur actuel, son anniversaire est déclaré jour férié à partir de cette année-là.

2. Si le jour avant et après le jour d sont des vacances, alors d devient également un jour férié.

J'implémente ensuite par la suite les règles énoncées pour la question, pour ajouter progressivement les jours fériés (un) dans la liste des jours . Après num_emperor ou nombre d'empereurs, tous les jours ( d ) de day_list deviendront 1, c'est-à - dire que tous les jours deviendront des vacances . C'est le point de quitter la boucle while_loop dans la fonction Exp (D) et de compter le nombre d'empereurs requis. Pour obtenir le nombre moyen d'empereurs requis pour tous les jours pour devenir des vacances ( avg_n_emperor ), j'applique ensuite la méthode monte-carlo.

Pour mon code actuel, le temps est le suivant:

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

dans lequel le temps prend augmenter env. linéairement avec les iters .

cependant,

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

prend déjà environ 68 secondes, et la question demande D = 10000. Sans oublier que les iters requis pour que la réponse soit précise à moins de 4 chiffres après la virgule décimale (comme l'exige la question) seraient également beaucoup plus grands que 1000000 ...

Toute suggestion (s) pour accélérer mon code serait appréciée! :)

Answer 1

Bienvenue dans Code Review. Belle mise en œuvre, facile à lire et à comprendre.

Optimisation

Certaines opérations «coûteuses» peuvent être simplifiées. Ci-dessous, j'ai commenté les parties pertinentes:

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

Par \$O(D)\$Je veux dire que dans le pire des cas, une telle opération répétera des Dheures, où Dest le nombre de jours.

La condition de la boucle while peut être simplifiée en vérifiant si le nombre de vacances est <jours:

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

La deuxième optimisation consiste à éviter les boucles internes. Une fois le nouvel anniversaire calculé, il suffit de «regarder» ce jour-là:

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

L' %opérateur empêche le débordement du tableau, vous n'avez donc pas besoin d'intercepter les exceptions.

Courir la moyenne:

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

Concernant le style, @Peilonrayz a déjà fourni une excellente critique.

Answer 2

Tout d'abord, rendons votre code un peu plus propre:

• Vous pouvez utiliser statistics.meanplutôt que fabriquer my_mean.

• Vous devez utiliser une forboucle plutôt qu'une boucle while monte_carlo.

• Vous n'avez pas du tout besoin d'affecter n_empererdans la fonction.

• Expet Ddevrait l'être lower_snake_case. C'est comme ce sont des fonctions et des variables.

• Vous devez mettre des espaces autour de tous les opérateurs.

• Il devrait y avoir un espace après les virgules.

• Vous devriez avoir de meilleurs noms qui day_listpourraient être days, Dpourraient aussi être quelque chose comme days, summpeut être total, iterspourrait être amounts.

• Vous pouvez simplement utiliser all(day_list)plutôt que all((d == 1 for d in day_list)).

• Ne pas utiliser ==pour comparer aux singletons comme False. Ce serait mieux si vous utilisez à la place not.

• Cela ne vérifie pas si les deux valeurs sont égales à 1, mais vérifie si la première est véridique et la seconde est une. Cela signifie que si vous définissez day_list[index - 1]sur deux, ce sera toujours vrai.

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

  Pour vérifier qu'ils sont tous les deux égaux à celui que vous devez utiliser:

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

  Ici, je voudrais plutôt vérifier si elles sont véridiques.

• Vous n'avez pas besoin if ind == 0:comme si indvaut 0 alors le ind - 1sera -1.

• Vous pouvez simplement utiliser (ind + 1) % len(days)pour supprimer le besoin de 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)))

Maintenant que le code est beau et petit, nous pouvons nous concentrer sur ce qui cause des problèmes de performances.

1. Ce qui suit anys'exécute dans \$O(n)\$heure, où \$n\$est la longueur de days. Cela signifie que dans le pire des cas, il fonctionnera quelle que soit la durée des jours à chaque fois que vous l'appelez.

   not all(days)
   

   Nous pouvons faire mieux que cela en ajoutant une variable dans ces incréments chaque fois que nous changeons un 0 en un 1. Nous pouvons ensuite comparer cela days_in_yearpour voir si la liste est pleine. Cela fonctionnera dans \$O(1)\$ temps entraînant une économie significative.

2. Si un nouvel empereur est né un jour férié déjà existant, aucun congé supplémentaire ne sera effectué.

3. Quand un nouvel empereur est né, vous n'avez pas besoin de vérifier si chaque zéro peut être changé, vous n'avez qu'à en vérifier deux. Cela en coupera un autre \$O(n)\$opération à \$O(1)\$.
   Disons que nous avons ce qui suit comme days:

   0123456
   1000010
   

   Si le nouvel anniversaire est:

   • 6 - Parce que 5 et 0 sont déjà des 1, aucun congé supplémentaire ne peut être effectué.

   • 3 - Parce que 4 est un 0 et 5 est un 1, 4 peut devenir un 1. Parce que 2 est un 0 mais 1 est un 0 alors 3 ne peut pas devenir un 1.

     Cela ne peut pas se propager vers l'extérieur.

Answer 3

En réalité, ma critique devrait être "Cela ne fonctionnera pas, vous n'obtiendrez pas la précision requise avec une telle expérience. Vous avez besoin d'une approche différente" .

Mais voici une simulation de temps O (D). Au lieu de générer potentiellement des anniversaires déjà survenus encore et encore, je me concentre uniquement sur les nouveaux anniversaires. Autrement dit, je mélange tous les anniversaires possibles au début, puis je les passe simplement en revue. Bien sûr, cela signifie que je ne peux pas le faire emperors += 1. Au lieu de cela, j'ajoute le nombre attendu de nouveaux empereurs nécessaires pour rencontrer un nouvel anniversaire.

Avec 1000 simulations, il faut environ 0,6 seconde à mon ordinateur portable pour D = 365, 1,8 seconde pour D = 1000 ou 19 secondes pour 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. Je viens de l'essayer emperor += 1également, cela a pris environ 1,35, 4,1 et 62 secondes à la place:

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