Случайные числа придают жизни остроту. Ну, по крайней мере, в мире программирования. Например, Bored API использует их для выбора занятий, способных развеять вашу скуку, а игры вроде Minecraft — для создания случайной местности. Есть и другие варианты практического использования случайных чисел. Например, шифрование в CloudFlare: там в качестве генератора случайных чисел для шифрования веб-запросов используется стена из лавовых ламп.
Давайте теперь поговорим об использовании случайных чисел в Python. Например, разберем следующую задачу с собеседования.
# Напишите функцию, которая будет принимать # целое число n и список чисел и генерировать случайное число # в диапазоне от 0 до n-1 (включительно), # причем этого числа не должно быть в списке.
Если необходимо сгенерировать случайное число, нам нужны две вещи. Во-первых, библиотека Python random, а во-вторых, библиотека math (чтобы округлять случайные числа до целых).
import random import math
Далее мы определим наш метод. Он должен принимать целое число и список целых чисел, который мы назовем nums.
def get_rand(n, nums):
pass
Решение 1
Для начала давайте обсудим «великоразумную» идею, которая первой приходит в голову. План следующий. Сначала находим случайное число в заданном диапазоне, а затем, если это число есть в списке, просто запускаем генератор случайных чисел снова. Повторяем до тех пор, пока не найдем валидное число.
Начнем с получения рандомного числа от 0 до n. В объекте random есть метод под названием random(), который возвращает случайное десятичное число от 0,0 до 1,0. Для получения числа от 0 до n мы будем умножать полученное десятичное число на n, а затем округлять в меньшую сторону при помощи math.floor().
rand_num = math.floor(random.random() * n)
Если каждый раз после получения случайного числа мы будем перебирать в цикле весь список, проверяя, нет ли там этого числа, время работы этой программы будет просто ужасным. Мы можем сделать кое-что получше. Давайте вспомним о типе данных, который используется во многих языках программирования, включая Python, — о множествах.
Множество (set) содержит уникальные неупорядоченные значения.
Множества можно представлять в виде облаков, в которых совершенно хаотично плавает куча чисел. И что особенно важно, эти числа не повторяются, они все уникальны. Если вы попытаетесь добавить во множество число 3, а оно там уже есть, вы не сможете внести его повторно.
С уникальностью элементов во множестве связан полезный для нас факт. Проверка того, содержится ли во множестве какое-либо число, имеет постоянную временную сложность, O(1). Это не суперэффективно, но все же лучше, чем сложность O(N), которая у нас была бы, если бы мы стали каждый раз перебирать все элементы в цикле.
Как нам реализовать множество? Начнем с вызова класса set при помощи его конструктора, set().
s = set()
Далее мы добавим в наше множество числа из списка.
for num in nums:
s.add(num)
Теперь мы будем проверять, содержится ли во множестве полученное нами случайное число. Если оно там есть, мы будем искать новое случайное число. Это можно реализовать при помощи цикла while, который будет запускаться, если случайное число содержится во множестве. Чисто для интереса можно добавить print — чтобы посмотреть, сколько раз методу придется заново найти случайное число, прежде чем будет найдено валидное.
while rand_num in s:
print("reroll")
rand_num = math.floor(random.random()*n)
И, наконец, мы возвращаем итоговое случайное число сразу после выхода из цикла while. Все вместе выглядит следующим образом:
def get_rand(n, nums):
rand_num = math.floor(random.random()*n)
s = set()
for num in nums:
s.add(num)
while rand_num in s:
print("reroll")
rand_num = math.floor(random.random()*n)
return rand_num
Если мы это испытаем, запустив get_rand(5, [0, 1, 2, 3]), мы получим 4 — единственное число, меньшее 5 и не входящее в список.
Как уже упоминалось, это решение не слишком эффективно. Этот алгоритм вполне может выбирать рандомные числа до бесконечности, если подходящее никак не будет попадаться. Например, это произойдет в ситуации, когда попросту не существует числа, отвечающего заданным критериям. Вот попробуйте запустить get_rand(5, [0, 1, 2, 3, 4]). Теперь в списке содержатся все целые числа до 5. Получилось как-то так?
reroll reroll reroll reroll reroll reroll reroll …
Если нет чисел, из которых можно выбрать подходящее, этот алгоритм будет работать бесконечно. Поэтому давайте подумаем о других вариантах, в которых учитывались бы крайние случаи и ликвидировалась возможность бесконечной работы.
Решение 2
Иногда мы подходим к решению задач по программированию так, будто они математические, и забываем, что мы-то разработчики. Так что всегда стоит спрашивать себя: «А не могу ли я самостоятельно построить то, что нужно для решения этой задачи?»
Представьте, что вместо того чтобы каждый раз проверять, есть ли наше случайное число в списке, мы создаем список валидных чисел, из которых потом выбираем случайное. Такой подход также решит нашу проблему с бесконечной работой программы, потому что если список возможных чисел будет пуст, мы сможем просто вернуть None.
Первая часть нашего метода остается прежней: мы берем числа из списка nums и помещаем их во множество. После этого нам нужно сделать пустой список. В него мы поместим все те валидные числа, из которых можно будет выбирать случайное.
def get_rand2(n, nums):
s = set()
for num in nums:
s.add(num)
poss_nums = []
Как нам найти валидные числа? Мы просто переберем в цикле каждое число от 0 до n и, если этого числа не будет во множестве, мы добавим его в список.
for num in range(n):
if num not in s:
poss_nums.append(num)
Если бы мы теперь запустили get_rand(5, [0, 1, 2, 3]), мы бы получили список poss_nums, содержащий только число 4.
Далее мы проверяем наш крайний случай. Просто смотрим, не пуст ли список, и если он действительно пуст, возвращаем None.
if not len(poss_nums):
return None
Что нам остается? Конечно, выбрать случайное число! Сначала мы выбираем случайный индекс, получая случайное число при помощи функции random.random() и умножая его на длину списка с валидными числами. Затем мы возвращаем число под этим индексом из списка валидных чисел.
rand_i = math.floor(random.random()*len(poss_nums)) return poss_nums[rand_i]
Вот как выглядит весь код полностью:
def get_rand2(n, nums):
s = set()
for num in nums:
s.add(num)
poss_nums = []
for num in range(n):
if num not in s:
poss_nums.append(num)
if not len(poss_nums):
return None
rand_i = math.floor(random.random()*len(poss_nums))
return poss_nums[rand_i]
Если мы теперь попробуем запустить get_rand(5, [0, 1, 2, 3, 4]) и вывести результат, мы получим None, потому что нет чисел, отвечающих заданным критериям. Ура! Больше никаких бесконечных циклов.
