Générer 4000 coordonnées cartésiennes pseudo-aléatoires uniques FASTER?

Question

La gamme pour x et y est de 0 à 99.

Je suis actuellement en train de faire comme ceci:

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

mais il faut les âges et je dois vraiment accélérer cela.

Des idées?

Answer 1

Vincent Savard a un answer presque deux fois plus rapide que la première solution proposée ici.

---

Voici mon point de vue. Il faut tuples au lieu des listes pour hashability:

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

Assurez-vous que la limite est sain d'esprit que d'autres answerers ont souligné. Pour une entrée sensée, c'est mieux algorithmiquement O (n) que O (n^2) à cause de l'ensemble au lieu de la liste. En outre, python est beaucoup plus efficace pour charger les locales que les globals, donc mettez toujours ce truc dans une fonction.

EDIT: En fait, je ne suis pas sûr qu'ils soient O (n) et O (n^2) respectivement à cause de la composante probabiliste mais les estimations sont correctes si n est pris comme le nombre d'éléments uniques ils voient. Ils seront tous les deux plus lents à mesure qu'ils s'approcheront du nombre total d'espaces disponibles. Si vous voulez un montant de points qui se rapproche du nombre total disponible, alors vous pourriez être mieux d'utiliser:

import random 
import itertools 

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

Ce sera un porc de mémoire mais il est sûr d'être plus rapide que la densité des augmentations de points car elle évite regardant le même point plus d'une fois.Une autre option de profilage vaut (probablement mieux que dernier) serait

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

Vous pouvez faire une table de recherche de valeurs aléatoires ... faire un index au hasard dans cette table de consultation, puis à travers l'étape avec un compteur d'incrément statique ...

Answer 3

Je suis sûr que quelqu'un va venez ici avec une utilisation de numpy, mais que diriez-vous d'utiliser un ensemble et un tuple? .: par exemple

excludeFromTrainingSet = set() 
while len(excludeFromTrainingSet) < 40000: 
    temp = (random.randint(0, 99), random.randint(0, 99)) 
    if temp not in excludeFromTrainingSet: 
     excludeFromTrainingSet.add(temp) 

EDIT: Est-ce une boucle infinie car il n'y a que 100^2 = 10000 résultats possibles, et vous attendez jusqu'à ce que vous obtenez 40000?

Answer 4

Générer nombres prendra inévitablement un certain temps. Mais vous effectuez une recherche linéaire O (n) sur excludeFromTrainingSet, ce qui prend beaucoup de temps, surtout plus tard dans le processus. Utilisez un ensemble à la place. Vous pouvez également envisager de générer un certain nombre de jeux de coordonnées, par ex. pendant la nuit et les pickle, de sorte que vous n'avez pas à générer de nouvelles données pour chaque test (ne sais pas ce que vous faites, donc cela pourrait ou ne peut pas aider). L'utilisation de tuples, comme quelqu'un l'a noté, n'est pas seulement un choix sémantiquement correct, cela peut aussi aider avec les performances (la création de tuple est plus rapide que la création de liste). Edit: idiot me, en utilisant tuples est requis lors de l'utilisation des ensembles, car les membres de l'ensemble doivent être lavable et les listes sont indisponibles.

Mais dans votre cas, votre boucle ne se termine pas parce que 0..99 est 100 nombres et deux-tuples d'entre eux ont seulement 100^2 = 10000 combinaisons uniques. Corrigez cela, puis appliquez ce qui précède.

Answer 5

Ma suggestion:

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

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

au lieu de la génération 2 nombres aléatoires à chaque fois, vous devez d'abord générer la liste des numéros de 0 à 99 , puis vous choisissez 2 et ajoute à la liste. Comme d'autres l'ont souligné, il n'y a que 10 000 possibilités, donc vous ne pouvez pas boucler jusqu'à ce que vous obteniez 40 000, mais vous avez compris.

Answer 6

Faites une liste de toutes les valeurs possibles (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)) 

Lecture aléatoire la liste:

from random import shuffle 
shuffle(allpairs) 

Lire le premier 'n' valeurs:

n = 4000 
trainingset = allpairs[:n] 

Cela fonctionne assez bien sur mon ordinateur portable.

Answer 7

Prendre le code de Vince Savard:

>>> from random import choice 
>>> def method2(size): 
...  randints = range(0, 100) 
...  excludeFromTrainingSet = set() 
...  while True: 
...   x = size - len(excludeFromTrainingSet) 
...   if not x: 
...    break 
...   else: 
...    excludeFromTrainingSet.add((choice(randints), choice(randints)) for _ in range(x)) 
...  return excludeFromTrainingSet 
... 
>>> s = method2(4000) 
>>> len(s) 
4000 

Ce n'est pas un algorithme car il doit faire face à des collisions, mais tuple génération rend tolérable. Cela fonctionne dans environ une seconde sur mon ordinateur portable.

Answer 8

## for py 3.0+ 
## generate 4000 points in 2D 
## 
import random 
maxn = 10000 
goodguys = 0 
excluded = [0 for excl in range(0, maxn)] 
for ntimes in range(0, maxn): 
    alea = random.randint(0, maxn - 1) 
    excluded[alea] += 1 
    if(excluded[alea] > 1): continue 
    goodguys += 1 
    if goodguys > 4000: break 
    two_num = divmod(alea, 100) ## Unfold the 2 numbers 
    print(two_num)