Prodotto cartesiano agnostico (generico) dimensionalità

Question

Sto cercando di generare il prodotto cartesiano di un numero relativamente grande di array per coprire una griglia ad alta dimensione. A causa dell'elevata dimensionalità, non sarà possibile memorizzare in memoria il risultato del calcolo del prodotto cartesiano; piuttosto sarà scritto sul disco rigido. A causa di questo vincolo, ho bisogno di accedere ai risultati intermedi mentre vengono generati. Quello che ho fatto fino ad ora è questo:

for x in xrange(0, 10): 
    for y in xrange(0, 10): 
     for z in xrange(0, 10): 
      writeToHdd(x,y,z) 

che, oltre ad essere molto brutto, non è scalabile (vale a dire che sarebbe bisogno di me la scrittura come molti loop come dimensioni). Ho provato a utilizzare la soluzione proposta here, ma questa è una soluzione ricorsiva, che rende quindi piuttosto difficile ottenere i risultati al volo mentre vengono generati. C'è un modo "pulito" per fare questo oltre ad avere un ciclo hardcoded per dimensione?

Answer 1

In semplice Python, è possibile generare il prodotto cartesiano di una raccolta di iterables utilizzando itertools.product.

>>> arrays = range(0, 2), range(4, 6), range(8, 10) 
>>> list(itertools.product(*arrays)) 
[(0, 4, 8), (0, 4, 9), (0, 5, 8), (0, 5, 9), (1, 4, 8), (1, 4, 9), (1, 5, 8), (1, 5, 9)] 

In Numpy, è possibile combinare numpy.meshgrid (passando sparse=True per evitare l'espansione del prodotto in memoria) con numpy.ndindex:

>>> arrays = np.arange(0, 2), np.arange(4, 6), np.arange(8, 10) 
>>> grid = np.meshgrid(*arrays, sparse=True) 
>>> [tuple(g[i] for g in grid) for i in np.ndindex(grid[0].shape)] 
[(0, 4, 8), (0, 4, 9), (1, 4, 8), (1, 4, 9), (0, 5, 8), (0, 5, 9), (1, 5, 8), (1, 5, 9)] 

Answer 2

Sembra che si desideri eseguire il ciclo su un numero arbitrario di dimensioni. La mia soluzione generica per questo sta usando un campo indice e incrementa gli indici più la gestione degli overflow.

Esempio:

n = 3 # number of dimensions 
N = 1 # highest index value per dimension 

idx = [0]*n 
while True: 
    print(idx) 
    # increase first dimension 
    idx[0] += 1 
    # handle overflows 
    for i in range(0, n-1): 
     if idx[i] > N: 
      # reset this dimension and increase next higher dimension 
      idx[i] = 0 
      idx[i+1] += 1 
    if idx[-1] > N: 
     # overflow in the last dimension, we are finished 
     break 

Dà:

[0, 0, 0] 
[1, 0, 0] 
[0, 1, 0] 
[1, 1, 0] 
[0, 0, 1] 
[1, 0, 1] 
[0, 1, 1] 
[1, 1, 1] 

Numpy ha qualcosa di simile integrato: ndenumerate.

Answer 3

Credo di aver capito un bel modo utilizzando un file mappato di memoria:

def carthesian_product_mmap(vectors, filename, mode='w+'): 
    ''' 
    Vectors should be a tuple of `numpy.ndarray` vectors. You could 
    also make it more flexible, and include some error checking 
    '''   
    # Make a meshgrid with `copy=False` to create views 
    grids = np.meshgrid(*vectors, copy=False, indexing='ij') 

    # The shape for concatenating the grids from meshgrid 
    shape = grid[0].shape + (len(vectors),) 

    # Find the "highest" dtype neccesary 
    dtype = np.result_type(*vectors) 

    # Instantiate the memory mapped file 
    M = np.memmap(filename, dtype, mode, shape=shape) 

    # Fill the memmap with the grids 
    for i, grid in enumerate(grids): 
     M[...,i] = grid 

    # Make sure the data is written to disk (optional?) 
    M.flush() 

    # Reshape to put it in the right format for Carthesian product 
    return M.reshape((-1, len(vectors))) 

Ma mi chiedo se è davvero necessario memorizzare l'intero prodotto cartesiano (c'è molta duplicazione dei dati). Non è un'opzione per generare le righe nel prodotto nel momento in cui sono necessarie?