Utilisation de numpy pour créer un tableau de toutes les combinaisons de deux tableaux

143

J'essaie de parcourir l'espace des paramètres d'une fonction à 6 paramètres pour étudier son comportement numérique avant d'essayer de faire quelque chose de complexe avec, donc je recherche un moyen efficace de le faire.

Ma fonction prend des valeurs flottantes données un tableau numpy de 6 dim en entrée. Voici ce que j'ai essayé de faire au départ:

J'ai d'abord créé une fonction qui prend 2 tableaux et génère un tableau avec toutes les combinaisons de valeurs des deux tableaux

from numpy import *
def comb(a,b):
    c = []
    for i in a:
        for j in b:
            c.append(r_[i,j])
    return c

Ensuite, reduce()j'appliquais cela à m copies du même tableau:

def combs(a,m):
    return reduce(comb,[a]*m)

Et puis j'évalue ma fonction comme ceci:

values = combs(np.arange(0,1,0.1),6)
for val in values:
    print F(val)

Cela fonctionne mais c'est trop lent. Je sais que l'espace des paramètres est énorme, mais cela ne devrait pas être si lent. Je n'ai échantillonné que 10 6 (un million) points dans cet exemple et il a fallu plus de 15 secondes pour créer le tableau values.

Connaissez-vous un moyen plus efficace de faire cela avec numpy?

Je peux modifier la façon dont la fonction Fprend ses arguments si c'est nécessaire.

Rafael S. Calsaverini
la source
Pour le produit cartésien le plus rapide que j'ai trouvé, voyez cette réponse . (Puisque la question est formulée assez différemment de celle-ci, je considère que les questions ne sont pas des doublons, mais la meilleure solution aux deux questions est la même.)
senderle

Réponses:

128

Dans la nouvelle version de numpy(> 1.8.x), numpy.meshgrid()fournit une implémentation beaucoup plus rapide:

la solution de @ pv

In [113]:

%timeit cartesian(([1, 2, 3], [4, 5], [6, 7]))
10000 loops, best of 3: 135 µs per loop
In [114]:

cartesian(([1, 2, 3], [4, 5], [6, 7]))

Out[114]:
array([[1, 4, 6],
       [1, 4, 7],
       [1, 5, 6],
       [1, 5, 7],
       [2, 4, 6],
       [2, 4, 7],
       [2, 5, 6],
       [2, 5, 7],
       [3, 4, 6],
       [3, 4, 7],
       [3, 5, 6],
       [3, 5, 7]])

numpy.meshgrid()utilisé pour être 2D seulement, maintenant il est capable de ND. Dans ce cas, 3D:

In [115]:

%timeit np.array(np.meshgrid([1, 2, 3], [4, 5], [6, 7])).T.reshape(-1,3)
10000 loops, best of 3: 74.1 µs per loop
In [116]:

np.array(np.meshgrid([1, 2, 3], [4, 5], [6, 7])).T.reshape(-1,3)

Out[116]:
array([[1, 4, 6],
       [1, 5, 6],
       [2, 4, 6],
       [2, 5, 6],
       [3, 4, 6],
       [3, 5, 6],
       [1, 4, 7],
       [1, 5, 7],
       [2, 4, 7],
       [2, 5, 7],
       [3, 4, 7],
       [3, 5, 7]])

Notez que l'ordre de la résultante finale est légèrement différent.

CT Zhu
la source
16
np.stack(np.meshgrid([1, 2, 3], [4, 5], [6, 7]), -1).reshape(-1, 3)donnera le bon ordre
Eric
@CT Zhu Existe-t-il un moyen simple de transformer cela afin que la matrice contenant les différents tableaux sous forme de colonnes soit utilisée à la place comme entrée?
Dole le
2
Il convient de noter que meshgrid ne fonctionne que pour les ensembles de plages plus petits, j'en ai un grand et j'obtiens une erreur: ValueError: la dimension maximale prise en charge pour un ndarray est de 32, trouvée 69
mikkom
158

Voici une implémentation purement numpy. C'est environ 5 fois plus rapide que d'utiliser itertools.


import numpy as np

def cartesian(arrays, out=None):
    """
    Generate a cartesian product of input arrays.

    Parameters
    ----------
    arrays : list of array-like
        1-D arrays to form the cartesian product of.
    out : ndarray
        Array to place the cartesian product in.

    Returns
    -------
    out : ndarray
        2-D array of shape (M, len(arrays)) containing cartesian products
        formed of input arrays.

    Examples
    --------
    >>> cartesian(([1, 2, 3], [4, 5], [6, 7]))
    array([[1, 4, 6],
           [1, 4, 7],
           [1, 5, 6],
           [1, 5, 7],
           [2, 4, 6],
           [2, 4, 7],
           [2, 5, 6],
           [2, 5, 7],
           [3, 4, 6],
           [3, 4, 7],
           [3, 5, 6],
           [3, 5, 7]])

    """

    arrays = [np.asarray(x) for x in arrays]
    dtype = arrays[0].dtype

    n = np.prod([x.size for x in arrays])
    if out is None:
        out = np.zeros([n, len(arrays)], dtype=dtype)

    m = n / arrays[0].size
    out[:,0] = np.repeat(arrays[0], m)
    if arrays[1:]:
        cartesian(arrays[1:], out=out[0:m, 1:])
        for j in xrange(1, arrays[0].size):
            out[j*m:(j+1)*m, 1:] = out[0:m, 1:]
    return out
