Dimensionalität agnostisch (generisch) kartesisches Produkt

Question

Ich möchte das kartesische Produkt einer relativ großen Anzahl von Arrays erzeugen, um ein hochdimensionales Gitter zu überspannen. Aufgrund der hohen Dimensionalität wird es nicht möglich sein, das Ergebnis der kartesischen Produktberechnung im Speicher zu speichern; Stattdessen wird es auf die Festplatte geschrieben. Aufgrund dieser Einschränkung muss ich auf die Zwischenergebnisse zugreifen, wenn sie generiert werden. Was ich bisher zu tun, ist dies:

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

, die, abgesehen von sehr böse sein, nicht skalierbar ist (das heißt würde es erfordert ich so viele Schleifen als Dimensionen zu schreiben). Ich habe versucht, die vorgeschlagene Lösung here zu verwenden, aber das ist eine rekursive Lösung, die es daher ziemlich schwierig macht, die Ergebnisse während der Generierung zu erhalten. Gibt es einen "sauberen" Weg, dies zu tun, als eine hardcodierte Schleife pro Dimension zu haben?

Answer 1

Im einfachen Python können Sie das kartesische Produkt einer Sammlung von Iterablen mit itertools.product generieren.

>>> 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 können Sie kombinieren numpy.meshgrid (sparse=True Passieren des Produkts im Speicher zu vermeiden Erweiterung) mit 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

Es scheint, Sie wollen nur eine beliebige Anzahl von Dimensionen durchlaufen. Meine generische Lösung hierfür ist die Verwendung eines Indexfelds und Inkrementindizes plus Handling-Overflows.

Beispiel:

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 

Gibt:

[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 etwas ähnliches eingebaute hat: ndenumerate.

Answer 3

Ich denke, dass ich ein guter Weg, einen Memory-Mapped-Datei herausgefunden:

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

Aber ich frage mich, ob Sie wirklich das gesamte Produkt von Carthesian speichern müssen (es gibt eine Menge von Datenduplikation). Ist es nicht eine Option, die Zeilen im Produkt zu dem Zeitpunkt zu generieren, in dem sie benötigt werden?