Numpy: декартово произведение точек массива x и y в один массив 2D точек

канонический cartesian_product (почти)

существует множество подходов к этой проблеме с разными свойствами. Некоторые из них быстрее, чем другие, а некоторые более общего назначения. После Большого тестирования и настройки, я обнаружил, что следующая функция, которая вычисляет n-мерный cartesian_product, быстрее, чем большинство других для многих входов. Для пары подходов, которые немного сложнее, но даже немного быстрее во многих случаях, см. ответ от Павел Panzer.

учитывая этот ответ, это уже не быстрый реализация декартова произведения в numpy это мне известно. Тем не менее, я думаю, что его простота будет продолжать делать его полезным ориентиром для будущего улучшения:

def cartesian_product(*arrays):
    la = len(arrays)
    dtype = numpy.result_type(*arrays)
    arr = numpy.empty([len(a) for a in arrays] + [la], dtype=dtype)
    for i, a in enumerate(numpy.ix_(*arrays)):
        arr[...,i] = a
    return arr.reshape(-1, la)

стоит отметить, что эта функция использует ix_ необычным способом; в то время как документально использование ix_ это создать индексына массив, он просто так получается, что массивы с одинаковой формой могут быть использованы для широковещательного назначения. Большое спасибо mgilson, который вдохновил меня попробовать использовать ix_ таким образом, и unutbu, который предоставил некоторые чрезвычайно полезные отзывы об этом ответе, включая предложение использовать numpy.result_type.

заметных альтернатив

иногда быстрее писать непрерывные блоки памяти в порядке Фортрана. Вот в чем основа этого альтернатива, cartesian_product_transpose, который оказался быстрее на некоторых машинах, чем cartesian_product (см. ниже). Однако ответ пола Пензера, который использует тот же принцип, еще быстрее. Тем не менее, я включаю это здесь для заинтересованных читателей:

def cartesian_product_transpose(*arrays):
    broadcastable = numpy.ix_(*arrays)
    broadcasted = numpy.broadcast_arrays(*broadcastable)
    rows, cols = numpy.prod(broadcasted[0].shape), len(broadcasted)
    dtype = numpy.result_type(*arrays)

    out = numpy.empty(rows * cols, dtype=dtype)
    start, end = 0, rows
    for a in broadcasted:
        out[start:end] = a.reshape(-1)
        start, end = end, end + rows
    return out.reshape(cols, rows).T

после того, как я понял подход Панцера, я написал новую версию, которая почти так же быстро, как и его, и почти так же просто, как cartesian_product:

def cartesian_product_simple_transpose(arrays):
    la = len(arrays)
    dtype = numpy.result_type(*arrays)
    arr = numpy.empty([la] + [len(a) for a in arrays], dtype=dtype)
    for i, a in enumerate(numpy.ix_(*arrays)):
        arr[i, ...] = a
    return arr.reshape(la, -1).T

это, кажется, имеет некоторые постоянные накладные расходы, что делает его работать медленнее, чем Танковые для небольших входов. Но для больших входов, во всех тестах, которые я запускал, он выполняет так же хорошо, как и его самая быстрая реализация (cartesian_product_transpose_pp).

в следующих разделах, я включаю некоторые тесты других альтернатив. Они сейчас несколько устарели, но вместо того, чтобы дублировать усилия, я решил оставить их здесь из исторического интереса. Для современных тестов см. ответ Panzer, а также Нико Schlömer ' s.

тесты на альтернативы

вот батарея тестов, которые показывают повышение производительности, что некоторые из этих функций обеспечивают относительно ряда альтернатив. Все тесты, показанные здесь, были выполнены на четырехъядерной машине, работающей под управлением Mac OS 10.12.5, Python 3.6.1 и numpy 1.12.1. Известно, что вариации аппаратного и программного обеспечения дают разные результаты, поэтому YMMV. Выполнить эти тесты для себя, чтобы быть уверенным!

определение:

import numpy
import itertools
from functools import reduce

### Two-dimensional products ###

def repeat_product(x, y):
    return numpy.transpose([numpy.tile(x, len(y)), 
                            numpy.repeat(y, len(x))])

