Najszybszy sposób na powiększenie numpy tablicy numerycznej

80

Wymagania:

  • Muszę utworzyć dowolnie dużą tablicę na podstawie danych.
  • Mogę odgadnąć rozmiar (około 100-200) bez gwarancji, że tablica będzie pasować za każdym razem
  • Gdy osiągnie ostateczny rozmiar, muszę wykonać na nim obliczenia numeryczne, więc wolałbym ostatecznie przejść do tablicy numpy 2-D.
  • Szybkość jest krytyczna. Na przykład dla jednego z 300 plików metoda update () jest wywoływana 45 milionów razy (zajmuje około 150 sekund), a metoda finalize () jest wywoływana 500 tys. Razy (zajmuje łącznie 106 sekund) ... w sumie 250 sekund lub tak.

Oto mój kod:

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

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

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

Inne rzeczy, które próbowałem, obejmują następujący kod ... ale to jest bardzo wolniejsze.

def class 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, size=(self.data.shape[0]/5, 5))

Oto schemat, jak to się nazywa:

for i in range(500000):
    ax = A()
    for j in range(200):
         ax.update([1,2,3,4,5])
    ax.finalize()
    # some processing on ax
python  performance  numpy 
— fodon
źródło
2
Czy musi to być tablica numpy, zanim zostanie zakończona? Jeśli nie, użyj listy list, a po zakończeniu dokonaj konwersji.
— Andrew Jaffe,
1
@AndrewJaffe Czy listy list odpowiadają wydajności pamięci numpy?
— AturSams

Odpowiedzi:

96

Próbowałem kilku różnych rzeczy, z wyczuciem czasu.

import numpy as np

  1. Wspomniana metoda jako wolna: (32,094 sekundy)

    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. Zwykła lista ol Pythona: (0,308 sekundy)

    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. Próba zaimplementowania arraylisty w numpy: (0,362 sekundy)

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

I tak to zaplanowałem:

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

Wygląda więc na to, że zwykłe stare listy w Pythonie są całkiem dobre;)

— piekarnik
źródło
1
Myślę, że porównanie jest wyraźniejsze w przypadku 60 mln aktualizacji i 500 tys. Wygląda na to, że w tym przykładzie nie wywołałeś finalizacji.
— fodon
1
@fodon Właściwie zadzwoniłem do finalize - raz na przebieg (więc nie wydaje mi się, żeby miało to duży wpływ). Ale to sprawia, że ​​myślę, że może źle zrozumiałem, jak rosną twoje dane: jeśli dostaniesz 60 milionów podczas aktualizacji, myślałem, że dostarczy to co najmniej 60 milionów danych do następnej finalizacji?
— Owen
@Owen 60M i 500k średnimi 60 mln i 500 tys wywołania updatei finalizeodpowiednio. Zobacz mój poprawiony czas, który testuje stosunek 100: 1 updatedofinalize
— Prashant Kumar
Zaktualizowałem pytanie krótkim skryptem (który może nie być poprawny składniowo), aby dać wyobrażenie, jak to działa.
— fodon
3
Pamiętaj, że trzecia opcja jest lepsza, gdy kończy się pamięć. Druga opcja wymaga dużej ilości pamięci. Powodem jest to, że listy Pythona są tablicami odniesień do wartości, podczas gdy tablice NumPy są rzeczywistymi tablicami wartości.
— Fabianius,
20

np.append () kopiuje wszystkie dane z tablicy za każdym razem, ale lista zwiększa pojemność o współczynnik (1,125). lista jest szybka, ale użycie pamięci jest większe niż tablica. Jeśli zależy Ci na pamięci, możesz użyć modułu tablicy ze standardowej biblioteki Pythona.

Oto dyskusja na ten temat:

Jak utworzyć tablicę dynamiczną

— HYRY
źródło
2
czy istnieje sposób, aby zmienić czynnik, o który rośnie lista?
— fodon
1
np.append () pochłaniający czas wykładniczo rośnie wraz z liczbą elementów.
— Zegar ZHONG
1
^ liniowa (tzn. całkowity czas skumulowany jest czterokrotnie), a nie wykładniczy.
— user1111929
15

Korzystając z deklaracji klas w poście Owena, tutaj jest poprawiona synchronizacja z pewnym efektem finalizacji.

Krótko mówiąc, uważam, że klasa C zapewnia implementację, która jest ponad 60 razy szybsza niż metoda w oryginalnym poście. (przepraszam za ścianę tekstu)

Plik, którego użyłem:

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

# ... class declarations here ...

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)

Teraz wynikowe czasy:

ZA:

     903005 function calls in 16.049 seconds

Ordered by: standard name

ncalls  tottime  percall  cumtime  percall filename:lineno(function)
     1    0.000    0.000   16.049   16.049 <string>:1(<module>)
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 function calls in 16.885 seconds

Ordered by: standard name

ncalls  tottime  percall  cumtime  percall filename:lineno(function)
     1    0.001    0.001   16.885   16.885 <string>:1(<module>)
  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}

DO:

     204010 function calls in 0.244 seconds

Ordered by: standard name

ncalls  tottime  percall  cumtime  percall filename:lineno(function)
     1    0.000    0.000    0.244    0.244 <string>:1(<module>)
  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}

Klasa A jest niszczona przez aktualizacje, klasa B jest niszczona podczas finalizacji. Klasa C jest wytrzymała w obliczu obu z nich.

— Prashant Kumar
źródło
Aktualizacja jest wykonywana raz, a następnie finalizacja jest wywoływana raz. Cały ten proces jest wykonywany m razy (w przeciwnym razie nie ma danych do sfinalizowania). Ponadto, porównując z oryginalnym postem ... czy masz na myśli pierwszy (array.append + numpy conversion) czy (numpy.append + reshape)?
— fodon
1
cProfile. To pierwszy import i ostatnia linia wywołana w moim fragmencie kodu.
— Prashant Kumar
5

istnieje duża różnica w wydajności funkcji, której używasz do finalizacji. Rozważ następujący kod:

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 "Timing version vstack ",np.mean(b)

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

print "Timing 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 "Timing version concatenate ",np.mean(b)

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

Używanie konkatenacji wydaje się być dwa razy szybsze niż pierwsza wersja i ponad 10 razy szybsze niż druga wersja.

Timing version vstack  1.5774928093
Timing version reshape  9.67419199944
Timing version concatenate  0.669512557983
— Luca Fiaschi
źródło
1

Jeśli chcesz poprawić wydajność operacji na listach, spójrz na bibliotekę blist. Jest to zoptymalizowana implementacja listy Pythona i innych struktur.

Nie testowałem tego jeszcze, ale wyniki na ich stronie wydają się obiecujące.

— joaonrb
źródło
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.