Produk Cartesian dari titik array x dan y menjadi satu array titik 2D

Saya memiliki dua array numpy yang menentukan sumbu x dan y dari grid. Sebagai contoh:

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

Saya ingin menghasilkan produk Cartesian dari array ini untuk menghasilkan:

array([[1,4],[2,4],[3,4],[1,5],[2,5],[3,5]])

Dengan cara yang tidak terlalu tidak efisien karena saya perlu melakukan ini berkali-kali dalam satu lingkaran. Saya berasumsi bahwa mengonversi mereka ke daftar Python dan menggunakan itertools.productdan kembali ke array numpy bukan bentuk yang paling efisien.

>>> numpy.transpose([numpy.tile(x, len(y)), numpy.repeat(y, len(x))])
array([[1, 4],
       [2, 4],
       [3, 4],
       [1, 5],
       [2, 5],
       [3, 5]])

Lihat Menggunakan numpy untuk membangun array dari semua kombinasi dari dua array untuk solusi umum untuk menghitung produk Cartesian dari array N.

Kanonik cartesian_product (hampir)

Ada banyak pendekatan untuk masalah ini dengan properti yang berbeda. Beberapa lebih cepat dari yang lain, dan beberapa lebih untuk tujuan umum. Setelah banyak pengujian dan penyesuaian, saya menemukan bahwa fungsi berikut, yang menghitung dimensi-n cartesian_product, lebih cepat daripada kebanyakan yang lain untuk banyak input. Untuk sepasang pendekatan yang sedikit lebih kompleks, tetapi bahkan sedikit lebih cepat dalam banyak kasus, lihat jawabannya oleh Paul Panzer .

Mengingat jawaban itu, ini bukan lagi implementasi tercepat dari produk cartesian numpyyang saya sadari. Namun, saya pikir kesederhanaannya akan terus menjadikannya tolok ukur yang berguna untuk peningkatan di masa depan:

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)

Perlu disebutkan bahwa fungsi ini digunakan ix_dengan cara yang tidak biasa; sedangkan penggunaan terdokumentasi ix_adalah untuk menghasilkan indeks ke dalam array, kebetulan bahwa array dengan bentuk yang sama dapat digunakan untuk penugasan yang disiarkan. Terima kasih banyak kepada mgilson , yang mengilhami saya untuk mencoba menggunakan ix_cara ini, dan kepada unutbu , yang memberikan umpan balik yang sangat membantu pada jawaban ini, termasuk saran untuk menggunakannumpy.result_type .

Alternatif penting

Terkadang lebih cepat untuk menulis blok memori yang berdekatan dalam urutan Fortran. Itulah dasar dari alternatif ini cartesian_product_transpose,, yang telah terbukti lebih cepat pada beberapa perangkat keras daripada cartesian_product(lihat di bawah). Namun, jawaban Paul Panzer, yang menggunakan prinsip yang sama, bahkan lebih cepat. Namun, saya memasukkan ini di sini untuk pembaca yang tertarik:

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

Setelah memahami pendekatan Panzer, saya menulis versi baru yang hampir secepat miliknya, dan hampir sesederhana 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

Ini tampaknya memiliki beberapa overhead waktu konstan yang membuatnya berjalan lebih lambat daripada Panzer untuk input kecil. Tetapi untuk input yang lebih besar, dalam semua tes yang saya jalankan, performanya sama baiknya dengan implementasi tercepatnya (cartesian_product_transpose_pp ).

Di bagian berikut, saya menyertakan beberapa tes alternatif lain. Ini sekarang agak ketinggalan zaman, tetapi daripada upaya duplikat, saya telah memutuskan untuk meninggalkan mereka di sini karena kepentingan sejarah. Untuk tes terbaru, lihat jawaban Panzer, serta Nico Schlömer .

Tes terhadap alternatif

