Thưa thớt trong Python

Hãy tưởng tượng bạn có một ma trận 2-D với hàng trăm triệu phần tử, trong đó chỉ một vài trong số chúng chứa các giá trị khác không. Khi lưu trữ một ma trận như vậy bằng cách sử dụng phương pháp thông thường, chúng ta sẽ lãng phí rất nhiều dung lượng cho các số không

Cấu trúc dữ liệu thưa thớt cho phép chúng tôi chỉ lưu trữ các giá trị khác không với giả sử phần còn lại của chúng là số không. Cách tiếp cận này tiết kiệm rất nhiều bộ nhớ và thời gian tính toán. Trên thực tế, bạn có thể thường xuyên gặp phải các ma trận như vậy khi làm việc với NLP hoặc các tác vụ học máy.

Trong Python, cấu trúc dữ liệu thưa thớt được triển khai trong scipy. mô-đun thưa thớt, phần lớn dựa trên mảng

from scipy.sparse import random

def get_sparse_size[matrix]:
    # get size of a sparse matrix
    return int[[matrix.data.nbytes + matrix.indptr.nbytes + matrix.indices.nbytes] / 1024.]

# create a sparse matrix, 1000 x 100000
sparse_mat = random[10 ** 3, 10 ** 5, format='csr']

# get size of a sparse matrix
sparse_size = get_sparse_size[sparse_mat]

# convert sparse matrix to a regular matrix and get its size
regular_size = sparse_mat.toarray[].nbytes / 1024.

1 thông thường

>>> import numpy as np
>>> from scipy.sparse import csc_matrix
>>> csc_matrix[[3, 4], dtype=np.int8].toarray[]
array[[[0, 0, 0, 0],
       [0, 0, 0, 0],
       [0, 0, 0, 0]], dtype=int8]

Hãy tạo một ma trận thưa thớt ngẫu nhiên và so sánh kích thước của nó với một ma trận thông thường giống hệt nhau

from scipy.sparse import random

def get_sparse_size[matrix]:
    # get size of a sparse matrix
    return int[[matrix.data.nbytes + matrix.indptr.nbytes + matrix.indices.nbytes] / 1024.]

# create a sparse matrix, 1000 x 100000
sparse_mat = random[10 ** 3, 10 ** 5, format='csr']

# get size of a sparse matrix
sparse_size = get_sparse_size[sparse_mat]

# convert sparse matrix to a regular matrix and get its size
regular_size = sparse_mat.toarray[].nbytes / 1024.

>>> print["The size of sparse matrix is %s KiB" % sparse_size]
The size of sparse matrix is 11722 KiB
>>> print["The size of regular matrix is %s KiB" % regular_size]
The size of regular matrix is 781250.0 KiB
>>> print["Data compression ratio is %s" % [regular_size / sparse_size]]
Data compression ratio is 66.6481829039413

Các loại ma trận thưa thớt trong scipy

Có nhiều cách để biểu diễn một ma trận thưa thớt, Scipy cung cấp bảy cách trong số đó

• Khối ma trận hàng thưa thớt [BSR]
• Ma trận danh sách tọa độ [COO]
• Ma trận cột thưa được nén [CSC]
• Ma trận hàng thưa được nén [CSR]
• Ma trận thưa thớt với lưu trữ DIAgonal [DIA]
• Dictionary Of Keys dựa trên ma trận thưa thớt [DOK]
• Ma trận thưa danh sách liên kết dựa trên hàng [LIL]

Mỗi định dạng đều có ưu và nhược điểm, vì vậy điều quan trọng là phải biết về sự khác biệt giữa chúng

Từ điển các phím [DOK]

Từ điển khóa [

from scipy.sparse import random

def get_sparse_size[matrix]:
    # get size of a sparse matrix
    return int[[matrix.data.nbytes + matrix.indptr.nbytes + matrix.indices.nbytes] / 1024.]

# create a sparse matrix, 1000 x 100000
sparse_mat = random[10 ** 3, 10 ** 5, format='csr']

# get size of a sparse matrix
sparse_size = get_sparse_size[sparse_mat]

# convert sparse matrix to a regular matrix and get its size
regular_size = sparse_mat.toarray[].nbytes / 1024.

2 trong scipy] là cách dễ nhất để triển khai ma trận thưa thớt. Như tên gợi ý, nó dựa trên một từ điển, trong đó các khóa là các bộ đại diện cho các chỉ số, tôi. e.

from scipy.sparse import random

