Le moyen le plus rapide d'échantillonner à partir du produit de deux listes

Question

Je voudrais obtenir n échantillons (sans remplacement) à partir du produit de deux listes. Comme indiqué ci-dessous, je suis en train de calculer l'ensemble du produit, puis de l'échantillonner, mais cela devient difficile à gérer pour les longues listes. Y a-t-il un moyen d'optimiser ce processus? Autrement dit, ne pas avoir à calculer le produit entier mais à échantillonner plus efficacement?

approche naïve actuelle (par erreur d'échantillonnage avec remplacement, comme il est indiqué ci-dessous):

from itertools import product 
from random import choice 

def get_sample(a,b,n): 
"""return n samples from the product a and b""" 
    D = list(product(a,b)) 
    D = [choice(D) for _ in range(n)] 

    return D 

Answer 1

Vous devriez être très bien si vous ne faites pas vraiment utilisation list si vous ne voulez un list; un échantillon non aléatoire peut être trouvé par

from itertools import product 

def get_first_n_sample(a,b,n): 
"""return n samples from the product a and b""" 
    D = product(a,b) 
    D = [D.next() for _ in range(n)] ## if you're on Python2, use xrange! 
    return D 

maintenant, si vous voulez juste des échantillons aléatoires de certaines combinaisons de a et b, un itérateur est clairement pas la bonne approche, et par conséquent, itertools ne sont pas non plus . Si l'on suppose a et b sont rapides sur l'accès aléatoire (par exemple list s, tuple s):

from random import choice 

def get_random_sample(a, b): 
    return (choice(a), choice(b)) 

obtenir néchantillons unique est plus complexe, bien que:

from random import sample 

def get_random_samples(a, b, n): 
    n_prod = len(a) * len(b) 
    indices = sample(range(n_prod), n) 
    return [(a[idx % len(a)], b[idx // len(a)]) for idx in indices] 

Answer 2

Malheureusement vous ne pouvez pas prendre un échantillon aléatoire d'un itérateur. Un itérateur (comme product) signifie que vous ne connaissez qu'une seule valeur à la fois et vous devez connaître plus d'une valeur pour fournir un caractère aléatoire.

L'approche naïve peut être plus efficace mais avec random.sample() comme ceci:

from itertools import product 
import random 
def get_sample(a,b,n): 
"""return n samples from the product a and b""" 
    D = list(product(a,b)) 
    return random.sample(D, n) 

Answer 3

Si vous voulez un échantillon remplacement, la façon dont votre code le fait actuellement, vous pouvez prendre des éléments aléatoires de product(a, b) avec (choice(a), choice(b):

sample = [(choice(a), choice(b)) for _ in xrange(n)] 

Si vous voulez un échantillon sans remplacement, faire un échantillon de paires aléatoires d'indices:

sample = [(a[i // len(b)], b[i % len(b)]) 
      for i in random.sample(xrange(len(a)*len(b)), n)]