Berikut ini adalah serangkaian tes yang menunjukkan peningkatan kinerja yang disediakan beberapa fungsi ini relatif terhadap sejumlah alternatif. Semua tes yang ditunjukkan di sini dilakukan pada mesin quad-core, menjalankan Mac OS 10.12.5, Python 3.6.1, dannumpy 1.12.1. Variasi pada perangkat keras dan lunak diketahui menghasilkan hasil yang berbeda, demikian YMMV. Jalankan tes ini untuk diri Anda sendiri untuk memastikan!

Definisi:

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

Hasil tes:

In [2]: test_all(*(x100 * 2))
repeat_product:
67.5 µs ± 633 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)
dstack_product:
67.7 µs ± 1.09 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)
cartesian_product:
33.4 µs ± 558 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)
cartesian_product_transpose:
67.7 µs ± 932 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)
cartesian_product_recursive:
215 µs ± 6.01 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
cartesian_product_itertools:
3.65 ms ± 38.7 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

In [3]: test_all(*(x500 * 2))
repeat_product:
1.31 ms ± 9.28 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
dstack_product:
1.27 ms ± 7.5 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
cartesian_product:
375 µs ± 4.5 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
cartesian_product_transpose:
488 µs ± 8.88 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
cartesian_product_recursive:
2.21 ms ± 38.4 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
cartesian_product_itertools:
105 ms ± 1.17 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)

In [4]: test_all(*(x1000 * 2))
repeat_product:
10.2 ms ± 132 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
dstack_product:
12 ms ± 120 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
cartesian_product:
4.75 ms ± 57.1 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
cartesian_product_transpose:
7.76 ms ± 52.7 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
cartesian_product_recursive:
13 ms ± 209 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
cartesian_product_itertools:
422 ms ± 7.77 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

Dalam semua kasus, cartesian_product sebagaimana didefinisikan pada awal jawaban ini adalah yang tercepat.

Untuk fungsi-fungsi yang menerima jumlah array input yang sewenang-wenang, ada baiknya memeriksa kinerja len(arrays) > 2juga. (Sampai saya dapat menentukan mengapa cartesian_product_recursivemelempar kesalahan dalam kasus ini, saya telah menghapusnya dari tes ini.)

In [5]: test_cartesian(*(x100 * 3))
cartesian_product:
8.8 ms ± 138 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
cartesian_product_transpose:
7.87 ms ± 91.5 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
cartesian_product_itertools:
518 ms ± 5.5 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

In [6]: test_cartesian(*(x50 * 4))
cartesian_product:
169 ms ± 5.1 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)
cartesian_product_transpose:
184 ms ± 4.32 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)
cartesian_product_itertools:
3.69 s ± 73.5 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

In [7]: test_cartesian(*(x10 * 6))
cartesian_product:
26.5 ms ± 449 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)
cartesian_product_transpose:
16 ms ± 133 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
cartesian_product_itertools:
728 ms ± 16 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

In [8]: test_cartesian(*(x10 * 7))
cartesian_product:
650 ms ± 8.14 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
cartesian_product_transpose:
518 ms ± 7.09 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
cartesian_product_itertools:
8.13 s ± 122 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

Seperti yang ditunjukkan oleh tes ini, cartesian_producttetap kompetitif hingga jumlah array input naik di atas (kira-kira) empat. Setelah itu, cartesian_product_transposememang ada sedikit keunggulan.

Perlu ditegaskan kembali bahwa pengguna dengan perangkat keras dan sistem operasi lain mungkin melihat hasil yang berbeda. Misalnya, unutbu melaporkan melihat hasil berikut untuk pengujian ini menggunakan Ubuntu 14.04, Python 3.4.3, dan numpy1.14.0.dev0 + b7050a9:

>>> %timeit cartesian_product_transpose(x500, y500) 
1000 loops, best of 3: 682 µs per loop
>>> %timeit cartesian_product(x500, y500)
1000 loops, best of 3: 1.55 ms per loop

