3 вложенных цикла: оптимизация простой симуляции для скорости - PullRequest
Новая
       29

3 вложенных цикла: оптимизация простой симуляции для скорости

0 голосов
/ 10 декабря 2018

Фон

Мне попалась загадка.Вот оно:

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

  • Убить себя
  • Ничего не делать
  • Разделить себя на двух пришельцев (убиваясам)
  • раскололся на трех инопланетян (убивая себя)

Какова вероятность того, что инопланетный вид в конечном итоге полностью исчезнет?

Ссылка на источник и решение, проблема # 10

К сожалению, я не смог решить проблему теоретически.Затем я перешел к моделированию с использованием базовых симуляций Маркова и Монте-Карло.

Об этом мне не говорили в интервью.Я узнал проблему от друга, а затем нашел ссылку выше при поиске математических решений.

Переосмысление вопроса

Начнем с количества пришельцев n = 1.n имеет шанс не измениться, быть уменьшенным на 1, увеличенным на 1 и уменьшенным на 2,% 25 для каждого.Если n увеличивается, то есть умножается на инопланетян, мы повторяем эту процедуру еще раз n.Это соответствует тому, что каждый инопланетянин снова сделает свое дело.Я должен установить верхний предел, чтобы мы прекратили симуляцию и избежали сбоев.n, вероятно, увеличится, и мы повторяем n раз снова и снова.

Если инопланетяне как-то вымирают, мы прекращаем симуляцию снова, так как имитировать нечего.

Послеn достигает нуля или верхнего предела, мы также записываем население (это будет либо ноль, либо некоторое число >= max_pop).

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

Код 

from random import randint
import numpy as np

pop_max = 100
iter_max = 100000

results = np.zeros(iter_max, dtype=int)

for i in range(iter_max):
    n = 1
    while n > 0 and n < pop_max:
        for j in range(n):
            x = randint(1, 4)
            if x == 1:
                n = n - 1
            elif x == 2:
                continue
            elif x == 3:
                n = n + 1
            elif x == 4:
                n = n + 2
    results[i] = n

print( np.bincount(results)[0] / iter_max )

iter_max и pop_max действительно можно изменить, но ясчиталось, что если будет 100 инопланетян, вероятность их вымирания будет ничтожно мала.Хотя это всего лишь предположение, я ничего не сделал, чтобы рассчитать (более) правильный верхний предел для населения.

Этот код дает многообещающие результаты, довольно близкие к реальному ответу, который составляет примерно% 41,4.

Некоторые результаты 

> python aliens.py
0.41393
> python aliens.py
0.41808
> python aliens.py
0.41574
> python aliens.py
0.4149
> python aliens.py
0.41505
> python aliens.py
0.41277
> python aliens.py
0.41428
> python aliens.py
0.41407
> python aliens.py
0.41676

Последствия

Я согласен с результатами, но я не могу сказать то же самое в течение времени, которое занимает этот код.Это занимает около 16-17 секунд:)

Как мне улучшить скорость?Как я могу оптимизировать циклы (особенно цикл while)?Может быть, есть гораздо лучший подход или лучшие модели?

Ответы [ 2 ]

0 голосов
/ 10 декабря 2018

Никакого бесполезного решения, для моделирования 100k требуется около 5 с: 

from random import choices

def simulate_em():
    def spwn(aliens):
        return choices(range(-1,3), k=aliens)

    aliens = {1:1}
    i = 1
    while aliens[i] > 0 and aliens[i] < 100:    
        i += 1
        num = aliens[i-1]
        aliens[i] = num + sum(spwn(num))

    # commented for speed
    # print(f"Round {i:<5} had {aliens[i]:>20} alien alive.")
    return (i,aliens[i])

Тестирование (около 5 с на pyfiddle.io): 

from datetime import datetime

t = datetime.now()    
d = {}
wins = 0
test = 100000
for k in range(test):
    d[k] = simulate_em()
    wins += d[k][1]>=100

print(1-wins/test)         # 0.41532
print(datetime.now()-t)    # 0:00:04.840127

Так что для его выполнения требуется около 5 секунд100 тыс. Тестов ...

Выходные данные (из 2 прогонов): 

Round 1     had                    1 alien alive.
Round 2     had                    3 alien alive.
Round 3     had                    6 alien alive.
Round 4     had                    9 alien alive.
Round 5     had                    7 alien alive.
Round 6     had                   13 alien alive.
Round 7     had                   23 alien alive.
Round 8     had                   20 alien alive.
Round 9     had                   37 alien alive.
Round 10    had                   54 alien alive.
Round 11    had                   77 alien alive.
Round 12    had                  118 alien alive.

Round 1     had                    1 alien alive.
Round 2     had                    0 alien alive.

Используя amount_of_aliens + sum над choices(range(-1,3),k=amount_of_aliens), вы упрощаете суммирования и быстрее выполняете свои задания.?Если количество инопланетян падает ниже 0, они вымерли.

0 голосов
/ 10 декабря 2018

Вы можете векторизовать свой внутренний цикл, сгенерировав n случайных целых чисел одновременно с numpy (намного быстрее), и избавиться от всех ваших операторов if, используя арифметику вместо логической логики. 

while...: 
    #population changes by (-1, 0, +1, +2) for each alien
    n += np.random.randint(-1,3, size=n).sum()

Используя ваш точный код для всего остального (вы, вероятно, могли бы найти другие оптимизации в другом месте), я пошел с 21,2 секунды до 4,3 секунды, используя это одно изменение.

Без изменения алгоритма (то есть решение с помощью метода, отличного от Монте-Карло)Я не вижу никаких других радикальных изменений, которые могли бы сделать это намного быстрее, пока вы не начнете компилировать в машинный код (что, к счастью, очень легко, если у вас установлена ​​numba).

Я не буду давать полный урокпри своевременной компиляции, которую выполняет numba, но вместо этого я просто поделюсь своим кодом и запомню внесенные мной изменения: 

from time import time
import numpy as np
from numpy.random import randint
from numba import njit, int32, prange

@njit('i4(i4)')
def simulate(pop_max): #move simulation of one population to a function for parallelization
    n = 1
    while 0 < n < pop_max:
        n += np.sum(randint(-1,3,n))
    return n

@njit('i4[:](i4,i4)', parallel=True)
def solve(pop_max, iter_max):
    #this could be easily simplified to just return the raio of populations that die off vs survive to pop_max
    # which would save you some ram (though the speed is about the same)
    results = np.zeros(iter_max, dtype=int32) #numba needs int32 here rather than python int
    for i in prange(iter_max): #prange specifies that this loop can be parallelized
        results[i] = simulate(pop_max)
    return results

pop_max = 100
iter_max = 100000

t = time()
print( np.bincount(solve(pop_max, iter_max))[0] / iter_max )
print('time elapsed: ', time()-t)

Компиляция с распараллеливанием снижает скорость оценки примерно до0,15 секунды в моей системе.

...