Generate 4000 unique pseudo-random cartesian coordinates FASTER?

Question

The range for x and y is from 0 to 99.

I am currently doing it like this:

excludeFromTrainingSet = []
while len(excludeFromTrainingSet) < 4000:
    tempX = random.randint(0, 99)
    tempY = random.randint(0, 99)
    if [tempX, tempY] not in excludeFromTrainingSet:
        excludeFromTrainingSet.append([tempX, tempY])

But it takes ages and I really need to speed this up.

Any ideas?

Answer 1

Vincent Savard has an answer that's almost twice as fast as the first solution offered here.

---

Here's my take on it. It requires tuples instead of lists for hashability:

def method2(size):
    ret = set()
    while len(ret) < size:
        ret.add((random.randint(0, 99), random.randint(0, 99)))
    return ret

Just make sure that the limit is sane as other answerers have pointed out. For sane input, this is better algorithmically O(n) as opposed to O(n^2) because of the set instead of list. Also, python is much more efficient about loading locals than globals so always put this stuff in a function.

EDIT: Actually, I'm not sure that they're O(n) and O(n^2) respectively because of the probabilistic component but the estimations are correct if n is taken as the number of unique elements that they see. They'll both be slower as they approach the total number of available spaces. If you want an amount of points which approaches the total number available, then you might be better off using:

import random
import itertools

def method2(size, min_, max_):
    range_ = range(min_, max_)
    points = itertools.product(range_, range_)
    return random.sample(list(points), size)

This will be a memory hog but is sure to be faster as the density of points increases because it avoids looking at the same point more than once. Another option worth profiling (probably better than last one) would be

def method3(size, min_, max_):
    range_ = range(min_, max_)
    points = list(itertools.product(range_, range_))

    N = (max_ - min_)**2
    L =  N - size
    i = 1
    while i <= L:
        del points[random.randint(0, N - i)]
        i += 1
    return points

Answer 2

My suggestion :

def method2(size):
    randints = range(0, 100)
    excludeFromTrainingSet = set()

    while len(excludeFromTrainingSet) < size:
        excludeFromTrainingSet.add((random.choice(randints), random.choice(randints)))
    return excludeFromTrainingSet

Instead of generation 2 random numbers every time, you first generate the list of numbers from 0 to 99, then you choose 2 and appends to the list. As others pointed out, there are only 10 000 possibilities so you can't loop until you get 40 000, but you get the point.