Lưu trữ Python ma trận thưa thớt

Trong hướng dẫn này, chúng ta sẽ tìm hiểu cách lưu trữ ma trận thưa thớt một cách hiệu quả bằng cách sử dụng từ điển trong Python. Nhiều lần chúng ta gặp phải tình huống lãng phí bộ nhớ để lưu trữ dữ liệu một cách không hiệu quả. Để khắc phục vấn đề này, chúng ta có thể sử dụng các cấu trúc dữ liệu như từ điển trong Python

TỪ ĐIỂN

Từ điển là một cấu trúc dữ liệu trong đó chúng tôi lưu trữ các giá trị dưới dạng một cặp khóa và giá trị

• Mỗi khóa của nó được cách ly với giá trị của nó bằng dấu hai chấm [. ]
• Các mục liên tiếp được phân biệt bằng dấu phẩy [,]

cú pháp

Dictonary_name={key1:value_1,key2:value_2...}

MA TRẬN THẺ

Nó là một ma trận chứa rất ít phần tử khác không. Hầu hết các phần tử của nó bằng không. Khi nó được biểu diễn bằng mảng 2 chiều, chúng ta sẽ tốn rất nhiều dung lượng trong bộ nhớ

Vì hầu hết các phần tử của nó đều bằng 0, nên chúng tôi cố gắng chỉ lưu trữ các phần tử khác 0 vì dù sao thì tất cả các phần tử còn lại cũng sẽ bằng 0. Vì vậy, bây giờ một câu hỏi đặt ra là tại sao lại sử dụng ma trận thưa thớt này?

Câu trả lời là các ma trận này rất hữu ích để lưu trữ dữ liệu chứa một số lượng lớn các phần tử có giá trị bằng 0 và có thể tiết kiệm rất nhiều bộ nhớ cũng như tăng tốc độ xử lý

[1,]    [2,]      [3,]     [4,]     [5,]

[,1]    2         0        0       0        0

[,2]   0         0       0        0        1

[,3]   2          0          2       0         0

[,4]    0        0          0        3         0

[,5]    1        4         0         0         0

Để lưu trữ cái này hiệu quả hơn trong bộ nhớ, chúng tôi sử dụng từ điển trong Python. Bằng cách sử dụng từ điển, chúng ta có thể chỉ ra các hàng và cột có chứa phần tử khác 0 cùng với giá trị có trong chúng

matrix=[[0,0,0,1,0],
        [2,0,0,0,3],
        [0,0,0,4,0]]
Dict={}
print["Sparse Matrix"]
for i in range [len[matrix]]:
     print["\n"]
     for j in range[len[matrix[i]]]:
         print[matrix[i][j],end=' ']
         if matrix[i][j]!=0:
            Dict[[i,j]]=matrix[i][j]
print["\n\n Sparse Matrix can be efficiently represented as Dictionary :"]
print[Dict]

ĐẦU RA

Sparse Matrix
0 0 0 1 0
2 0 0 0 3
0 0 0 4 0
sparse matrix can be efficiently represented as Dictionary:
{[0, 3]: 1, [2, 3]: 4, [1, 0]: 2, [1, 4]: 3}

Trong ví dụ trên, ma trận chỉ chứa 4 phần tử khác không và do đó chúng được hiển thị dưới dạng từ điển

Nhiều phương pháp tồn tại để lưu trữ các ma trận thưa thớt ở các định dạng nén tiêu thụ ít bộ nhớ hơn đáng kể so với các ma trận dày đặc điển hình1

Các ma trận thưa được nén trong Python được xử lý phổ biến nhất với mô-đun thưa từ scipy. Theo đó, bộ bài toán này kiểm tra kiến ​​thức của bạn về ma trận thưa thớt của scipy

Bạn có biết NumPy không?

scipy được xây dựng trên NumPy. Chúng tôi thực sự khuyên bạn nên tìm hiểu một số NumPy trước khi học các ma trận thưa thớt scipy

Cách cài đặt scipy¶

pip insall scipy