def get_sparse_size[matrix]:
    # get size of a sparse matrix
    return int[[matrix.data.nbytes + matrix.indptr.nbytes + matrix.indices.nbytes] / 1024.]

# create a sparse matrix, 1000 x 100000
sparse_mat = random[10 ** 3, 10 ** 5, format='csr']

# get size of a sparse matrix
sparse_size = get_sparse_size[sparse_mat]

# convert sparse matrix to a regular matrix and get its size
regular_size = sparse_mat.toarray[].nbytes / 1024.

3

>>> import numpy as np
>>> from scipy.sparse import random
>>> np.random.seed[10]
>>>
>>> matrix = random[3, 3, format='dok', density=0.4]
>>> matrix[1, 1] = 33
>>> # dict[tuple[row, column]] = value
... matrix[[2, 1]] = 10
>>>
>>> matrix.toarray[]
[[  0.49850701   0.           0.        ]
 [  0.22479665  33.           0.        ]
 [  0.          10.           0.        ]]
>>> dict[matrix]
{[1, 0]: 0.22479664553084766, [0, 0]: 0.49850701230259042, [1, 1]: 33.0, [2, 1]: 10.0}

Thuận lợi

• truy cập hiệu quả vào các mục riêng lẻ [trung bình O[1]]
• thi công nhanh
• cấu trúc linh hoạt
• có thể được chuyển đổi hiệu quả sang định dạng COO

Nhược điểm

• lặp lại rất chậm theo thứ tự từ điển [do thứ tự ngẫu nhiên của các khóa]
• tính toán chậm
• cắt chậm

Danh sách của danh sách [LIL]

Định dạng dựa trên hàng [

from scipy.sparse import random

def get_sparse_size[matrix]:
    # get size of a sparse matrix
    return int[[matrix.data.nbytes + matrix.indptr.nbytes + matrix.indices.nbytes] / 1024.]

# create a sparse matrix, 1000 x 100000
sparse_mat = random[10 ** 3, 10 ** 5, format='csr']

# get size of a sparse matrix
sparse_size = get_sparse_size[sparse_mat]

# convert sparse matrix to a regular matrix and get its size
regular_size = sparse_mat.toarray[].nbytes / 1024.

4 trong scipy], sử dụng hai mảng có nhiều mảng với các danh sách Python thông thường bên trong chúng. Mảng

from scipy.sparse import random

def get_sparse_size[matrix]:
    # get size of a sparse matrix
    return int[[matrix.data.nbytes + matrix.indptr.nbytes + matrix.indices.nbytes] / 1024.]

# create a sparse matrix, 1000 x 100000
sparse_mat = random[10 ** 3, 10 ** 5, format='csr']

# get size of a sparse matrix
sparse_size = get_sparse_size[sparse_mat]

# convert sparse matrix to a regular matrix and get its size
regular_size = sparse_mat.toarray[].nbytes / 1024.

5 lưu trữ thông tin về các ô bị chiếm, trong khi mảng

from scipy.sparse import random

def get_sparse_size[matrix]:
    # get size of a sparse matrix
    return int[[matrix.data.nbytes + matrix.indptr.nbytes + matrix.indices.nbytes] / 1024.]

# create a sparse matrix, 1000 x 100000
sparse_mat = random[10 ** 3, 10 ** 5, format='csr']

# get size of a sparse matrix
sparse_size = get_sparse_size[sparse_mat]

# convert sparse matrix to a regular matrix and get its size
regular_size = sparse_mat.toarray[].nbytes / 1024.

6 lưu trữ các giá trị tương ứng

>>> import numpy as np
>>> from scipy.sparse import csc_matrix
>>> csc_matrix[[3, 4], dtype=np.int8].toarray[]
array[[[0, 0, 0, 0],
       [0, 0, 0, 0],
       [0, 0, 0, 0]], dtype=int8]

0

Một thuật toán đơn giản hóa để truy xuất một mục

>>> import numpy as np
>>> from scipy.sparse import csc_matrix
>>> csc_matrix[[3, 4], dtype=np.int8].toarray[]
array[[[0, 0, 0, 0],
       [0, 0, 0, 0],
       [0, 0, 0, 0]], dtype=int8]

1

Thuận lợi

• xây dựng gia tăng nhanh

Nhược điểm

• tính toán chậm
• cắt cột chậm
• bộ nhớ tham lam

Danh sách tọa độ [COO]