Di bawah ini, saya masuk ke beberapa detail tentang tes sebelumnya yang saya jalankan di sepanjang garis ini. Kinerja relatif dari pendekatan ini telah berubah dari waktu ke waktu, untuk berbagai perangkat keras dan versi Python dan numpy. Meskipun tidak segera bermanfaat bagi orang yang menggunakan versi terbarunumpy , ini menggambarkan bagaimana banyak hal telah berubah sejak versi pertama dari jawaban ini.

Alternatif sederhana: meshgrid+dstack

Jawaban yang saat ini diterima menggunakan tiledan repeatuntuk menyiarkan dua array bersama-sama. Tetapi meshgridfungsinya praktis melakukan hal yang sama. Inilah output dari tiledan repeatsebelum diteruskan ke transpose:

In [1]: import numpy
In [2]: x = numpy.array([1,2,3])
   ...: y = numpy.array([4,5])
   ...: 

In [3]: [numpy.tile(x, len(y)), numpy.repeat(y, len(x))]
Out[3]: [array([1, 2, 3, 1, 2, 3]), array([4, 4, 4, 5, 5, 5])]

Dan inilah output dari meshgrid:

In [4]: numpy.meshgrid(x, y)
Out[4]: 
[array([[1, 2, 3],
        [1, 2, 3]]), array([[4, 4, 4],
        [5, 5, 5]])]

Seperti yang Anda lihat, ini hampir identik. Kita hanya perlu membentuk ulang hasilnya untuk mendapatkan hasil yang persis sama.

In [5]: xt, xr = numpy.meshgrid(x, y)
   ...: [xt.ravel(), xr.ravel()]
Out[5]: [array([1, 2, 3, 1, 2, 3]), array([4, 4, 4, 5, 5, 5])]

Namun, alih-alih membentuk kembali pada titik ini, kita dapat meneruskan output dari meshgridke dstackdan membentuk kembali setelahnya, yang menghemat beberapa pekerjaan:

In [6]: numpy.dstack(numpy.meshgrid(x, y)).reshape(-1, 2)
Out[6]: 
array([[1, 4],
       [2, 4],
       [3, 4],
       [1, 5],
       [2, 5],
       [3, 5]])

Bertentangan dengan klaim dalam komentar ini , saya tidak melihat bukti bahwa input yang berbeda akan menghasilkan output yang berbeda bentuk, dan seperti ditunjukkan di atas, mereka melakukan hal yang sangat mirip, sehingga akan sangat aneh jika mereka melakukannya. Harap beri tahu saya jika Anda menemukan contoh tandingan.

Menguji meshgrid+ dstackvs. repeat+transpose

Kinerja relatif dari kedua pendekatan ini telah berubah seiring waktu. Dalam versi Python sebelumnya (2.7), hasil menggunakan meshgrid+ dstackterasa lebih cepat untuk input kecil. (Perhatikan bahwa tes ini berasal dari versi lama dari jawaban ini.) Definisi:

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

Untuk input berukuran sedang, saya melihat peningkatan yang signifikan. Tapi saya mencoba kembali tes ini dengan versi Python (3.6.1) dan numpy(1.12.1) yang lebih baru, pada mesin yang lebih baru. Kedua pendekatan itu hampir identik sekarang.

Tes Lama

>>> x, y = numpy.arange(500), numpy.arange(500)
>>> %timeit repeat_product(x, y)
10 loops, best of 3: 62 ms per loop
>>> %timeit dstack_product(x, y)
100 loops, best of 3: 12.2 ms per loop

Tes Baru

In [7]: x, y = numpy.arange(500), numpy.arange(500)
In [8]: %timeit repeat_product(x, y)
1.32 ms ± 24.7 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
In [9]: %timeit dstack_product(x, y)
1.26 ms ± 8.47 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

Seperti biasa, YMMV, tetapi ini menunjukkan bahwa dalam versi terbaru Python dan numpy, ini dapat dipertukarkan.

Fungsi produk umum

