dlaczego konwertowanie długiej listy 2D na tablicę numpy jest tak powolne?

Question

Mam długą listę współrzędnych xy i chciałbym przekształcić go w tablicy numpy.

>>> import numpy as np 
>>> xy = np.random.rand(1000000, 2).tolist() 

Oczywistym sposobem byłoby:

>>> a = np.array(xy) # Very slow... 

Jednakże powyższy kod jest stanowczo za wolno. Co ciekawe, aby przetransponować długą listę najpierw, przekonwertuj ją na tablicę numpy, a następnie przetransferuj ją z powrotem znacznie szybciej (20x na moim laptopie).

>>> def longlist2array(longlist): 
...  wide = [[row[c] for row in longlist] for c in range(len(longlist[0]))] 
...  return np.array(wide).T 
>>> a = longlist2array(xy) # 20x faster! 

Czy to błąd numpy?

Edycja:

Jest to lista punktów (o współrzędnych XY) generowany w locie, tak zamiast preallocating tablicy i rozszerzenia, gdy jest to konieczne, lub utrzymywania dwóch 1D listy dla x i y, Myślę, że obecna reprezentacja jest najbardziej naturalna.

Dlaczego przechodzimy przez drugi indeks szybciej niż pierwszy indeks, biorąc pod uwagę, że przechodzimy przez listę python w obu kierunkach?

EDIT 2:

podstawie odpowiedzi @ Tiago i , znalazłem następujący kod dwa razy tak szybko, jak mojej oryginalnej wersji:

>>> from itertools import chain 
>>> def longlist2array(longlist): 
...  flat = np.fromiter(chain.from_iterable(longlist), np.array(longlist[0][0]).dtype, -1) # Without intermediate list:) 
...  return flat.reshape((len(longlist), -1)) 

Answer 1

Realizacja tego w Cython bez dodatkowego sprawdzenia związanego z określaniem wymiarowości itp. prawie eliminuje różnicę czasu, którą widzisz. Oto plik .pyx, którego użyłem do zweryfikowania tego.

from numpy cimport ndarray as ar 
import numpy as np 
cimport cython 

@cython.boundscheck(False) 
@cython.wraparound(False) 
def toarr(xy): 
    cdef int i, j, h=len(xy), w=len(xy[0]) 
    cdef ar[double,ndim=2] new = np.empty((h,w)) 
    for i in xrange(h): 
     for j in xrange(w): 
      new[i,j] = xy[i][j] 
    return new 

Przypuszczam, że dodatkowy czas spędzony na sprawdzeniu długość i zawartość poszczególnych podmenu w celu określenia typów danych, wymiarów i wielkości pożądanej tablicy. Gdy są tylko dwie podlisty, wystarczy sprawdzić dwie długości, aby określić liczbę kolumn w tablicy, zamiast sprawdzać 1000000 z nich.

Answer 2

To dlatego, że najszybciej różnym indeks listy jest ostatnim, więc np.array() musi wielokrotnie przechodzić przez tablicę, ponieważ pierwszy indeks jest znacznie większy. Jeśli lista została transponowana, np.array() byłoby szybciej niż longlist2array:

In [65]: import numpy as np 

In [66]: xy = np.random.rand(10000, 2).tolist() 

In [67]: %timeit longlist2array(xy) 
100 loops, best of 3: 3.38 ms per loop 

In [68]: %timeit np.array(xy) 
10 loops, best of 3: 55.8 ms per loop 

In [69]: xy = np.random.rand(2, 10000).tolist() 

In [70]: %timeit longlist2array(xy) 
10 loops, best of 3: 59.8 ms per loop 

In [71]: %timeit np.array(xy) 
1000 loops, best of 3: 1.96 ms per loop 

Nie ma magiczne rozwiązanie problemu. Tak właśnie Python przechowuje twoją listę w pamięci. Czy naprawdę potrzebujesz listy o tym kształcie? Nie możesz tego odwrócić? (? I czy naprawdę potrzebujemy listę, biorąc pod uwagę, że jesteś konwersja do NumPy)

Jeśli trzeba konwertować listę, funkcja ta jest o 10% szybsza niż longlist2array:

from itertools import chain 

def convertlist(longlist) 
    tmp = list(chain.from_iterable(longlist)) 
    return np.array(tmp).reshape((len(longlist), len(longlist[0]))) 

Answer 3

Jeśli masz pandy, można użyć pandas.lib.to_object_array(), jest to najszybsza metoda:

import numpy as np 
import pandas as pd 
a = np.random.rand(100000, 2) 
b = a.tolist() 

%timeit np.array(b, dtype=float, ndmin=2) 
%timeit np.array(b, dtype=object).astype(float) 
%timeit np.array(zip(*b)).T 
%timeit pd.lib.to_object_array(b).astype(float) 

wyjścia:

1 loops, best of 3: 462 ms per loop 
1 loops, best of 3: 192 ms per loop 
10 loops, best of 3: 39.9 ms per loop 
100 loops, best of 3: 13.7 ms per loop