Le moyen le plus rapide de faire croître un tableau numérique numpy

Question

Exigences :

• Je dois faire croître un tableau de manière arbitraire à partir de données.
• Je peux estimer la taille (environ 100-200) sans garantie que le tableau s'adapte à chaque fois.
• Une fois qu'il a atteint sa taille finale, je dois effectuer des calculs numériques dessus, donc je préférerais finalement obtenir un tableau numpy 2D.
• La vitesse est critique. Par exemple, pour l'un des 300 fichiers, la méthode update() est appelée 45 millions de fois (prend environ 150s) et la méthode finalize() est appelée 500 000 fois (prend un total de 106s)... pour un total d'environ 250s.

Voici mon code :

def __init__(self):
    self.data = []

def update(self, row):
    self.data.append(row)

def finalize(self):
    dx = np.array(self.data)

D'autres choses que j'ai essayées incluent le code suivant... mais c'est beaaaucoup plus lent.

def classe A :
    def __init__(self):
        self.data = np.array([])

    def update(self, row):
        np.append(self.data, row)

    def finalize(self):
        dx = np.reshape(self.data, shape=(self.data.shape[0]/5, 5))

Voici un schéma de comment cela est appelé :

for i in range(500000):
    ax = A()
    for j in range(200):
         ax.update([1,2,3,4,5])
    ax.finalize()
    # du traitement sur ax

Answer 1

J'ai essayé quelques options différentes, en travaillant sur la synchronisation.

import numpy as np

1. La méthode que vous mentionnez comme étant lente : (32.094 secondes)

   class A:
   
       def __init__(self):
           self.data = np.array([])
   
       def update(self, row):
           self.data = np.append(self.data, row)
   
       def finalize(self):
           return np.reshape(self.data, newshape=(self.data.shape[0]/5, 5))

2. Liste Python régulière : (0.308 secondes)

   class B:
   
       def __init__(self):
           self.data = []
   
       def update(self, row):
           for r in row:
               self.data.append(r)
   
       def finalize(self):
           return np.reshape(self.data, newshape=(len(self.data)/5, 5))

3. Essayer d'implémenter une arraylist en numpy : (0.362 secondes)

   class C:
   
       def __init__(self):
           self.data = np.zeros((100,))
           self.capacity = 100
           self.size = 0
   
       def update(self, row):
           for r in row:
               self.add(r)
   
       def add(self, x):
           if self.size == self.capacity:
               self.capacity *= 4
               newdata = np.zeros((self.capacity,))
               newdata[:self.size] = self.data
               self.data = newdata
   
           self.data[self.size] = x
           self.size += 1
   
       def finalize(self):
           data = self.data[:self.size]
           return np.reshape(data, newshape=(len(data)/5, 5))

Et voilà comment j'ai mesuré le temps :

x = C()
for i in xrange(100000):
    x.update([i])

Il semble donc que les listes Python régulières fonctionnent assez bien ;)

Answer 2

Np.append() copie toutes les données dans le tableau à chaque fois, mais la liste augmente la capacité d'un facteur (1,125). La liste est rapide, mais l'utilisation de la mémoire est plus importante que le tableau. Vous pouvez utiliser le module array de la bibliothèque standard python si vous vous souciez de la mémoire.

Voici une discussion sur ce sujet:

Comment créer un tableau dynamique

Answer 3

En utilisant les déclarations de classe dans le post d'Owen, voici un timing révisé avec un effet de finalisation.

En bref, je trouve que la classe C fournit une implémentation qui est plus de 60 fois plus rapide que la méthode dans le post original. (désolé pour le mur de texte)

Le fichier que j'ai utilisé :

#!/usr/bin/python
import cProfile
import numpy as np

# ... déclarations de classe ici ...

def test_class(f):
    x = f()
    for i in xrange(100000):
        x.update([i])
    for i in xrange(1000):
        x.finalize()

for x in 'ABC':
    cProfile.run('test_class(%s)' % x)

Maintenant, les timings résultants :

A :

     903005 appels de fonction en 16,049 secondes

Classé par : nom standard