Trong scipy, định dạng COO [

from scipy.sparse import random

def get_sparse_size[matrix]:
    # get size of a sparse matrix
    return int[[matrix.data.nbytes + matrix.indptr.nbytes + matrix.indices.nbytes] / 1024.]

# create a sparse matrix, 1000 x 100000
sparse_mat = random[10 ** 3, 10 ** 5, format='csr']

# get size of a sparse matrix
sparse_size = get_sparse_size[sparse_mat]

# convert sparse matrix to a regular matrix and get its size
regular_size = sparse_mat.toarray[].nbytes / 1024.

7] sử dụng ba mảng, đối với mỗi giá trị khác không, có một mục nhập trong tất cả chúng

>>> import numpy as np
>>> from scipy.sparse import csc_matrix
>>> csc_matrix[[3, 4], dtype=np.int8].toarray[]
array[[[0, 0, 0, 0],
       [0, 0, 0, 0],
       [0, 0, 0, 0]], dtype=int8]

3

Mảng

from scipy.sparse import random

def get_sparse_size[matrix]:
    # get size of a sparse matrix
    return int[[matrix.data.nbytes + matrix.indptr.nbytes + matrix.indices.nbytes] / 1024.]

# create a sparse matrix, 1000 x 100000
sparse_mat = random[10 ** 3, 10 ** 5, format='csr']

# get size of a sparse matrix
sparse_size = get_sparse_size[sparse_mat]

# convert sparse matrix to a regular matrix and get its size
regular_size = sparse_mat.toarray[].nbytes / 1024.

6 đang lưu trữ tất cả các giá trị khác không, trong khi

from scipy.sparse import random

def get_sparse_size[matrix]:
    # get size of a sparse matrix
    return int[[matrix.data.nbytes + matrix.indptr.nbytes + matrix.indices.nbytes] / 1024.]

# create a sparse matrix, 1000 x 100000
sparse_mat = random[10 ** 3, 10 ** 5, format='csr']

# get size of a sparse matrix
sparse_size = get_sparse_size[sparse_mat]

# convert sparse matrix to a regular matrix and get its size
regular_size = sparse_mat.toarray[].nbytes / 1024.

9 và

>>> print["The size of sparse matrix is %s KiB" % sparse_size]
The size of sparse matrix is 11722 KiB
>>> print["The size of regular matrix is %s KiB" % regular_size]
The size of regular matrix is 781250.0 KiB
>>> print["Data compression ratio is %s" % [regular_size / sparse_size]]
Data compression ratio is 66.6481829039413

0 đang lưu trữ các chỉ số tương ứng cho các giá trị này

datarowcol0. 72493393000. 4202036100. 485427112

Để tìm một giá trị cụ thể trong ma trận, bạn cần lặp lại cả hai mảng chỉ mục, điều này làm cho việc truy cập chậm khi so sánh với các định dạng khác

Thuận lợi

• xây dựng gia tăng nhanh
• số học thông minh về mặt hàng nhanh
• chuyển đổi nhanh sang định dạng CSR/CSC
• cho phép các mục trùng lặp

Nhược điểm

• truy cập chậm
• tính toán chậm

Nén Định dạng thưa thớt

Hàng thưa được nén [CSR] và cột thưa được nén [CSC] là các định dạng được biết đến rộng rãi và được sử dụng nhiều nhất. Chủ yếu, chúng được sử dụng cho các tác vụ ghi một lần đọc nhiều lần

Trong nội bộ, CSR dựa trên ba mảng gọn gàng

• from scipy.sparse import random
  
  def get_sparse_size[matrix]:
      # get size of a sparse matrix
      return int[[matrix.data.nbytes + matrix.indptr.nbytes + matrix.indices.nbytes] / 1024.]
  
  # create a sparse matrix, 1000 x 100000
  sparse_mat = random[10 ** 3, 10 ** 5, format='csr']
  
  # get size of a sparse matrix
  sparse_size = get_sparse_size[sparse_mat]
  
  # convert sparse matrix to a regular matrix and get its size
  regular_size = sparse_mat.toarray[].nbytes / 1024.
  

  6 là một mảng chứa tất cả các mục nhập khác không theo thứ tự chính của hàng

• >>> print["The size of sparse matrix is %s KiB" % sparse_size]
  The size of sparse matrix is 11722 KiB
  >>> print["The size of regular matrix is %s KiB" % regular_size]
  The size of regular matrix is 781250.0 KiB
  >>> print["Data compression ratio is %s" % [regular_size / sparse_size]]
  Data compression ratio is 66.6481829039413
  

  2 điểm để bắt đầu hàng [i. e. , cho biết vị trí mỗi hàng bắt đầu]

