Советы по повышению эффективности моделирования при уменьшении дисперсии в Python

Question

Я использую Riddler 538 для практики кода.Написал простое моделирование в Python, но пришлось добавить еще один вложенный цикл, чтобы получить среднее значение для уменьшения дисперсии на выходе.Попытался запустить его, но через 45 минут я остановил его, думая, что должен быть способ повысить эффективность кода.

Для контекста проблема заключается в следующем: у вас есть радио и вы проигрываете 100 песен в день.Насколько большим должен быть плейлист, чтобы вероятность проигрывания одной и той же песни была равна 50%.

Мой подход заключается в увеличении размера списка воспроизведения (начиная с 7000) с 1 до тех пор, пока общее среднее значение средней вероятности повторного воспроизведения не станет равным 50%, используя 1000 как для размеров выборки, так и для числа.образцов.

Код:

import random

playlist = 7000
chance_of_replay = []
sample = 1000
mean_chance_of_replay = 0
replays = 0
temp_sum = 0

while mean_chance_of_replay > 0.5 or mean_chance_of_replay == 0.0:

    playlist += 1

    for j in range(0, sample):

        for i in range(1, sample + 1):

            songs_to_play = 100
            songs_played = []

            while songs_to_play > 0:

                song_pick = random.randint(1, playlist + 1)

                if song_pick not in songs_played:
                    songs_played.append(song_pick)
                    songs_to_play -= 1
                else:
                    replays += 1
                    break

        chance_of_replay.insert(j, (replays / sample))
        replays = 0

    for element in chance_of_replay:
        temp_sum = temp_sum + element

    mean_chance_of_replay = temp_sum/sample

print(playlist)

Answer 1

Шанс воспроизведения двух одинаковых песен уменьшается с увеличением размера списка воспроизведения.Считаете ли вы, что вероятность того, что одна и та же песня воспроизводится в плейлисте размером 7000, на самом деле ниже 50%?Если это так, то проверка любых более высоких значений приведет только к меньшим процентам, поэтому вы никогда не найдете свой ответ.

Если вы хотите провести симуляцию (в отличие от чисто математического подхода),Основная оптимизация, которую я могу найти, заключается в том, что вставка и добавление массива довольно сильно снижает производительность, если делать это много раз.То, что я сделал, было создать массив логических значений, которые хранят состояние, если какая-либо из данных песен была воспроизведена.Гораздо проще проверить, воспроизводилась ли данная песня, и не требуется никаких вставок, которые создают новые массивы за кадром.

Вот код:

from random import randint

playlist_size = 1
samples = 1000

songs_per_sample = 100

simulation_running = True
while simulation_running:
    replays = 0

    for _ in range(samples):
        songs_played = [False] * playlist_size

        for song_sample in range(songs_per_sample):
            song_to_play_index = randint(0, playlist_size - 1)

            if songs_played[song_to_play_index]:
                replays += 1

            songs_played[song_to_play_index] = True

    replay_chance = replays / (samples * songs_per_sample)

    if replay_chance <= 0.5:
        break

    playlist_size += 1

print(playlist_size)

Запуск этойна самом деле дает удивительный ответ, который намного ниже 7000!

Answer 2

Прежде чем посмотреть на проблемы с производительностью в вашем коде, сначала нужно решить более серьезную проблему: код находится в бесконечном цикле.

Список chance_of_replay никогда не очищается, ипеременная temp_sum никогда не устанавливается в 0. Из-за этого переменная mean_chance_of_replay всегда увеличивается, и ваш код будет работать вечно.

После исправления этих двух логических ошибок,Вы должны начать беспокоиться об оптимизации производительности.