Slow List Generation

This function works as expected, but it’s very slow on large test cases. Can you figure out what’s wrong and fix it without changing its statistical distribution?

Make the generate_random_list function run faster than 100ms for both tests.

Problem:

import random

def generate_random_list(n):
    result = []
    for i in range(n):
        x = random.randint(1,n)
        if x not in result:
            result.append(x)
    return result

## Don't edit testcases below, it's cheating!

import time

# SMALL TEST
start = time.time()
generate_random_list(100)
test_time = (time.time() - start) * 1000
print(f'Small test took {test_time:.1f} ms')
assert test_time < 100, 'Too slow!'

# LARGE TEST
start = time.time()
generate_random_list(20000)
test_time = (time.time() - start) * 1000
print(f'Large test took {test_time:.1f} ms')
assert test_time < 100, 'Too slow!'

Solution #1:

Append to the list instead of generating

import random

def generate_random_list(n):
    result = []
    x = []
    for i in range(n):
        # x = random.randint(1,n)
        x.append(random.randint(1,n))
        if x not in result:
            result.append(x)
    return result

Solution #2:

Use shuffle to create a predefined list.

import random

def generate_random_list(n):
    result = []
    for i in range(n):
       result.append(i+1)
    return(random.shuffle(result))