Làm cách nào để tôi điền hai (hoặc nhiều) mảng khối ô từ một bộ lặp có thể lặp lại?

Question

Vấn đề thực tế tôi có là tôi muốn lưu trữ một danh sách dài được sắp xếp của (float, str) bộ dữ liệu trong RAM. Một danh sách đơn giản không phù hợp với RAM 4Gb của tôi, vì vậy tôi nghĩ tôi có thể sử dụng hai số numpy.ndarray s.

Nguồn dữ liệu có thể lặp lại với 2 bộ dữ liệu. numpy có chức năng fromiter, nhưng làm cách nào tôi có thể sử dụng? Số lượng mục trong vòng lặp không xác định được. Tôi không thể tiêu thụ nó vào một danh sách đầu tiên do giới hạn bộ nhớ. Tôi nghĩ về itertools.tee, nhưng có vẻ như thêm rất nhiều phí bộ nhớ ở đây.

Những gì tôi đoán tôi có thể làm là tiêu thụ trình lặp trong các khối và thêm chúng vào các mảng. Sau đó, câu hỏi của tôi là, làm thế nào để làm điều đó một cách hiệu quả? Tôi có nên tạo 2 mảng 2D và thêm hàng vào chúng không? (Sau đó, tôi cần phải chuyển đổi chúng thành 1D).

Hoặc có thể có cách tiếp cận tốt hơn? Mọi thứ tôi thực sự cần là tìm kiếm thông qua một chuỗi các chuỗi bằng giá trị của số tương ứng trong thời gian logarit (đó là lý do tại sao tôi muốn sắp xếp theo giá trị của phao) và giữ cho nó càng nhỏ càng tốt.

P.S. Các iterable không được sắp xếp.

Answer 1

lẽ xây dựng một duy nhất, cấu trúc mảng bằng np.fromiter:

import numpy as np 


def gendata(): 
    # You, of course, have a different gendata... 
    for i in xrange(N): 
     yield (np.random.random(), str(i)) 

N = 100 

arr = np.fromiter(gendata(), dtype='<f8,|S20') 

Sorting nó bằng cách cột đầu tiên, bằng cách sử dụng thứ hai cho tie-ngắt sẽ mất O (N log N) thời gian:

arr.sort(order=['f0','f1']) 

Tìm hàng theo giá trị trong cột đầu tiên có thể được thực hiện với searchsorted trong thời gian O (log N):

# Some pseudo-random value in arr['f0'] 
val = arr['f0'][10] 
print(arr[10]) 
# (0.049875262239617246, '46') 

idx = arr['f0'].searchsorted(val) 
print(arr[idx]) 
# (0.049875262239617246, '46') 

---

Bạn đã hỏi nhiều câu hỏi quan trọng trong nhận xét; hãy để tôi cố gắng trả lời chúng tại đây:

• Các loại dtypes cơ bản được giải thích trong numpybook. Có thể có một hoặc hai dtypes thêm (như float16 mà đã được thêm vào vì đó cuốn sách được viết ra, nhưng những điều cơ bản đều đã giải thích ở đó.)

  Có lẽ một cuộc thảo luận kỹ lưỡng hơn là trong online documentation. Đó là một bổ sung tốt cho các ví dụ bạn đã đề cập here.

• Dtypes có thể được sử dụng để xác định mảng có cấu trúc có tên cột hoặc với tên cột mặc định. 'f0', 'f1', v.v. là các cột mặc định là . Vì tôi đã xác định dtype là '<f8,|S20' Tôi không cung cấp được tên của các tên cột , vì vậy NumPy đặt tên cột đầu tiên là 'f0' và thứ hai 'f1'. Nếu chúng ta đã sử dụng

  dtype='[('fval','<f8'), ('text','|S20')] 
  

  thì mảng cấu trúc arr sẽ có tên cột 'fval' và 'text'.

