tại sao chuyển đổi danh sách 2D dài thành mảng có nhiều mảng chậm?

Question

Tôi có một danh sách dài các tọa độ xy và muốn chuyển đổi nó thành mảng có nhiều mảng.

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

Cách rõ ràng sẽ là:

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

Tuy nhiên, các mã trên là bất hợp lý chậm. Thật thú vị, để chuyển đổi danh sách dài đầu tiên, chuyển đổi nó thành mảng numpy, và sau đó chuyển đổi trở lại sẽ nhanh hơn nhiều (20x trên máy tính xách tay của tôi).

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

Đây có phải là lỗi không đầy đặn?

EDIT:

Đây là một danh sách các điểm (với tọa độ xy) tạo on-the-fly, nên thay vì preallocating một mảng và mở rộng nó khi cần thiết, hoặc duy trì hai danh sách 1D cho x và y, Tôi nghĩ đại diện hiện tại là tự nhiên nhất.

Tại sao vòng lặp thông qua chỉ mục thứ 2 nhanh hơn chỉ mục thứ nhất, do chúng tôi đang lặp qua danh sách python theo cả hai hướng?

EDIT 2:

Dựa trên câu trả lời @ Tiago và , tôi thấy đoạn mã sau hai lần nhanh như phiên bản ban đầu của tôi:

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

Thực hiện điều này trong Cython mà không cần kiểm tra thêm liên quan để xác định kích thước, vv gần như loại bỏ sự khác biệt thời gian bạn đang nhìn thấy. Đây là tệp .pyx tôi đã sử dụng để xác minh điều đó.

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 

Tôi giả sử thêm thời gian để kiểm tra độ dài và nội dung của từng danh sách con để xác định kiểu dữ liệu, thứ nguyên và kích thước của mảng mong muốn. Khi chỉ có hai danh sách con, nó chỉ phải kiểm tra hai độ dài để xác định số cột trong mảng, thay vì kiểm tra 1000000 của chúng.

Answer 2

Điều này là do chỉ số nhanh nhất thay đổi danh sách của bạn là cái cuối cùng, vì vậy np.array() phải đi qua mảng nhiều lần vì chỉ mục đầu tiên lớn hơn nhiều. Nếu danh sách của bạn đã được hoán, np.array() sẽ nhanh hơn longlist2array của bạn:

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 

Không có giải pháp kỳ diệu cho vấn đề của bạn. Nó chỉ là cách Python lưu trữ danh sách của bạn trong bộ nhớ. Bạn có thực sự cần phải có một danh sách với hình dạng đó? Bạn không thể đảo ngược nó? (? Và bạn có thực sự cần một danh sách, cho rằng bạn đang chuyển đổi để NumPy)

Nếu bạn phải chuyển đổi một danh sách, chức năng này là nhanh hơn so với bạn longlist2array khoảng 10%:

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

Nếu bạn có gấu trúc, bạn có thể sử dụng pandas.lib.to_object_array(), đó là phương pháp nhanh nhất:

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) 

kết quả đầu ra:

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