Secara umum, kita mungkin berharap bahwa menggunakan fungsi bawaan akan lebih cepat untuk input kecil, sedangkan untuk input besar, fungsi yang dibangun khusus mungkin lebih cepat. Selanjutnya untuk produk n-dimensi umum, tiledanrepeat tidak akan membantu, karena mereka tidak memiliki analog dimensi yang lebih tinggi. Jadi ada baiknya menyelidiki perilaku fungsi yang dibangun juga.

Sebagian besar tes yang relevan muncul di awal jawaban ini, tetapi di sini ada beberapa tes yang dilakukan pada versi Python sebelumnya dan numpyuntuk perbandingan.

The cartesianfungsi yang didefinisikan dalam jawaban lain digunakan untuk melakukan cukup baik untuk input yang lebih besar. (Ini sama dengan fungsi yang disebut cartesian_product_recursivedi atas.) Dalam rangka untuk membandingkan cartesianuntuk dstack_prodct, kita menggunakan hanya dua dimensi.

Di sini sekali lagi, tes lama menunjukkan perbedaan yang signifikan, sedangkan tes baru menunjukkan hampir tidak ada.

Tes Lama

>>> x, y = numpy.arange(1000), numpy.arange(1000)
>>> %timeit cartesian([x, y])
10 loops, best of 3: 25.4 ms per loop
>>> %timeit dstack_product(x, y)
10 loops, best of 3: 66.6 ms per loop

Tes Baru

In [10]: x, y = numpy.arange(1000), numpy.arange(1000)
In [11]: %timeit cartesian([x, y])
12.1 ms ± 199 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
In [12]: %timeit dstack_product(x, y)
12.7 ms ± 334 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

Seperti sebelumnya, dstack_productmasih berdetak cartesianpada skala yang lebih kecil.

Tes Baru ( tes lama yang berlebihan tidak ditampilkan )

In [13]: x, y = numpy.arange(100), numpy.arange(100)
In [14]: %timeit cartesian([x, y])
215 µs ± 4.75 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
In [15]: %timeit dstack_product(x, y)
65.7 µs ± 1.15 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)

Menurut saya, perbedaan-perbedaan ini menarik dan layak dicatat; tetapi pada akhirnya mereka akademis. Seperti yang ditunjukkan oleh tes pada awal jawaban ini, semua versi ini hampir selalu lebih lambat dari yang cartesian_productdidefinisikan pada awal jawaban ini - yang sedikit lebih lambat daripada implementasi tercepat di antara jawaban untuk pertanyaan ini.

Anda bisa melakukan pemahaman daftar normal dengan python

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

yang seharusnya memberi Anda

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

Saya juga tertarik dengan ini dan melakukan sedikit perbandingan kinerja, mungkin agak lebih jelas daripada di jawaban @ senderle.

Untuk dua array (kasus klasik):

Untuk empat array:

(Perhatikan bahwa panjang array hanya beberapa lusin entri di sini.)

Kode untuk mereproduksi plot:

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: 2 * (numpy.arange(n, dtype=float),),
    n_range=[2 ** k for k in range(13)],
    # 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,
)

Membangun di atas tanah contoh kerja @ senderle saya telah datang dengan dua versi - satu untuk C dan satu untuk tata letak Fortran - yang seringkali sedikit lebih cepat.

• cartesian_product_transpose_ppadalah - tidak seperti @ senderle cartesian_product_transposeyang menggunakan strategi yang berbeda sama sekali - versi cartesion_productyang menggunakan tata letak memori transpose yang lebih menguntungkan + beberapa optimasi yang sangat kecil.
• cartesian_product_pptetap dengan tata letak memori asli. Apa yang membuatnya cepat adalah penggunaan salin yang berdekatan. Salinan yang berdekatan ternyata jauh lebih cepat sehingga menyalin blok memori penuh meskipun hanya sebagian yang berisi data yang valid lebih baik daripada hanya menyalin bit yang valid.

Beberapa perflot. Saya membuat yang terpisah untuk tata letak C dan Fortran, karena ini adalah tugas yang berbeda IMO.

Nama yang berakhiran 'pp' adalah pendekatan saya.