• Thật không may, dtype phải được sửa vào thời điểm np.fromiter được gọi. Bạn conceivably có thể lặp qua gendata một lần để khám phá chiều dài tối đa của chuỗi, xây dựng dtype của bạn và sau đó gọi np.fromiter (và lặp qua gendata một lần thứ hai), nhưng đó là khá nặng nề. Đó là tất nhiên tốt hơn nếu bạn biết trong trước kích thước tối đa của các chuỗi. (|S20 xác định trường chuỗi có độ dài cố định là 20 byte.)
• NumPy mảng đặt dữ liệu của một kích thước được xác định trước trong các mảng có kích thước cố định. Hãy suy nghĩ về mảng (ngay cả những mảng đa chiều) như một khối tiếp giáp của bộ nhớ một chiều. (Đó là một sự đơn giản - có những mảng không tiếp giáp - nhưng sẽ giúp trí tưởng tượng của bạn cho những điều sau đây.) NumPy phát sinh phần lớn tốc độ của nó bằng cách tận dụng các kích thước cố định (được thiết lập bởi dtype) để nhanh chóng tính toán các offset cần thiết truy cập các phần tử trong mảng. Nếu các chuỗi có các kích thước khác nhau, thì sẽ khó cho NumPy để tìm đúng độ lệch. Bởi khó khăn, tôi có nghĩa là NumPy sẽ cần một chỉ mục hoặc bằng cách nào đó được thiết kế lại. NumPy chỉ đơn giản là không phải là được xây dựng theo cách này.
• NumPy có kiểu mã là object cho phép bạn đặt con trỏ4 byte vào bất kỳ đối tượng Python nào bạn muốn. Bằng cách này, bạn có thể có các mảng NumPy với dữ liệu Python tùy ý. Thật không may, chức năng np.fromiter không cho phép bạn tạo mảng dtype object. Tôi không chắc chắn tại sao có hạn chế này ...
• Lưu ý rằng np.fromiter có hiệu suất tốt hơn khi count là được chỉ định. Bằng cách biết số count (số hàng) và dtype (và do đó kích thước của mỗi hàng) NumPy có thể phân bổ trước chính xác đủ bộ nhớ cho mảng kết quả. Nếu bạn không chỉ định số count thì NumPy sẽ đoán trước kích thước ban đầu của mảng và nếu quá nhỏ, nó sẽ cố gắng thay đổi kích thước mảng. Nếu khối ban đầu của bộ nhớ có thể được mở rộng, bạn đang ở trong may mắn. Nhưng nếu NumPy phải phân bổ một bộ nhớ hoàn toàn mới thì tất cả dữ liệu cũ sẽ phải được sao chép sang vị trí mới, điều này sẽ làm chậm hiệu suất đáng kể.

Answer 2

Đây là một cách để xây dựng N mảng riêng biệt ra khỏi một máy phát điện của N -tuples:

import numpy as np 
import itertools as IT 


def gendata(): 
    # You, of course, have a different gendata... 
    N = 100 
    for i in xrange(N): 
     yield (np.random.random(), str(i)) 


def fromiter(iterable, dtype, chunksize=7): 
    chunk = np.fromiter(IT.islice(iterable, chunksize), dtype=dtype) 
    result = [chunk[name].copy() for name in chunk.dtype.names] 
    size = len(chunk) 
    while True: 
     chunk = np.fromiter(IT.islice(iterable, chunksize), dtype=dtype) 
     N = len(chunk) 
     if N == 0: 
      break 
     newsize = size + N 
     for arr, name in zip(result, chunk.dtype.names): 
      col = chunk[name] 
      arr.resize(newsize, refcheck=0) 
      arr[size:] = col 
     size = newsize 
    return result 

x, y = fromiter(gendata(), '<f8,|S20') 

order = np.argsort(x) 
x = x[order] 
y = y[order] 

# Some pseudo-random value in x 
N = 10 
val = x[N] 
print(x[N], y[N]) 
# (0.049875262239617246, '46') 

idx = x.searchsorted(val) 
print(x[idx], y[idx]) 
# (0.049875262239617246, '46') 

Chức năng fromiter trên đọc iterable trong khối (kích thước chunksize). Nó gọi phương thức mảng NumPy resize để mở rộng các mảng kết quả khi cần thiết.

Tôi đã sử dụng mặc định nhỏ chunksize vì tôi đã thử nghiệm mã này trên dữ liệu nhỏ. Tất nhiên, bạn sẽ muốn thay đổi kích thước mặc định hoặc chuyển thông số chunksize với giá trị lớn hơn.