Làm thế nào để tạo ra iterate thông qua một danh sách lớn các danh sách trong python hiệu quả?

Question

Tôi có dữ liệu của tôi như vậy:

data = {'x':Counter({'a':1,'b':45}), 'y':Counter({'b':1, 'c':212})} 

nơi nhãn của tôi là chìa khóa của data và chìa khóa của từ điển bên trong là các tính năng:

all_features = ['a','b','c'] 
all_labels = ['x','y'] 

tôi cần phải tạo ra danh sách các danh sách như ví dụ:

[[data[label][feat] for feat in all_features] for label in all_labels] 

[ra]:

[[1, 45, 0], [0, 1, 212]] 

My len(all_features) là ~ 5.000.000 và len(all_labels) là ~ 100.000

Mục đích cuối cùng là tạo ra ma trận thưa thớt scipy, ví dụ .:

from collections import Counter 
from scipy.sparse import csc_matrix 
import numpy as np 


all_features = ['a','b','c'] 
all_labels = ['x','y'] 

csc_matrix(np.array([[data[label][feat] for feat in all_features] for label in all_labels])) 

nhưng vòng lặp thông qua một danh sách lớn của danh sách là khá hiệu quả.

Vì vậy, Tôi có thể xem danh sách danh sách lớn hiệu quả bằng cách nào?

Có cách nào khác để tạo ma trận scipy từ data mà không lặp qua tất cả các tính năng và nhãn không?

Answer 1

Chuyển từ điển từ điển thành một mảng mờ hoặc scipy, như bạn đang gặp phải, không quá nhiều niềm vui. Nếu bạn biết all_features và all_labels trước khi bàn tay, bạn có lẽ nên sử dụng ma trận COO thưa thớt scipy ngay từ đầu để giữ số lượng của bạn.

Cho dù điều đó là có thể hay không, bạn sẽ muốn giữ danh sách các tính năng và nhãn theo thứ tự sắp xếp, để tăng tốc độ tra cứu. Vì vậy, tôi sẽ cho rằng những điều sau đây không làm thay đổi một trong hai mảng:

all_features = np.array(all_features) 
all_labels = np.array(all_labels) 
all_features.sort() 
all_labels.sort() 

Cho phép trích xuất các nhãn trong data theo thứ tự chúng được lưu trữ trong từ điển, và nhìn thấy nơi ở all_labels không từng hạng mục sụp đổ:

labels = np.fromiter(data.iterkeys(), all_labels.dtype, len(data)) 
label_idx = np.searchsorted(all_labels, labels) 

Bây giờ cho phép đếm có bao nhiêu tính năng nào mỗi nhãn có, và tính toán từ nó số lượng các mục khác không sẽ có trong mảng thưa thớt của bạn:

label_features = np.fromiter((len(c) for c in data.iteritems()), np.intp, 
          len(data)) 
indptr = np.concatenate(([0], np.cumsum(label_features))) 
nnz = indptr[-1] 

Bây giờ, chúng tôi trích xuất các tính năng cho mỗi nhãn, và số lượng tương ứng của họ

import itertools 
features_it = itertools.chain(*(c.iterkeys() for c in data.itervalues())) 
features = np.fromiter(features_it, all_features.dtype, nnz) 
feature_idx = np.searchsorted(all_features, features) 
counts_it = itertools.chain(*(c.itervalues() for c in data.itervalues())) 
counts = np.fromiter(counts_it, np.intp, nnz) 

Với những gì chúng ta có, chúng ta có thể tạo ra một ma trận CSR trực tiếp, với các nhãn như hàng và các tính năng như cột:

sps_data = csr_matrix((counts, feature_idx, indptr), 
         shape=(len(all_labels), len(all_features))) 

Vấn đề duy nhất là các hàng của mảng thưa thớt này không theo thứ tự all_labels, nhưng theo thứ tự chúng xuất hiện khi lặp qua data.Nhưng chúng ta phải feature_idx nói với chúng ta đâu mỗi nhãn kết thúc, và chúng ta có thể sắp xếp lại các hàng bằng cách thực hiện:

sps_data = sps_data[np.argsort(label_idx)] 

Vâng, đó là lộn xộn, khó hiểu, và có lẽ không phải là rất nhanh, nhưng nó hoạt động, và nó sẽ có bộ nhớ hiệu quả hơn những gì bạn đề xuất trong câu hỏi của bạn:

>>> sps_data.A 
array([[ 1, 45, 0], 
     [ 0, 1, 212]], dtype=int64) 
>>> all_labels 
array(['x', 'y'], 
     dtype='<S1') 
>>> all_features 
array(['a', 'b', 'c'], 
     dtype='<S1') 

Answer 2

Bộ dữ liệu là khá lớn, vì vậy tôi không nghĩ là thực tế để xây dựng một mảng numPy tạm thời (nếu 32 số nguyên bit được sử dụng một 1e5 x Ma trận 5e6 sẽ yêu cầu ~ 2 Terabyte bộ nhớ).

Tôi giả sử bạn biết giới hạn trên cho số lượng nhãn.

Mã này có thể trông giống như:

import scipy.sparse 
n_rows = len(data.keys()) 
max_col = int(5e6) 
temp_sparse = scipy.sparse.lil_matrix((n_rows, max_col), dtype='int') 

for i, (features, counts) in enumerate(data.iteritems()): 
    for label, n in counts.iteritem(): 
     j = label_pos[label] 
     temp_sparse[i, j] = n 
csc_matrix = temp_sparse.csc_matrix(temp_matrix) 

đâu label_pos trả về cột-index của nhãn. Nếu hóa ra là không thực tế để sử dụng một từ điển để lưu trữ chỉ mục của 5 triệu nhãn một cơ sở dữ liệu ổ đĩa cứng nên làm. Từ điển có thể tạo trực tuyến, vì vậy kiến ​​thức trước đó về tất cả các nhãn là không cần thiết.

Lặp lại 100.000 tính năng sẽ mất thời gian hợp lý, vì vậy tôi nghĩ giải pháp này có thể hoạt động nếu tập dữ liệu đủ thưa thớt. Chúc may mắn!

Answer 3

có cách nào khác để tạo ma trận scipy từ dữ liệu mà không lặp lại thông qua tất cả các tính năng và nhãn không?

Tôi không nghĩ có bất kỳ cắt ngắn nào làm giảm tổng số lần tra cứu. Bạn đang bắt đầu với một từ điển đếm (một phân lớp dict) để cả hai cấp độ lồng nhau là các bộ sưu tập không có thứ tự. Cách duy nhất để đưa chúng trở lại theo thứ tự bắt buộc là thực hiện tra cứu data[label][feat] cho mọi điểm dữ liệu.

Bạn có thể cắt thời gian khoảng một nửa bằng cách đảm bảo tra cứu data[label] chỉ thực hiện một lần mỗi nhãn:

>>> counters = [data[label] for label in all_labels] 
>>> [[counter[feat] for feat in all_features] for counter in counters] 
[[1, 45, 0], [0, 1, 212]] 

Bạn cũng có thể cố gắng đẩy nhanh tiến độ thời gian chạy bằng cách sử dụng bản đồ() thay vì một danh sách hiểu (lập bản đồ có thể tận dụng lợi thế của length_hint nội bộ đến các mảng kết quả kích thước trước):

>>> [map(counter.__getitem__, all_features) for counter in counters] 
[[1, 45, 0], [0, 1, 212]] 

Cuối cùng, hãy chắc chắn để chạy các mã bên trong một hàm (tra cứu biến địa phương trong CPython là fas ter so với tra cứu biến toàn cầu):

def f(data, all_features, all_labels): 
    counters = [data[label] for label in all_labels] 
    return [map(counter.__getitem__, all_features) for counter in counters]