Cách nhập mô-đun thưa thớt của scipy¶

from scipy import sparse

Định dạng nén ma trận thưa thớt¶

Ma trận thưa thớt có thể được lưu trữ ở nhiều định dạng nén khác nhau, mỗi định dạng có ưu và nhược điểm riêng

FormatDetailsProsConsDictionary Of Keys [DOK]sử dụng từ điển để ánh xạ [hàng, cột]-các cặp với giá trị của các phần tử- truy cập nhanh vào các phần tử riêng lẻ
- tốt cho việc xây dựng ma trận gia tăng- .
- slow access rows, colsList of Lists [LIL]stores one list per row, with each entry containing the column index and the value- good for incremental matrix construction- slow access to elements
- slow access to rows, colsCompressed Sparse Row [CSR]Stores three arrays:
- các mục nhập khác 0
- chỉ số cột của các mục nhập khác 0
- tổng số mục nhập khác 0, mỗi .
- các mục nhập khác 0
- chỉ số hàng của các mục nhập khác 0
- số lượng tích lũy của các mục nhập khác 0, mỗi

Hàng thưa được nén [CSR]¶

Giả sử bạn có một ma trận thưa thớt như thế này

uncompressed = np.array[
    [[0, 0, 3, 0, 0],
     [0, 0, 0, 0, 1],
     [1, 0, 0, 2, 0],
     [0, 0, 0, 0, 0],
     [0, 0, 0, 0, 1]]
]

Để lưu trữ ma trận này ở định dạng CSR cần có ba mảng

• ______43. một mảng chứa giá trị của từng phần tử khác không
  Trong ví dụ này.

  from scipy import sparse
  

  4
• ______45. một mảng chứa chỉ mục cột của từng phần tử khác không
  Trong ví dụ này.

  from scipy import sparse
  

  6
• ____47. một mảng chứa tổng số phần tử khác 0 tích lũy trên mỗi hàng của ma trận, được thêm vào trước bởi 0
  Trong ví dụ này.

  from scipy import sparse
  

  8

Bạn có thể xác nhận điều này trong scipy bằng cách chuyển đổi

from scipy import sparse

9 thành

uncompressed = np.array[
    [[0, 0, 3, 0, 0],
     [0, 0, 0, 0, 1],
     [1, 0, 0, 2, 0],
     [0, 0, 0, 0, 0],
     [0, 0, 0, 0, 1]]
]

0 và kiểm tra các thuộc tính

from scipy import sparse

3,

from scipy import sparse

5 và

from scipy import sparse

7 của nó

matrix=[[0,0,0,1,0],
        [2,0,0,0,3],
        [0,0,0,4,0]]
Dict={}
print["Sparse Matrix"]
for i in range [len[matrix]]:
     print["\n"]
     for j in range[len[matrix[i]]]:
         print[matrix[i][j],end=' ']
         if matrix[i][j]!=0:
            Dict[[i,j]]=matrix[i][j]
print["\n\n Sparse Matrix can be efficiently represented as Dictionary :"]
print[Dict]

7

Tại sao điều này lại hữu ích?
Việc xây dựng lại và vận hành trên các hàng của ma trận này cực kỳ hiệu quả vì

from scipy import sparse

7 cung cấp một cách trực tiếp để truy cập các phần tử khác 0 của bất kỳ hàng nào. Ví dụ: xem xét yêu cầu sau.

Tìm nạp các phần tử khác 0 ở hàng thứ ba của ma trận [chỉ số hàng 2]

Để hoàn thành việc này,

1. Tra cứu số phần tử khác 0 xuất hiện trước chỉ mục hàng 2

   matrix=[[0,0,0,1,0],
           [2,0,0,0,3],
           [0,0,0,4,0]]
   Dict={}
   print["Sparse Matrix"]
   for i in range [len[matrix]]:
        print["\n"]
        for j in range[len[matrix[i]]]:
            print[matrix[i][j],end=' ']
            if matrix[i][j]!=0:
               Dict[[i,j]]=matrix[i][j]
   print["\n\n Sparse Matrix can be efficiently represented as Dictionary :"]
   print[Dict]
   
   
   

   9

   1. Sparse Matrix
      0 0 0 1 0
      2 0 0 0 3
      0 0 0 4 0
      sparse matrix can be efficiently represented as Dictionary:
      {[0, 3]: 1, [2, 3]: 4, [1, 0]: 2, [1, 4]: 3}

      0