pv.
la source
47
avez-vous déjà envisagé de soumettre ceci pour être inclus dans numpy? ce n'est pas la première fois que je cherche cette fonctionnalité et que je trouve votre message.
endolith
1
Il y a un bogue dans cette implémentation. Pour les tableaux de chaînes par exemple: tableaux [0] .dtype = "| S3" et tableaux [1] .dtype = "| S5". Il est donc nécessaire de trouver la chaîne la plus longue en entrée et d'utiliser son type dans out = np.zeros ([n, len (tableaux)], dtype = dtype)
norecces
38
FYI: semble avoir fait partie du package scikit-learn àfrom sklearn.utils.extmath import cartesian
Gus
2
Je viens de réaliser: c'est légèrement différent de itertools.combinations, car cette fonction respecte l'ordre des valeurs alors que les combinaisons ne le font pas, donc cette fonction renvoie plus de valeurs que les combinaisons. Toujours très impressionnant, mais malheureusement pas ce que je recherchais :(
David Marx
6
TypeError: slice indices must be integers or None or have an __index__ methodlancé parcartesian(arrays[1:], out=out[0:m,1:])
Boern
36

itertools.combinations est en général le moyen le plus rapide d'obtenir des combinaisons à partir d'un conteneur Python (si vous voulez en fait des combinaisons, c'est-à-dire des arrangements SANS répétitions et indépendants de l'ordre; ce n'est pas ce que votre code semble faire, mais je ne peux pas dire si c'est parce que votre code est bogué ou parce que vous utilisez la mauvaise terminologie).

Si vous voulez quelque chose de différent des combinaisons, peut-être que d'autres itérateurs dans itertools, productou permutations, pourraient mieux vous servir. Par exemple, il semble que votre code soit à peu près le même que:

for val in itertools.product(np.arange(0, 1, 0.1), repeat=6):
    print F(val)

Tous ces itérateurs produisent des tuples, pas des listes ou des tableaux numpy, donc si votre F est pointilleux pour obtenir spécifiquement un tableau numpy, vous devrez accepter la surcharge supplémentaire de construction ou d'effacement et de re-remplissage d'un à chaque étape.

Alex Martelli
la source
8

Tu peux faire quelque chose comme ça

import numpy as np

def cartesian_coord(*arrays):
    grid = np.meshgrid(*arrays)        
    coord_list = [entry.ravel() for entry in grid]
    points = np.vstack(coord_list).T
    return points

a = np.arange(4)  # fake data
print(cartesian_coord(*6*[a])

qui donne

array([[0, 0, 0, 0, 0, 0],
   [0, 0, 0, 0, 0, 1],
   [0, 0, 0, 0, 0, 2],
   ..., 
   [3, 3, 3, 3, 3, 1],
   [3, 3, 3, 3, 3, 2],
   [3, 3, 3, 3, 3, 3]])
Felippe
la source
2
Existe-t-il un moyen pour que NumPy accepte plus de 32 tableaux pour meshgrid? Cette méthode fonctionne pour moi tant que je ne passe pas plus de 32 tableaux.
Joelmob le
8

L'implémentation numpy suivante doit être d'env. 2x la vitesse de la réponse donnée:

def cartesian2(arrays):
    arrays = [np.asarray(a) for a in arrays]
    shape = (len(x) for x in arrays)

    ix = np.indices(shape, dtype=int)
    ix = ix.reshape(len(arrays), -1).T

    for n, arr in enumerate(arrays):
        ix[:, n] = arrays[n][ix[:, n]]

    return ix
Stefan van der Walt
la source
1
Cela semble bon. D'après mes tests rudimentaires, cela semble plus rapide que la réponse originale pour toutes les paires, triplets et 4-tuples de {1,2, ..., 100}. Après cela, la réponse originale l'emporte. Aussi, pour les futurs lecteurs qui cherchent à générer tous les k-tuples de {1, ..., n}, np.indices((n,...,n)).reshape(k,-1).Tfera l'affaire.
jme
Cela ne fonctionne que pour les entiers, tandis que la réponse acceptée fonctionne également pour les flottants.
FJC
7

Il semble que vous vouliez une grille pour évaluer votre fonction, auquel cas vous pouvez utiliser numpy.ogrid(open) ou numpy.mgrid(étoffé):

import numpy
my_grid = numpy.mgrid[[slice(0,1,0.1)]*6]
steabert
la source
6

vous pouvez utiliser np.array(itertools.product(a, b))

William Song
la source
np.array (list (itertools.product (l, l2)))
ZirconCode
4

Voici encore une autre façon, en utilisant NumPy pur, sans récursion, sans compréhension de liste et sans boucles for explicites. C'est environ 20% plus lent que la réponse originale, et il est basé sur np.meshgrid.

def cartesian(*arrays):
    mesh = np.meshgrid(*arrays)  # standard numpy meshgrid
    dim = len(mesh)  # number of dimensions
    elements = mesh[0].size  # number of elements, any index will do
    flat = np.concatenate(mesh).ravel()  # flatten the whole meshgrid
    reshape = np.reshape(flat, (dim, elements)).T  # reshape and transpose
    return reshape

Par exemple,

x = np.arange(3)
a = cartesian(x, x, x, x, x)
print(a)

donne

[[0 0 0 0 0]
 [0 0 0 0 1]
 [0 0 0 0 2]
 ..., 
 [2 2 2 2 0]
 [2 2 2 2 1]
 [2 2 2 2 2]]
étale-cohomologie
la source
3

Pour une implémentation numérique pure du produit cartésien de tableaux 1D (ou de listes python plates), il suffit d'utiliser meshgrid(), de rouler les axes avec transpose()et de remodeler à la sortie souhaitée:

 def cartprod(*arrays):
     N = len(arrays)
     return transpose(meshgrid(*arrays, indexing='ij'), 
                      roll(arange(N + 1), -1)).reshape(-1, N)

Notez que cela a la convention du dernier axe qui change le plus rapidement ("style C" ou "ligne-majeure").

In [88]: cartprod([1,2,3], [4,8], [100, 200, 300, 400], [-5, -4])
Out[88]: 
array([[  1,   4, 100,  -5],
       [  1,   4, 100,  -4],
       [  1,   4, 200,  -5],
       [  1,   4, 200,  -4],
       [  1,   4, 300,  -5],
       [  1,   4, 300,  -4],
       [  1,   4, 400,  -5],
       [  1,   4, 400,  -4],
       [  1,   8, 100,  -5],
       [  1,   8, 100,  -4],
       [  1,   8, 200,  -5],
       [  1,   8, 200,  -4],
       [  1,   8, 300,  -5],
       [  1,   8, 300,  -4],
       [  1,   8, 400,  -5],
       [  1,   8, 400,  -4],
       [  2,   4, 100,  -5],
       [  2,   4, 100,  -4],
       [  2,   4, 200,  -5],
       [  2,   4, 200,  -4],
       [  2,   4, 300,  -5],
       [  2,   4, 300,  -4],
       [  2,   4, 400,  -5],
       [  2,   4, 400,  -4],
       [  2,   8, 100,  -5],
       [  2,   8, 100,  -4],
       [  2,   8, 200,  -5],
       [  2,   8, 200,  -4],
       [  2,   8, 300,  -5],
       [  2,   8, 300,  -4],
       [  2,   8, 400,  -5],
       [  2,   8, 400,  -4],
       [  3,   4, 100,  -5],
       [  3,   4, 100,  -4],
       [  3,   4, 200,  -5],
       [  3,   4, 200,  -4],
       [  3,   4, 300,  -5],
       [  3,   4, 300,  -4],
       [  3,   4, 400,  -5],
       [  3,   4, 400,  -4],
       [  3,   8, 100,  -5],
       [  3,   8, 100,  -4],
       [  3,   8, 200,  -5],
       [  3,   8, 200,  -4],
       [  3,   8, 300,  -5],
       [  3,   8, 300,  -4],
       [  3,   8, 400,  -5],
       [  3,   8, 400,  -4]])

Si vous voulez changer le premier axe le plus rapidement ("style FORTRAN" ou "colonne-majeur"), changez simplement le orderparamètre reshape()comme ceci:reshape((-1, N), order='F')

RBF06
la source
1

Pandas mergepropose une solution naïve et rapide au problème:

# given the lists
x, y, z = [1, 2, 3], [4, 5], [6, 7]

# get dfs with same, constant index 
x = pd.DataFrame({'x': x}, index=np.repeat(0, len(x))
y = pd.DataFrame({'y': y}, index=np.repeat(0, len(y))
z = pd.DataFrame({'z': z}, index=np.repeat(0, len(z))

# get all permutations stored in a new df
df = pd.merge(x, pd.merge(y, z, left_index=True, righ_index=True),
              left_index=True, right_index=True)
Simone
la source