appels tottime percall cumtime percall fichier: ligne (fonction)
     1    0.000    0.000   16.049   16.049 :1()
100000    0.139    0.000    1.888    0.000 fromnumeric.py:1043(ravel)
  1000    0.001    0.000    0.003    0.000 fromnumeric.py:107(reshape)
100000    0.322    0.000   14.424    0.000 function_base.py:3466(append)
100000    0.102    0.000    1.623    0.000 numeric.py:216(asarray)
100000    0.121    0.000    0.298    0.000 numeric.py:286(asanyarray)
  1000    0.002    0.000    0.004    0.000 test.py:12(finalize)
     1    0.146    0.146   16.049   16.049 test.py:50(test_class)
     1    0.000    0.000    0.000    0.000 test.py:6(__init__)
100000    1.475    0.000   15.899    0.000 test.py:9(update)
     1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}
100000    0.126    0.000    0.126    0.000 {method 'ravel' of 'numpy.ndarray' objects}
  1000    0.002    0.000    0.002    0.000 {method 'reshape' of 'numpy.ndarray' objects}
200001    1.698    0.000    1.698    0.000 {numpy.core.multiarray.array}
100000   11.915    0.000   11.915    0.000 {numpy.core.multiarray.concatenate}

B :

     208004 appels de fonction en 16,885 secondes

Classé par : nom standard

appels tottime percall cumtime percall fichier: ligne (fonction)
     1    0.001    0.001   16,885   16,885 :1()
  1000    0.025    0.000   16,508    0,017 fromnumeric.py:107(reshape)
  1000    0.013    0.000   16,483    0,016 fromnumeric.py:32(_wrapit)
  1000    0.007    0.000   16,445    0,016 numeric.py:216(asarray)
     1    0.000    0.000    0.000    0.000 test.py:16(__init__)
100000    0.068    0.000    0.080    0.000 test.py:19(update)
  1000    0.012    0.000   16,520    0,017 test.py:23(finalize)
     1    0.284    0.284   16,883   16,883 test.py:50(test_class)
  1000    0.005    0.000    0.005    0.000 {getattr}
  1000    0.001    0.000    0.001    0.000 {len}
100000    0.012    0.000    0.012    0.000 {method 'append' of 'list' objects}
     1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}
  1000    0.020    0.000    0.020    0.000 {method 'reshape' of 'numpy.ndarray' objects}
  1000   16,438    0.016   16,438    0.016 {numpy.core.multiarray.array}

C :

     204010 appels de fonction en 0,244 secondes

Classé par : nom standard

appels tottime percall cumtime percall fichier: ligne (fonction)
     1    0.000    0.000    0,244    0,244 :1()
  1000    0,001    0,000    0,003    0,000 fromnumeric.py:107(reshape)
     1    0,000    0,000    0,000    0,000 test.py:27(__init__)
100000    0,082    0,000    0,170    0,000 test.py:32(update)
100000    0,087    0,000    0,088    0,000 test.py:36(add)
  1000    0,002    0,000    0,005    0,000 test.py:46(finalize)
     1    0,068    0,068    0,243    0,243 test.py:50(test_class)
  1000    0,000    0,000    0,000    0,000 {len}
     1    0,000    0,000    0,000    0,000 {method 'disable' of '_lsprof.Profiler' objects}
  1000    0,002    0,000    0,002    0,000 {method 'reshape' of 'numpy.ndarray' objects}
     6    0,001    0,000    0,001    0,000 {numpy.core.multiarray.zeros}

La classe A est détruite par les mises à jour, la classe B est détruite par les finalisations. La classe C est robuste face à l'un et l'autre.

Answer 4

Il existe une grande différence de performance dans la fonction que vous utilisez pour la finalisation. Considérez le code suivant:

N=100000
nruns=5

a=[]
for i in range(N):
    a.append(np.zeros(1000))

print "start"

b=[]
for i in range(nruns):
    s=time()
    c=np.vstack(a)
    b.append((time()-s))
print "Chronométrage version vstack ",np.mean(b)

