Tableau Numpy incrémental de taille en Python

Question

Je viens de rencontrer le besoin d'un tableau Numpy incrémental en Python, et comme je n'ai rien trouvé, je l'ai implémenté. Je me demande simplement si ma voie est la meilleure ou si vous pouvez trouver d'autres idées. Donc, le problème est que j'ai un tableau 2D (le programme gère les tableaux nD) pour lequel la taille n'est pas connue à l'avance et la quantité variable de données doit être concaténée au tableau dans une direction (disons que Je dois appeler np.vstak beaucoup de fois). Chaque fois que je concatène des données, je dois prendre le tableau, le trier le long de l'axe 0 et faire d'autres choses, donc je ne peux pas construire une longue liste de tableaux, puis np.vstak la liste à la fois. Puisque l'allocation de mémoire est chère, je me suis tourné vers des tableaux incrémentaux, où j'incrémente la taille du tableau d'une quantité supérieure à la taille dont j'ai besoin (j'utilise des incréments de 50%), afin de minimiser le nombre d'allocations.

Je Codé Ce et vous pouvez le voir dans le code suivant:

class ExpandingArray: 

    __DEFAULT_ALLOC_INIT_DIM = 10 # default initial dimension for all the axis is nothing is given by the user 
    __DEFAULT_MAX_INCREMENT = 10 # default value in order to limit the increment of memory allocation 

    __MAX_INCREMENT = [] # Max increment 
    __ALLOC_DIMS = []  # Dimensions of the allocated np.array 
    __DIMS = []    # Dimensions of the view with data on the allocated np.array (__DIMS <= __ALLOC_DIMS) 

    __ARRAY = []   # Allocated array 

    def __init__(self,initData,allocInitDim=None,dtype=np.float64,maxIncrement=None): 
     self.__DIMS = np.array(initData.shape) 

     self.__MAX_INCREMENT = maxIncrement 
     if self.__MAX_INCREMENT == None: 
      self.__MAX_INCREMENT = self.__DEFAULT_MAX_INCREMENT 

     # Compute the allocation dimensions based on user's input 
     if allocInitDim == None: 
      allocInitDim = self.__DIMS.copy() 

     while np.any(allocInitDim < self.__DIMS ) or np.any(allocInitDim == 0): 
      for i in range(len(self.__DIMS)): 
       if allocInitDim[i] == 0: 
        allocInitDim[i] = self.__DEFAULT_ALLOC_INIT_DIM 
       if allocInitDim[i] < self.__DIMS[i]: 
        allocInitDim[i] += min(allocInitDim[i]/2, self.__MAX_INCREMENT) 

     # Allocate memory 
     self.__ALLOC_DIMS = allocInitDim 
     self.__ARRAY = np.zeros(self.__ALLOC_DIMS,dtype=dtype) 

     # Set initData 
     sliceIdxs = [slice(self.__DIMS[i]) for i in range(len(self.__DIMS))] 
     self.__ARRAY[sliceIdxs] = initData 

    def shape(self): 
     return tuple(self.__DIMS) 

    def getAllocArray(self): 
     return self.__ARRAY 

    def getDataArray(self): 
     """ 
     Get the view of the array with data 
     """ 
     sliceIdxs = [slice(self.__DIMS[i]) for i in range(len(self.__DIMS))] 
     return self.__ARRAY[sliceIdxs] 

    def concatenate(self,X,axis=0): 
     if axis > len(self.__DIMS): 
      print "Error: axis number exceed the number of dimensions" 
      return 

     # Check dimensions for remaining axis 
     for i in range(len(self.__DIMS)): 
      if i != axis: 
       if X.shape[i] != self.shape()[i]: 
        print "Error: Dimensions of the input array are not consistent in the axis %d" % i 
        return 

     # Check whether allocated memory is enough 
     needAlloc = False 
     while self.__ALLOC_DIMS[axis] < self.__DIMS[axis] + X.shape[axis]: 
      needAlloc = True 
      # Increase the __ALLOC_DIMS 
      self.__ALLOC_DIMS[axis] += min(self.__ALLOC_DIMS[axis]/2,self.__MAX_INCREMENT) 

     # Reallocate memory and copy old data 
     if needAlloc: 
      # Allocate 
      newArray = np.zeros(self.__ALLOC_DIMS) 
      # Copy 
      sliceIdxs = [slice(self.__DIMS[i]) for i in range(len(self.__DIMS))] 
      newArray[sliceIdxs] = self.__ARRAY[sliceIdxs] 
      self.__ARRAY = newArray 

     # Concatenate new data 
     sliceIdxs = [] 
     for i in range(len(self.__DIMS)): 
      if i != axis: 
       sliceIdxs.append(slice(self.__DIMS[i])) 
      else: 
       sliceIdxs.append(slice(self.__DIMS[i],self.__DIMS[i]+X.shape[i])) 

     self.__ARRAY[sliceIdxs] = X 
     self.__DIMS[axis] += X.shape[axis] 