def dstack_product(x, y):
    return numpy.dstack(numpy.meshgrid(x, y)).reshape(-1, 2)

### Generalized N-dimensional products ###

def cartesian_product(*arrays):
    la = len(arrays)
    dtype = numpy.result_type(*arrays)
    arr = numpy.empty([len(a) for a in arrays] + [la], dtype=dtype)
    for i, a in enumerate(numpy.ix_(*arrays)):
        arr[...,i] = a
    return arr.reshape(-1, la)

def cartesian_product_transpose(*arrays):
    broadcastable = numpy.ix_(*arrays)
    broadcasted = numpy.broadcast_arrays(*broadcastable)
    rows, cols = numpy.prod(broadcasted[0].shape), len(broadcasted)
    dtype = numpy.result_type(*arrays)

    out = numpy.empty(rows * cols, dtype=dtype)
    start, end = 0, rows
    for a in broadcasted:
        out[start:end] = a.reshape(-1)
        start, end = end, end + rows
    return out.reshape(cols, rows).T

# from https://stackoverflow.com/a/1235363/577088

def cartesian_product_recursive(*arrays, out=None):
    arrays = [numpy.asarray(x) for x in arrays]
    dtype = arrays[0].dtype

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

    m = n // arrays[0].size
    out[:,0] = numpy.repeat(arrays[0], m)
    if arrays[1:]:
        cartesian_product_recursive(arrays[1:], out=out[0:m,1:])
        for j in range(1, arrays[0].size):
            out[j*m:(j+1)*m,1:] = out[0:m,1:]
    return out

def cartesian_product_itertools(*arrays):
    return numpy.array(list(itertools.product(*arrays)))

### Test code ###

name_func = [('repeat_product',                                                 
              repeat_product),                                                  
             ('dstack_product',                                                 
              dstack_product),                                                  
             ('cartesian_product',                                              
              cartesian_product),                                               
             ('cartesian_product_transpose',                                    
              cartesian_product_transpose),                                     
             ('cartesian_product_recursive',                           
              cartesian_product_recursive),                            
             ('cartesian_product_itertools',                                    
              cartesian_product_itertools)]

def test(in_arrays, test_funcs):
    global func
    global arrays
    arrays = in_arrays
    for name, func in test_funcs:
        print('{}:'.format(name))
        %timeit func(*arrays)

def test_all(*in_arrays):
    test(in_arrays, name_func)

# `cartesian_product_recursive` throws an 
# unexpected error when used on more than
# two input arrays, so for now I've removed
# it from these tests.

def test_cartesian(*in_arrays):
    test(in_arrays, name_func[2:4] + name_func[-1:])

x10 = [numpy.arange(10)]
x50 = [numpy.arange(50)]
x100 = [numpy.arange(100)]
x500 = [numpy.arange(500)]
x1000 = [numpy.arange(1000)]

вы можете просто сделать нормальное понимание списка в python

x = numpy.array([1,2,3])
y = numpy.array([4,5])
[[x0, y0] for x0 in x for y0 in y]

, который должен дать вам

[[1, 4], [1, 5], [2, 4], [2, 5], [3, 4], [3, 5]]

Я тоже был заинтересован в этом и сделал небольшое сравнение производительности, возможно, несколько яснее, чем в ответе @senderle.

для двух массивов (классический случай):

в течение четырех массивов:

(обратите внимание, что длина массива составляет всего несколько десятков записей здесь.)

---

код для воспроизведения графиков:

from functools import reduce
import itertools
import numpy
import perfplot


def dstack_product(arrays):
    return numpy.dstack(
        numpy.meshgrid(*arrays, indexing='ij')
        ).reshape(-1, len(arrays))


# Generalized N-dimensional products
def cartesian_product(arrays):
    la = len(arrays)
    dtype = numpy.find_common_type([a.dtype for a in arrays], [])
    arr = numpy.empty([len(a) for a in arrays] + [la], dtype=dtype)
    for i, a in enumerate(numpy.ix_(*arrays)):
        arr[..., i] = a
    return arr.reshape(-1, la)