1) banyak faktor kecil (masing-masing 2 elemen)

2) banyak faktor kecil (masing-masing 4 elemen)

3) tiga faktor dengan panjang yang sama

4) dua faktor dengan panjang yang sama

Kode (perlu melakukan run terpisah untuk setiap plot b / c Saya tidak tahu cara mengatur ulang; juga perlu mengedit / berkomentar masuk / keluar dengan tepat):

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
    )

Pada Oktober 2017, numpy sekarang memiliki np.stackfungsi generik yang mengambil parameter sumbu. Dengan menggunakannya, kita dapat memiliki "produk cartesian umum" menggunakan teknik "dstack and meshgrid:

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

Perhatikan pada axis=-1parameter. Ini adalah sumbu (paling dalam) terakhir dalam hasilnya. Ini setara dengan menggunakan axis=ndim.

Satu komentar lain, karena produk Cartesian meledak sangat cepat, kecuali kita perlu menyadari susunan dalam memori untuk beberapa alasan, jika produk tersebut sangat besar, kita mungkin ingin menggunakan itertoolsdan menggunakan nilai-nilai on-the-fly.

Saya menggunakan jawaban @kennytm untuk sementara waktu, tetapi ketika mencoba melakukan hal yang sama di TensorFlow, tetapi saya menemukan bahwa TensorFlow tidak ada bandingannya dengannumpy.repeat() . Setelah sedikit percobaan, saya pikir saya menemukan solusi yang lebih umum untuk vektor titik sembarang.

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

dan untuk TensorFlow:

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)

Paket Scikit-learn memiliki implementasi cepat untuk hal ini:

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

Perhatikan bahwa konvensi implementasi ini berbeda dari yang Anda inginkan, jika Anda peduli dengan urutan output. Untuk pemesanan yang tepat, Anda bisa melakukannya

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

Secara lebih umum, jika Anda memiliki dua array numpy 2d dan a, dan Anda ingin menggabungkan setiap baris dari a ke setiap baris dari b (Produk cartesian dari baris, seperti gabungan dalam database), Anda dapat menggunakan metode ini :

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

Cara tercepat yang bisa Anda dapatkan adalah dengan menggabungkan ekspresi generator dengan fungsi peta:

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

Keluaran (sebenarnya seluruh daftar yang dihasilkan dicetak):

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

atau dengan menggunakan ekspresi generator ganda:

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

Output (seluruh daftar dicetak):

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

Perhatikan bahwa sebagian besar waktu perhitungan digunakan untuk perintah pencetakan. Perhitungan generator dinyatakan cukup efisien. Tanpa mencetak waktu perhitungan adalah:

execution time: 0.079208 s

untuk ekspresi generator + fungsi peta dan:

execution time: 0.007093 s

untuk ekspresi generator ganda.

Jika yang Anda inginkan adalah menghitung produk aktual dari masing-masing pasangan koordinat, yang tercepat adalah menyelesaikannya sebagai produk matriks 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()))

Output:

 [[     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

dan tanpa mencetak (dalam hal ini tidak menghemat banyak karena hanya sebagian kecil dari matriks yang benar-benar dicetak):

execution time: 0.003083 s

Ini juga dapat dengan mudah dilakukan dengan menggunakan metode itertools.product

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

Hasil: array ([
[1, 4],
[1, 5],
[2, 4],
[2, 5],
[3, 4],
[3, 5]], dtype = int32)

Waktu eksekusi: 0,000155 s

Dalam kasus khusus yang Anda perlukan untuk melakukan operasi sederhana seperti penambahan pada setiap pasangan, Anda dapat memperkenalkan dimensi ekstra dan membiarkan penyiaran melakukan pekerjaan:

>>> a, b = np.array([1,2,3]), np.array([10,20,30])
>>> a[None,:] + b[:,None]
array([[11, 12, 13],
       [21, 22, 23],
       [31, 32, 33]])

Saya tidak yakin apakah ada cara serupa untuk benar-benar mendapatkan pasangan itu sendiri.