• >>> print["The size of sparse matrix is %s KiB" % sparse_size]
  The size of sparse matrix is 11722 KiB
  >>> print["The size of regular matrix is %s KiB" % regular_size]
  The size of regular matrix is 781250.0 KiB
  >>> print["Data compression ratio is %s" % [regular_size / sparse_size]]
  Data compression ratio is 66.6481829039413
  

  3 là mảng các chỉ số cột [i. e. , cho chúng tôi biết ô nào có giá trị khác 0]

from scipy.sparse import random

def get_sparse_size[matrix]:
    # get size of a sparse matrix
    return int[[matrix.data.nbytes + matrix.indptr.nbytes + matrix.indices.nbytes] / 1024.]

# create a sparse matrix, 1000 x 100000
sparse_mat = random[10 ** 3, 10 ** 5, format='csr']

# get size of a sparse matrix
sparse_size = get_sparse_size[sparse_mat]

# convert sparse matrix to a regular matrix and get its size
regular_size = sparse_mat.toarray[].nbytes / 1024.

0

Chúng ta có thể truy cập và sửa đổi các mảng này

from scipy.sparse import random

def get_sparse_size[matrix]:
    # get size of a sparse matrix
    return int[[matrix.data.nbytes + matrix.indptr.nbytes + matrix.indices.nbytes] / 1024.]

# create a sparse matrix, 1000 x 100000
sparse_mat = random[10 ** 3, 10 ** 5, format='csr']

# get size of a sparse matrix
sparse_size = get_sparse_size[sparse_mat]

# convert sparse matrix to a regular matrix and get its size
regular_size = sparse_mat.toarray[].nbytes / 1024.

1

Thuật toán lập chỉ mục mục được đơn giản hóa trông như sau

from scipy.sparse import random

def get_sparse_size[matrix]:
    # get size of a sparse matrix
    return int[[matrix.data.nbytes + matrix.indptr.nbytes + matrix.indices.nbytes] / 1024.]

# create a sparse matrix, 1000 x 100000
sparse_mat = random[10 ** 3, 10 ** 5, format='csr']

# get size of a sparse matrix
sparse_size = get_sparse_size[sparse_mat]

# convert sparse matrix to a regular matrix and get its size
regular_size = sparse_mat.toarray[].nbytes / 1024.

2

from scipy.sparse import random

def get_sparse_size[matrix]:
    # get size of a sparse matrix
    return int[[matrix.data.nbytes + matrix.indptr.nbytes + matrix.indices.nbytes] / 1024.]

# create a sparse matrix, 1000 x 100000
sparse_mat = random[10 ** 3, 10 ** 5, format='csr']

# get size of a sparse matrix
sparse_size = get_sparse_size[sparse_mat]

# convert sparse matrix to a regular matrix and get its size
regular_size = sparse_mat.toarray[].nbytes / 1024.

0

Thuận lợi

• truy cập và cắt mục hiệu quả
• số học nhanh
• sản phẩm vector nhanh

Nhược điểm

• chỉnh sửa đắt tiền

Định dạng Cột thưa được nén [CSC] gần như giống hệt nhau, ngoại trừ các giá trị được lập chỉ mục đầu tiên theo cột với thứ tự chính của cột. Thông thường, CSC được sử dụng khi có nhiều hàng hơn cột. Ngược lại, CSR hoạt động tốt hơn đối với định dạng 'rộng'

Khối lưu trữ ma trận hàng thưa [BSR] và đường chéo

Lưu trữ đường chéo [

>>> print["The size of sparse matrix is %s KiB" % sparse_size]
The size of sparse matrix is 11722 KiB
>>> print["The size of regular matrix is %s KiB" % regular_size]
The size of regular matrix is 781250.0 KiB
>>> print["Data compression ratio is %s" % [regular_size / sparse_size]]
Data compression ratio is 66.6481829039413

4 là scipy] được sử dụng khi bạn cần lưu trữ ma trận đường chéo. Trong scipy, việc triển khai không chỉ giới hạn ở đường chéo chính. Tất cả các đường chéo được lưu trữ bằng hai mảng, một cho dữ liệu và một cho độ lệch đường chéo

Định dạng hàng thưa của khối rất giống với CSR, ngoại trừ nó lưu trữ các mẫu khối [hình vuông] thông thường chứa hầu hết dữ liệu khác không

thưa thớt nghĩa là gì trong Python?

Python mảng thưa thớt là gì?

Việc sử dụng thưa thớt là gì?

Giá trị thưa thớt là gì?