def cartesian_product_transpose(arrays):
    broadcastable = numpy.ix_(*arrays)
    broadcasted = numpy.broadcast_arrays(*broadcastable)
    rows, cols = reduce(numpy.multiply, broadcasted[0].shape), len(broadcasted)
    dtype = numpy.find_common_type([a.dtype for a in arrays], [])

    out = numpy.empty(rows * cols, dtype=dtype)
    start, end = 0, rows
    for a in broadcasted:
        out[start:end] = a.reshape(-1)
        start, end = end, end + rows
    return out.reshape(cols, rows).T


# from https://stackoverflow.com/a/1235363/577088
def cartesian_product_recursive(arrays, out=None):
    arrays = [numpy.asarray(x) for x in arrays]
    dtype = arrays[0].dtype

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

    m = n // arrays[0].size
    out[:, 0] = numpy.repeat(arrays[0], m)
    if arrays[1:]:
        cartesian_product_recursive(arrays[1:], out=out[0:m, 1:])
        for j in range(1, arrays[0].size):
            out[j*m:(j+1)*m, 1:] = out[0:m, 1:]
    return out


def cartesian_product_itertools(arrays):
    return numpy.array(list(itertools.product(*arrays)))


perfplot.show(
    setup=lambda n: 4*(numpy.arange(n, dtype=float),),
    n_range=[2**k for k in range(6)],
    kernels=[
        dstack_product,
        cartesian_product,
        cartesian_product_transpose,
        cartesian_product_recursive,
        cartesian_product_itertools
        ],
    logx=True,
    logy=True,
    xlabel='len(a), len(b)',
    equality_check=None
    )

основываясь на Образцовой наземной работе @senderle, я придумал две версии - одну для C и одну для макетов Fortran, которые часто немного быстрее.

• cartesian_product_transpose_pp - это - в отличие от @senderle это cartesian_product_transpose, который использует совершенно другую стратегию - версии cartesion_product который использует более благоприятную схему транспонирования памяти + некоторые очень незначительные оптимизации.
• cartesian_product_pp палочки с оригинальной планировкой памяти. Что делает его быстрым, так это его непрерывное копирование. Непрерывные копии оказываются настолько быстрее, что копирование полного блока памяти, даже если только часть его содержит допустимые данные, предпочтительнее, чем копирование только допустимых битов.

некоторые perfplots. Я сделал отдельные для макетов C и Fortran, потому что это разные задачи IMO.

имена, заканчивающиеся на " pp " - это мои подходы.

1) много крошечных факторов (2 элемента каждый)

2) много малых факторов (4 элемента каждый)

3) три фактора равной длины

4) два фактора равной длины

код (нужно сделать отдельные трассы для каждого сюжета b / c я не мог понять, как сбросить; также нужно отредактировать / прокомментировать in / out соответствующим образом):

import numpy
import numpy as np
from functools import reduce
import itertools
import timeit
import perfplot

def dstack_product(arrays):
    return numpy.dstack(
        numpy.meshgrid(*arrays, indexing='ij')
        ).reshape(-1, len(arrays))

def cartesian_product_transpose_pp(arrays):
    la = len(arrays)
    dtype = numpy.result_type(*arrays)
    arr = numpy.empty((la, *map(len, arrays)), dtype=dtype)
    idx = slice(None), *itertools.repeat(None, la)
    for i, a in enumerate(arrays):
        arr[i, ...] = a[idx[:la-i]]
    return arr.reshape(la, -1).T

def cartesian_product(arrays):
    la = len(arrays)
    dtype = numpy.result_type(*arrays)
    arr = numpy.empty([len(a) for a in arrays] + [la], dtype=dtype)
    for i, a in enumerate(numpy.ix_(*arrays)):
        arr[...,i] = a
    return arr.reshape(-1, la)