Le code montre des performances bien meilleures que vstack/hstack plusieurs concaténations de taille au hasard. Ce que je me demande est: est-ce le meilleur moyen? Y at-il quelque chose qui le fait déjà en numpy? En outre, il serait intéressant de pouvoir surcharger l'opérateur d'affectation de tranches de np.array, de sorte que dès que l'utilisateur affecte quelque chose en dehors des dimensions réelles, un objet ExpandingArray.concatenate() est exécuté. Comment faire une telle surcharge?

Test du code: Je poste ici aussi du code que j'ai utilisé pour faire une comparaison entre vstack et ma méthode. J'additionne morceau aléatoire de données de longueur maximale 100.

import time 

N = 10000 

def performEA(N): 
    EA = ExpandingArray(np.zeros((0,2)),maxIncrement=1000) 
    for i in range(N): 
     nNew = np.random.random_integers(low=1,high=100,size=1) 
     X = np.random.rand(nNew,2) 
     EA.concatenate(X,axis=0) 
     # Perform operations on EA.getDataArray() 
    return EA 

def performVStack(N): 
    A = np.zeros((0,2)) 
    for i in range(N): 
     nNew = np.random.random_integers(low=1,high=100,size=1) 
     X = np.random.rand(nNew,2) 
     A = np.vstack((A,X)) 
     # Perform operations on A 
    return A 

start_EA = time.clock() 
EA = performEA(N) 
stop_EA = time.clock() 

start_VS = time.clock() 
VS = performVStack(N) 
stop_VS = time.clock() 

print "Elapsed Time EA: %.2f" % (stop_EA-start_EA) 
print "Elapsed Time VS: %.2f" % (stop_VS-start_VS) 

Answer 1

Je pense que le modèle de conception la plus courante pour ces choses est d'utiliser simplement une liste pour les petits tableaux. Bien sûr, vous pourriez faire des choses comme le redimensionnement dynamique (si vous voulez faire des choses folles, vous pouvez essayer d'utiliser la méthode resize array aussi). Je pense qu'une méthode typique consiste à toujours doubler la taille, quand on ne sait vraiment pas quelle sera la taille des choses. Bien sûr, si vous savez à quel point le tableau va grossir, il suffit simplement d'allouer la totalité à l'avant.

def performVStack_fromlist(N): 
    l = [] 
    for i in range(N): 
     nNew = np.random.random_integers(low=1,high=100,size=1) 
     X = np.random.rand(nNew,2) 
     l.append(X) 
    return np.vstack(l) 

Je suis sûr qu'il ya des cas d'utilisation où une gamme élargie pourrait être utile (par exemple lorsque les tableaux sont très-jointes petit), mais cette boucle semble mieux manié avec le modèle ci-dessus. L'optimisation concerne principalement la fréquence à laquelle vous devez tout copier, et faire une liste comme celle-ci (autre que la liste elle-même) c'est exactement une fois ici. Donc, c'est beaucoup plus rapide normalement.

Answer 2

Lorsque j'ai fait face à un problème similaire, j'ai utilisé ndarray.resize() (http://docs.scipy.org/doc/numpy/reference/generated/numpy.ndarray.resize.html#numpy.ndarray.resize). La plupart du temps, cela évitera la réaffectation + la copie. Je ne peux pas garantir qu'il se révélera plus rapide (il le ferait probablement), mais c'est tellement plus simple. Pour ce qui est de votre deuxième question, je pense que l'attribution d'une section prioritaire à des fins d'extension n'est pas une bonne idée. Cet opérateur est destiné à être affecté à des éléments/tranches existants. Si vous voulez changer cela, ce n'est pas immédiatement clair comment vous voulez qu'il se comporter dans certains cas, par exemple .:

a = MyExtendableArray(np.arange(100)) 
a[200] = 6 # resize to 200? pad [100:200] with what? 
a[90:110] = 7 # assign to existing items AND automagically-allocated items? 
a[::-1][200] = 6 # ... 

Ma suggestion est que tranche l'affectation et appending données doivent rester séparées.