b=[]
for i in range(nruns):
    s=time()
    c1=np.reshape(a,(N,1000))
    b.append((time()-s))

print "Chronométrage version reshape ",np.mean(b)

b=[]
for i in range(nruns):
    s=time()
    c2=np.concatenate(a,axis=0).reshape(-1,1000)
    b.append((time()-s))

print "Chronométrage version concatenate ",np.mean(b)

print c.shape,c2.shape
assert (c==c2).all()
assert (c==c1).all()

L'utilisation de la fonction concatenate semble être deux fois plus rapide que la première version et plus de 10 fois plus rapide que la deuxième version.

Chronométrage version vstack  1.5774928093
Chronométrage version reshape  9.67419199944
Chronométrage version concatenate  0.669512557983

Answer 5

Tableaux Numpy à Dimensions Multiples

Ajoutant aux réponses de Owen et Prashant Kumar, voici une version utilisant des tableaux numpy à dimensions multiples (alias shape) qui accélère le code pour les solutions numpy. Cela est particulièrement utile si vous avez besoin d'accéder (finaliser()) souvent aux données.

Version

Prashant Kumar

row_length=1

row_length=5

Classe A - np.append

2,873 s

2,776 s

0,682 s

Classe B - liste python

6,693 s

80,868 s

22,012 s

Classe C - arraylist

0,095 s

0,180 s

0,043 s

La colonne Prashant Kumar est son exemple exécuté sur ma machine pour donner une comparaison. Avec row_length=5 c'est l'exemple de la question initiale. L'augmentation spectaculaire dans la liste python provient de {méthode intégrée numpy.array}, ce qui signifie que numpy a besoin de beaucoup plus de temps pour convertir une liste à dimensions multiples de listes en un tableau par rapport à une liste 1D et le remodeler lorsque les deux ont le même nombre d'entrées, par exemple np.array([[1,2,3]*5]) vs. np.array([1]*15).reshape((-1,3)).

Et voici le code :

import cProfile
import numpy as np

class A:
    def __init__(self,shape=(0,), dtype=float):
        """Le premier élément de shape est ignoré, le reste définit la forme"""
        self.data = np.array([], dtype=dtype).reshape((0,*shape[1:]))

    def update(self, row):
        self.data = np.append(self.data, row)

    def finalize(self):
        return self.data

class B:
    def __init__(self, shape=(0,), dtype=float):
        """Le premier élément de shape est ignoré, le reste définit la forme"""
        self.shape = shape
        self.dtype = dtype 
        self.data = []

    def update(self, row):
        self.data.append(row)

    def finalize(self):
        return np.array(self.data, dtype=self.dtype).reshape((-1, *self.shape[1:]))

class C:
    def __init__(self, shape=(0,), dtype=float):
        """Le premier élément de shape est ignoré, le reste définit la forme"""
        self.shape = shape
        self.data = np.zeros((100,*shape[1:]),dtype=dtype)
        self.capacity = 100
        self.size = 0

    def update(self, x):
        if self.size == self.capacity:
            self.capacity *= 4
            newdata = np.zeros((self.capacity,*self.data.shape[1:]))
            newdata[:self.size] = self.data
            self.data = newdata

        self.data[self.size] = x
        self.size += 1

    def finalize(self):
        return self.data[:self.size]

def test_class(f):
    row_length = 5
    x = f(shape=(0,row_length))
    for i in range(int(100000/row_length)):
        x.update([i]*row_length)
    for i in range(1000):
        x.finalize()

for x in 'ABC':
    cProfile.run('test_class(%s)' % x)

Et une autre option à ajouter au post ci-dessus de Luca Fiaschi.

b=[]
for i in range(nruns):
    s=time.time()
    c1=np.array(a, dtype=int).reshape((N,1000))
    b.append((time.time()-s))

print("Timing version array.reshape ",np.mean(b))

Le résultat de chronométrage pour moi est :

Timing version vstack         0.6863266944885253
Timing version reshape        0.505419111251831
Timing version array.reshape  0.5052066326141358
Timing version concatenate    0.5339600563049316