def cartesian_product_transpose(arrays):
    broadcastable = numpy.ix_(*arrays)
    broadcasted = numpy.broadcast_arrays(*broadcastable)
    rows, cols = numpy.prod(broadcasted[0].shape), len(broadcasted)
    dtype = numpy.result_type(*arrays)

    out = numpy.empty(rows * cols, dtype=dtype)
    start, end = 0, rows
    for a in broadcasted:
        out[start:end] = a.reshape(-1)
        start, end = end, end + rows
    return out.reshape(cols, rows).T

from itertools import accumulate, repeat, chain

def cartesian_product_pp(arrays, out=None):
    la = len(arrays)
    L = *map(len, arrays), la
    dtype = numpy.result_type(*arrays)
    arr = numpy.empty(L, dtype=dtype)
    arrs = *accumulate(chain((arr,), repeat(0, la-1)), np.ndarray.__getitem__),
    idx = slice(None), *itertools.repeat(None, la-1)
    for i in range(la-1, 0, -1):
        arrs[i][..., i] = arrays[i][idx[:la-i]]
        arrs[i-1][1:] = arrs[i]
    arr[..., 0] = arrays[0][idx]
    return arr.reshape(-1, la)

def cartesian_product_itertools(arrays):
    return numpy.array(list(itertools.product(*arrays)))


# from https://stackoverflow.com/a/1235363/577088
def cartesian_product_recursive(arrays, out=None):
    arrays = [numpy.asarray(x) for x in arrays]
    dtype = arrays[0].dtype

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

    m = n // arrays[0].size
    out[:, 0] = numpy.repeat(arrays[0], m)
    if arrays[1:]:
        cartesian_product_recursive(arrays[1:], out=out[0:m, 1:])
        for j in range(1, arrays[0].size):
            out[j*m:(j+1)*m, 1:] = out[0:m, 1:]
    return out

### Test code ###
if False:
  perfplot.save('cp_4el_high.png',
    setup=lambda n: n*(numpy.arange(4, dtype=float),),
                n_range=list(range(6, 11)),
    kernels=[
        dstack_product,
        cartesian_product_recursive,
        cartesian_product,
#        cartesian_product_transpose,
        cartesian_product_pp,
#        cartesian_product_transpose_pp,
        ],
    logx=False,
    logy=True,
    xlabel='#factors',
    equality_check=None
    )
else:
  perfplot.save('cp_2f_T.png',
    setup=lambda n: 2*(numpy.arange(n, dtype=float),),
    n_range=[2**k for k in range(5, 11)],
    kernels=[
#        dstack_product,
#        cartesian_product_recursive,
#        cartesian_product,
        cartesian_product_transpose,
#        cartesian_product_pp,
        cartesian_product_transpose_pp,
        ],
    logx=True,
    logy=True,
    xlabel='length of each factor',
    equality_check=None
    )

по состоянию на Октября. 2017, numpy теперь имеет общий np.stack функция, которая принимает параметр оси. Используя его, мы можем получить "обобщенное декартово произведение", используя метод "dstack и meshgrid":

import numpy as np
def cartesian_product(*arrays):
    ndim = len(arrays)
    return np.stack(np.meshgrid(*arrays), axis=-1).reshape(-1, ndim)

обратите внимание на

я использовал @kennytm ответ некоторое время, но при попытке сделать то же самое в TensorFlow, но я обнаружил, что TensorFlow не имеет эквивалента numpy.repeat(). После небольшого эксперимента я думаю, что нашел более общее решение для произвольных векторов точек.

для numpy:

import numpy as np

def cartesian_product(*args: np.ndarray) -> np.ndarray:
    """
    Produce the cartesian product of arbitrary length vectors.

    Parameters
    ----------
    np.ndarray args
        vector of points of interest in each dimension

    Returns
    -------
    np.ndarray
        the cartesian product of size [m x n] wherein:
            m = prod([len(a) for a in args])
            n = len(args)
    """
    for i, a in enumerate(args):
        assert a.ndim == 1, "arg {:d} is not rank 1".format(i)
    return np.concatenate([np.reshape(xi, [-1, 1]) for xi in np.meshgrid(*args)], axis=1)

и для тензорного потока:

import tensorflow as tf