2. Tra cứu số phần tử khác 0 xuất hiện trên hoặc trước chỉ mục hàng 2

   Sparse Matrix
   0 0 0 1 0
   2 0 0 0 3
   0 0 0 4 0
   sparse matrix can be efficiently represented as Dictionary:
   {[0, 3]: 1, [2, 3]: 4, [1, 0]: 2, [1, 4]: 3}

   1

   1. Sparse Matrix
      0 0 0 1 0
      2 0 0 0 3
      0 0 0 4 0
      sparse matrix can be efficiently represented as Dictionary:
      {[0, 3]: 1, [2, 3]: 4, [1, 0]: 2, [1, 4]: 3}

      2

3. Sử dụng các giá trị đó làm chỉ số lát cắt để tìm nạp các phần tử

   from scipy import sparse
   

   3 tương ứng

   Sparse Matrix
   0 0 0 1 0
   2 0 0 0 3
   0 0 0 4 0
   sparse matrix can be efficiently represented as Dictionary:
   {[0, 3]: 1, [2, 3]: 4, [1, 0]: 2, [1, 4]: 3}

   4

4. Việc tìm nạp các chỉ số cột tương ứng của chúng thật dễ dàng

   pip insall scipy
   

   0

Cột thưa được nén [CSC]¶

Định dạng Cột thưa được nén chỉ là sự phản ánh của định dạng Hàng thưa được nén. Ví dụ: giả sử bạn có ma trận thưa thớt sau

uncompressed = np.array[
    [[0, 0, 3, 0, 0],
     [0, 0, 0, 0, 1],
     [1, 0, 0, 2, 0],
     [0, 0, 0, 0, 0],
     [0, 0, 0, 0, 1]]
]

Để lưu trữ ma trận này ở định dạng CSC cần có ba mảng

• ______43. một mảng chứa giá trị của từng phần tử khác không
  Trong ví dụ này.

  uncompressed = np.array[
      [[0, 0, 3, 0, 0],
       [0, 0, 0, 0, 1],
       [1, 0, 0, 2, 0],
       [0, 0, 0, 0, 0],
       [0, 0, 0, 0, 1]]
  ]
  

  7
• ______45. một mảng chứa chỉ mục hàng của từng phần tử khác không
  Trong ví dụ này.

  uncompressed = np.array[
      [[0, 0, 3, 0, 0],
       [0, 0, 0, 0, 1],
       [1, 0, 0, 2, 0],
       [0, 0, 0, 0, 0],
       [0, 0, 0, 0, 1]]
  ]
  

  9
• ____47. một mảng chứa tổng số phần tử khác 0 tích lũy trên mỗi cột của ma trận, được thêm vào trước bởi 0
  Trong ví dụ này.

  matrix=[[0,0,0,1,0],
          [2,0,0,0,3],
          [0,0,0,4,0]]
  Dict={}
  print["Sparse Matrix"]
  for i in range [len[matrix]]:
       print["\n"]
       for j in range[len[matrix[i]]]:
           print[matrix[i][j],end=' ']
           if matrix[i][j]!=0:
              Dict[[i,j]]=matrix[i][j]
  print["\n\n Sparse Matrix can be efficiently represented as Dictionary :"]
  print[Dict]
  
  
  

  71

Bạn có thể xác nhận điều này trong scipy bằng cách chuyển đổi

from scipy import sparse

9 thành

matrix=[[0,0,0,1,0],
        [2,0,0,0,3],
        [0,0,0,4,0]]
Dict={}
print["Sparse Matrix"]
for i in range [len[matrix]]:
     print["\n"]
     for j in range[len[matrix[i]]]:
         print[matrix[i][j],end=' ']
         if matrix[i][j]!=0:
            Dict[[i,j]]=matrix[i][j]
