Расчета средней минимальной длины из случайных чисел от 0 до 1, который добавляет до более чем 1


Мой учитель по информатике дал задание вычислить среднее после одного миллиарда испытания.

Его точное назначение было такое:

Рассмотрим генерации последовательности случайных чисел на интервале [0, 1) возможно с помощью математики.случайный() в цикле и добавлять их вместе. Сколько номеров вы планируете произвести в такой последовательности прежде чем сумма превышает 1.0 ? (т. е. вероятность)

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

Примеры:

  • 0.449 0.814
    • длина последовательности: 2
  • 0.167 0.138 0.028 0.934
    • длина последовательности: 4
  • 0.640 0.258 0.417
    • длина последовательности: 3
  • 0.911 0.212
    • длина последовательности: 2

Средняя из четырех длин 11/4 ≈ 2.75

Сколько в среднем один миллиард случайных последовательностей?

Мой код был такой:

import random

def genSequence():
  storenums = 0
  numTrials = 1000000000
  for x in range(0,numTrials):
    numberOfAttempts = 0
    getToOne = 0 
    while (getToOne < 1): #keeps on generating random numbers and adding it to getToOne until it reaches 1 or is over 1
      getToOne += random.random()
      numberOfAttempts += 1
    storenums = storenums + numberOfAttempts
    #print (x)
    #print(storenums)
  calculateAverage(storenums,numTrials)

def calculateAverage(num,den):
  average = num/den
  print(average)

genSequence()

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

Проблема с моим кодом заключается в том, что он не может достигнуть 1 млрд испытания и перестает работать примерно 227,035. Я уверен, что это проблемы с памятью, но я не знаю как это исправить. Что я могу сделать так, что он на самом деле завершает млрд испытания и желательно не в очень длинный промежуток времени.

Редактировать: мой учитель результат должен быть, но не в этом смысл, как мне нужно написать код. Получаем е значит я сделал все правильно.



Комментарии
1 ответ

Если я перепишу genSequence Так что он принимает numTrials в качестве аргумента, то я получу следующие сроки с CPython:

Python 3.6.4 (default, Dec 21 2017, 20:33:21) 
>>> from timeit import timeit
>>> timeit(lambda:genSequence(10**8), number=1)
2.71825759
62.77562193598715

Исходя из этого, потребуется около 10 минут, чтобы вычислить genSequence(10**9). Возможно, вы просто не ждать достаточно долго.

Этот вид петли-тяжелой цифровой код, как правило, выполняется намного быстрее, если использовать PyPy, который имеет "точно в срок" компилятор. Я получаю более чем в десять раз ускорение с в PyPy:

[PyPy 5.10.0 with GCC 4.2.1 Compatible Apple LLVM 9.0] on darwin
>>>> from timeit import timeit
>>>> timeit(lambda:genSequence(10**8), number=1)
2.71816679
5.389536142349243

На Python. вы должны быть в состоянии выполнить \$10^9\$ испытаниях в течение одной минуты (на моем компьютере это занимает 51 секунд).

Некоторые моменты обзора:


  1. Количество 1000000000 трудно читать — его можно легко спутать с 100000000 или 10000000000. Я бы написал 10**9 чтобы было понятно.

  2. Там нет необходимости для переменной numberOfAttempts; вы могли бы просто добавить один storenums на каждом цикле.

  3. Имя storenums это немного расплывчато. Это общая длина случайные последовательности, генерируемые до сих пор, поэтому имя нравится total_length было бы яснее.

  4. Аналогично, имя genSequence расплывчато. Это вычисляет среднее длина случайной последовательности, так что название типа mean_sequence_length было бы яснее.

  5. Значение константы 1 не совсем ясно. Я бы дал ему имя нравится target_sum.

  6. Когда переменная цикла, как x не используется, это обычные для нее название _.

  7. range(0,numTrials) может быть написано range(numTrials).

Пересмотренный код:

import random

def mean_sequence_length(trials, target_sum=1.0):
"""Return mean length of random sequences adding up to at least
target_sum (carrying out the given number of trials).

"""
total_length = 0
for _ in range(trials):
current_sum = 0.0
while current_sum < target_sum:
current_sum += random.random()
total_length += 1
return total_length / trials

9
ответ дан 8 февраля 2018 в 03:02 Источник Поделиться