Python实现无重复数字

当我们想要取的一些不重复的数字时，通常我们会想到random.sample方法

import random

print(random.sample(range(0, 10), 4))
# [5, 1, 0, 2]

但是这样只能保证每次运行这行代码时的数字是不重复的，如果要多次运行上面的代码就会有重复的数字出现。

最先想到的方法就是将每次取到数字都放在一个set内，每次产生新的随机数字时，先判断它是否在这个set内

import random
import functools
import time


def scale_time(fn):
    functools.wraps(fn)

    def wrapper(*args, **kw):
        start_time = time.time()
        result = fn(*args, **kw)
        end_time = time.time()
        print(f"{end_time - start_time}")
        return result

    return wrapper


@scale_time
def test():
    result_set = set()

    while len(result_set) < 9999:
        _data = random.sample(range(0, 10000), 1)
        result_set = result_set | set(_data)


test()
# 6.2531819343566895

从上面代码可以看到，这种方式效率是比较低的，越到后面，产生不重复随机数的概率就会越来越低，就需要重试更多的次数

有没有优化的方式呢？那就是下面要讲的，利用列表来取不重复的随机数，每次取出来的随机数都能保证和之前取出来的不重复

import random
import functools
import time


def scale_time(fn):
    functools.wraps(fn)

    def wrapper(*args, **kw):
        start_time = time.time()
        result = fn(*args, **kw)
        end_time = time.time()
        print(f"{end_time - start_time}")
        return result

    return wrapper


@scale_time
def test():
    result_set = set()
    data = list(range(0, 10000))

    while len(result_set) < 9999:
        _data = random.randint(0, len(data)-1)
        result_set.add(data[_data])
        data.pop(_data)

test()
# 0.027987957000732422

上面的代码会pop原来数组的值，如果要继续优化，可以不pop，而是修改元素的位置

import random
import functools
import time


def scale_time(fn):
    functools.wraps(fn)

    def wrapper(*args, **kw):
        start_time = time.time()
        result = fn(*args, **kw)
        end_time = time.time()
        print(f"{end_time - start_time}")
        return result

    return wrapper


@scale_time
def test():
    result_set = set()
    data = list(range(0, 10000))

    _index = len(data) - 1
    while len(result_set) < 9999:
        _data = random.randint(0, _index)
        result_set.add(data[_data])
        _index -= 1
        data[-len(result_set)], data[_data] = data[_data], data[-len(result_set)]

test()
# 0.02704787254333496