4

Предположим, мне нужно создать огромный (порядка миллиона) список случайных чисел. Но не просто случайных чисел, а неодинаковых случайных чисел. Вопрос в следующем: как сделать это наиболее быстрым способом?

Варианты:

1: (проверка каждого элемента перед добавлением)

import random
nums = []
for i in range(10 ** 6):
    while True:
        x = random.random()
        if nums.find() + 1:
            nums.append(x)
            break
        else:
            continue

2: (проверка после генерации всего списка)

import random
while True:
    for i in range(10 ** 6):
        nums.append(random.random())
    if list(set(nums)) == nums: break
    else: continue

3: (варварский ☺)

import random
nums = []
x = random.random()
for i in range(10 ** 6):
    nums.append(x * i)

Может, есть и какой-то еще вариант с применениями специальных методов, — возможно из других модулей — предназначенных специально для генерации неодинаковых чисел. Если таковой имеется, подскажите его, пожалуйста.

Так какой вариант лучше? Или имеется более быстрый алгоритм?

13
  • Первые две идеи ок, но реализация плохая в обоих случаях. Commented 6 сент. 2023 в 18:37
  • stackoverflow.com/a/8505754/15035314 Commented 6 сент. 2023 в 19:26
  • 1
    Миллион - это не огромный. Огромный - это когда список не помещается в память. Commented 7 сент. 2023 в 7:03
  • 1
    Например, во-втором случае вероятность того, что в списке будет именно миллион элементов очень мала. И если там выпадет хотя бы два одинаковых числа, то цикл вообще никогда не завершится. Не говоря уже о том, что порядок элементов после list(set(nums)) вряд ли будет совпадать с исходным. Commented 7 сент. 2023 в 7:37
  • 3
    @Qwertiy, списки в Питоне сравниваются по содержимому, в отличие от JavaScript. Commented 7 сент. 2023 в 16:21

4 ответа 4

6

Первый вариант

Человек может догадаться что значит if nums.find() + 1:, компилятор - нет. В выражении не упоминается x, список в питоне не имеет метода find. Если предположить, что подразумевалось if x not in nums:, то способ рабочий. На моём компьютере он выполнится за полтора часа.

Второй вариант

Если условие if list(set(nums)) == nums: окажется истинным, то мы действительно получим список из миллиона уникальных чисел в nums. К сожалению комбинация list(set(...)) перемешивает свой аргумент определённым образом. Равенство выполнится если все числа уникальны и их порядок в nums совпадёт с результатом list(set(...)). Какова вероятность этого события? 1 / (106!) ≈ 10-5565709. Одна итерация цикла занимает примерно секунду. До получения результата нужно будет подождать около 105565709 секунд. Возраст вселенной - 1018 секунд. Ждать придётся долго. Но это только полбеды. Даже если бы у нас было в запасе это время, нужная комбинация не будет сгенерирована, скорее всего. Причину я опущу чтобы не утомлять вас. Вердикт - способ не рабочий.

Если заменить условие на if len(set(nums)) == 10 ** 6: то способ окажется рабочим и очень быстрым - будет работать около секунды.

Третий вариант

Числа не случайные. Если вас такая случайность устраивает - хорошо. Но внимательный наблюдатель заметит что числа растут, следуют с определённым интервалом. Короче - слишком заметны недостатки.

Решения

Примерно 0.69 секунды.

import random

s = set()
while len(s) < 1_000_000:
    s.add(random.random())
l = list(s)

Из них 0.16с уходит на собственно генерацию. Остальные 0.53с - работа с множеством.

Этот вариант чуть быстрее - 0.6с:

import random

size = 1_000_000
s = set()
while len(s) < size:
    s.update(random.random() for _ in range(size - len(s)))
l = list(s)

Ещё быстрее - 0.55c:

import random

size = 1_000_000
s = set(random.random() for _ in range(size))
while len(s) < size:
    s.update(random.random() for _ in range(size - len(s)))
l = list(s)

Часто ли во втором примере потребуется больше одной итерации? Часто ли в последнем примере понадобится заходить в цикл? На оба вопроса ответ один: вероятность что потребуется дополнять множество равна 6·10-5. Другими словами - редко. Если мой компьютер в цикле будет генерировать наборы случайных чисел, ему понадобится дополнять набор в среднем раз в два с половиной часа.

P.S. Честно говоря, первый вариант мне нравиться больше. Просто и достаточно быстро.

P.P.S. Более интересная задача возникнет если добавить ограничение на память при генерации.

10
  • Скажите, а почему вы между импортом и кодом вставляете две пустые строчки? По стандартам вроде полагается одна. Или я путаю?
    – Глeб
    Commented 7 сент. 2023 в 9:39
  • @Глеб, вы правы, ничего не путаете. Я неправильно запомнил и все блоки в глобальной области отделял двумя строками. ПЕП8 этого не требует. Поправил на одну строку. Спасибо! Commented 7 сент. 2023 в 9:59
  • 2
    Кстати, а есть причины считать, что вещественные числа вообще могут повторяться? Эксперимент говорит, что всё получается за первую генерацию: tio.run/##K6gsycjPM/7/PzO3IL@oRKEoMS8lP5eLKy2/…. Не означает ли повтор числа то, что мы выгребли весь возможный диапазон случайных чисел и новое вообще не можем получить? Впрочем, с проверкой и циклом надёжнее, по крайней мере в том плане, что если уж код завершится, то мы точно будем иметь нужное количество чисел.
    – Qwertiy
    Commented 7 сент. 2023 в 10:18
  • @Qwertiy, всё так и есть. В последнем варианте вероятность зайти в цикл очень низкая. Но для корректности сделано так. Можно было бы генерировать список без проверки. Не думаю что тестами такой "дефект" ловится. Commented 7 сент. 2023 в 10:25
  • @StanislavVolodarskiy, я просто не в курсе, что гарантирует random. Если там только одно значение в состоянии, то получится, что после первого повтора будет повторяться всё и в том же порядке. Но я не знаю ничего про его внутренности в питоне.
    – Qwertiy
    Commented 7 сент. 2023 в 10:39
3

Вероятно, вам подойдёт random.sample()

import random

print([x/1000 for x in random.sample(range(1000), 10)])
3
import uuid

s=[uuid.uuid4().int for i in range(1_000_000)]
l=list(set(s))

...
19338761825466288640265314643851179312
178303052562301544546569716401959751820
147718195392286393968890593237377029069
196091551904263230486818310589002110116
42826159964564327211771179483953807288
297151613728264239240276251569460736275
...

https://docs.python.org/3/library/uuid.html

2

Что-то никто не написал про перемешивание с помощью shuffle. Ну, тогда напишу я.

Чистый питон:

from random import shuffle

n = 1_000_000
lst = [i/(n+1) for i in range(n)]
shuffle(lst)

Долго - порядка 0.75с.

Но ведь у нас есть Numpy:

import numpy as np

n = 1_000_000
arr = np.arange(n) / (n+1)
np.random.shuffle(arr)

Быстро - около 30мс в Google Colab.

Ваш ответ

Нажимая «Отправить ответ», вы соглашаетесь с условиями пользования и подтверждаете, что прочитали политику конфиденциальности.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.