更快生成4000个唯一伪随机笛卡尔坐标？

Question

x 和 y 的范围是从 0 到 99。

我现在是这样做的：

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])

但是这样做太慢了，我真的需要加快速度。

有什么好主意吗？

Answer 1

列出所有可能的 (x,y) 值：

allpairs = list((x,y) for x in xrange(99) for y in xrange(99))

# or with Py2.6 or later:
from itertools import product
allpairs = list(product(xrange(99),xrange(99)))

# or even taking DRY to the extreme
allpairs = list(product(*[xrange(99)]*2))

把这个列表打乱顺序：

from random import shuffle
shuffle(allpairs)

取出前 'n' 个值：

n = 4000
trainingset = allpairs[:n]

在我的笔记本电脑上运行得很快。

Answer 2

我的建议是：

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

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

与其每次都生成两个随机数，不如先生成一个从0到99的数字列表，然后再从中选择两个数字添加到列表里。正如其他人提到的，可能的组合只有1万种，所以你不能循环到得到4万种，但你明白我的意思。

Answer 3

Vincent Savard 提供了一个答案，速度几乎是这里第一个解决方案的两倍。

---

这是我对这个问题的看法。这个方法需要用元组而不是列表，因为元组可以被哈希。

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

只要确保限制条件合理，就像其他回答者提到的那样。对于合理的输入，这个算法在效率上是 O(n)，而不是 O(n^2)，因为它使用了集合而不是列表。此外，Python 在加载局部变量时比全局变量要高效很多，所以最好把这些代码放在一个函数里。

编辑：其实，我不太确定它们分别是 O(n) 和 O(n^2)，因为有概率因素的影响，但如果把 n 看作是它们所看到的唯一元素的数量，那么这些估算是正确的。随着接近可用空间的总数，它们的速度都会变慢。如果你想要的点数接近可用的总数，那么你可能更适合使用：

import random
import itertools

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

这个方法会占用很多内存，但随着点的密度增加，它肯定会更快，因为它避免了多次查看同一个点。还有一个值得测试的选项（可能比最后一个更好）是：

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