def cartesian_product(*args: tf.Tensor) -> tf.Tensor:
    """
    Produce the cartesian product of arbitrary length vectors.

    Parameters
    ----------
    tf.Tensor args
        vector of points of interest in each dimension

    Returns
    -------
    tf.Tensor
        the cartesian product of size [m x n] wherein:
            m = prod([len(a) for a in args])
            n = len(args)
    """
    for i, a in enumerate(args):
        tf.assert_rank(a, 1, message="arg {:d} is not rank 1".format(i))
    return tf.concat([tf.reshape(xi, [-1, 1]) for xi in tf.meshgrid(*args)], axis=1)

The Scikit-learn пакет имеет быструю реализацию именно этого:

from sklearn.utils.extmath import cartesian
product = cartesian((x,y))

обратите внимание, что соглашение этой реализации отличается от того, что вы хотите, если вы заботитесь о порядке вывода. Для вашего точного заказа, вы можете сделать

product = cartesian((y,x))[:, ::-1]

в более общем случае, если у вас есть два 2d массива numpy a и b, и вы хотите объединить каждую строку a в каждую строку b (декартово произведение строк, вроде соединения в базе данных), вы можете использовать этот метод:

import numpy
def join_2d(a, b):
    assert a.dtype == b.dtype
    a_part = numpy.tile(a, (len(b), 1))
    b_part = numpy.repeat(b, len(a), axis=0)
    return numpy.hstack((a_part, b_part))

быстрее всего вы можете получить либо путем объединения выражения генератора с функцией map:

import numpy
import datetime
a = np.arange(1000)
b = np.arange(200)

start = datetime.datetime.now()

foo = (item for sublist in [list(map(lambda x: (x,i),a)) for i in b] for item in sublist)

print (list(foo))

print ('execution time: {} s'.format((datetime.datetime.now() - start).total_seconds()))

выходы (на самом деле весь результирующий список печатается):

[(0, 0), (1, 0), ...,(998, 199), (999, 199)]
execution time: 1.253567 s

или с помощью двойного выражения генератор:

a = np.arange(1000)
b = np.arange(200)

start = datetime.datetime.now()

foo = ((x,y) for x in a for y in b)

print (list(foo))

print ('execution time: {} s'.format((datetime.datetime.now() - start).total_seconds()))

выходы (весь напечатанный список):

[(0, 0), (1, 0), ...,(998, 199), (999, 199)]
execution time: 1.187415 s

учтите, что большая часть времени вычислений уходит на команду печати. Расчеты генератора в остальном достаточно эффективны. Без печать время расчета:

execution time: 0.079208 s

для выражения генератора + функция карты и:

execution time: 0.007093 s

для выражения двойного генератора.

если то, что вы на самом деле хотите, это вычислить фактическое произведение каждой из пар координат, самое быстрое-решить его как матричный продукт numpy:

a = np.arange(1000)
b = np.arange(200)

start = datetime.datetime.now()

foo = np.dot(np.asmatrix([[i,0] for i in a]), np.asmatrix([[i,0] for i in b]).T)

print (foo)

print ('execution time: {} s'.format((datetime.datetime.now() - start).total_seconds()))

выходы:

 [[     0      0      0 ...,      0      0      0]
 [     0      1      2 ...,    197    198    199]
 [     0      2      4 ...,    394    396    398]
 ..., 
 [     0    997   1994 ..., 196409 197406 198403]
 [     0    998   1996 ..., 196606 197604 198602]
 [     0    999   1998 ..., 196803 197802 198801]]
execution time: 0.003869 s

и без печати (в этом случае оно не спасти много так как только крошечный кусочек матрицы фактически распечатывается):

execution time: 0.003083 s

Это также можно легко сделать с помощью itertools.метод продукта

from itertools import product
import numpy as np

x = np.array([1, 2, 3])
y = np.array([4, 5])
cart_prod = np.array(list(product(*[[x], [y]])),dtype='int32')

результат: массив([
[1, 4],
[1, 5],
[2, 4],
[2, 5],
[3, 4],
[3, 5]], dtype=int32)

время выполнения: 0.000155 s