print["\n\n Sparse Matrix can be efficiently represented as Dictionary :"]
print[Dict]

73 và kiểm tra các thuộc tính

from scipy import sparse

3,

from scipy import sparse

5 và

from scipy import sparse

7 của nó

pip insall scipy

2

Tại sao điều này lại hữu ích?
Việc xây dựng lại và vận hành trên các cột của ma trận này cực kỳ hiệu quả vì

from scipy import sparse

7 cung cấp một cách trực tiếp để truy cập các phần tử khác 0 của bất kỳ cột nào. Ví dụ: xem xét yêu cầu sau.

Lấy các phần tử khác 0 trong cột thứ năm của ma trận [cột chỉ số 4]

Để hoàn thành việc này,

1. Tra cứu số phần tử khác 0 xuất hiện trước chỉ số cột 4

   pip insall scipy
   

   3

2. Tra cứu số phần tử khác 0 xuất hiện trên hoặc trước chỉ số cột 4

   pip insall scipy
   

   4

3. Sử dụng các giá trị đó để tìm nạp các phần tử

   from scipy import sparse
   

   3 tương ứng

   pip insall scipy
   

   5

4. Việc tìm nạp các chỉ số hàng tương ứng của chúng thật dễ dàng

   pip insall scipy
   

   6

Sử dụng cơ bản¶

Khởi tạo¶

Có nhiều cách để khởi tạo một ma trận thưa được nén trong scipy. Có lẽ kỹ thuật phổ biến nhất là sử dụng bộ ba [hàng, col, val]. Ví dụ,

pip insall scipy

7

Việc chuyển đổi một mảng NumPy thành ma trận thưa thớt được nén cũng rất phổ biến

pip insall scipy

8

thận trọng

Điều này thường được coi là thực hành xấu. Nếu mục tiêu của bạn là xây dựng một ma trận thưa được nén để tiết kiệm bộ nhớ, thì việc xây dựng một mảng gọn gàng ở bất kỳ giai đoạn nào trong quy trình sẽ đánh bại mục đích này. Tìm kiếm một phương pháp khởi tạo tốt hơn

Truy cập dữ liệu¶

Đưa ra một ma trận thưa được nén,

matrix=[[0,0,0,1,0],
        [2,0,0,0,3],
        [0,0,0,4,0]]
Dict={}
print["Sparse Matrix"]
for i in range [len[matrix]]:
     print["\n"]
     for j in range[len[matrix[i]]]:
         print[matrix[i][j],end=' ']
         if matrix[i][j]!=0:
            Dict[[i,j]]=matrix[i][j]
print["\n\n Sparse Matrix can be efficiently represented as Dictionary :"]
print[Dict]

79,

pip insall scipy

9

Bạn có thể truy cập các hàng và cột giống như một mảng NumPy

from scipy import sparse

0

Làm cách nào để in ma trận?¶

matrix=[[0,0,0,1,0],
        [2,0,0,0,3],
        [0,0,0,4,0]]
Dict={}
print["Sparse Matrix"]
for i in range [len[matrix]]:
     print["\n"]
     for j in range[len[matrix[i]]]:
         print[matrix[i][j],end=' ']
         if matrix[i][j]!=0:
            Dict[[i,j]]=matrix[i][j]
print["\n\n Sparse Matrix can be efficiently represented as Dictionary :"]
print[Dict]

90 in các mục khác không của ma trận

from scipy import sparse

1

Nếu bạn thực sự muốn in ma trận, hãy chuyển đổi nó thành một mảng NumPy

from scipy import sparse

2

coi chừng

Điều này có thể làm nổ máy tính của bạn nếu ma trận thưa thớt rất lớn

Tiếp theo

1. Ma trận dày đặc là ma trận trong đó hầu hết các phần tử đều khác không. Tuy nhiên, scipy [và những người khác] sử dụng thuật ngữ "dày đặc" để chỉ ma trận không ở định dạng nén. ↩