Hướng dẫn sparse matrix python without numpy - Python ma trận thưa thớt không có numpy

Tôi mới vào lập trình và lần đầu tiên tôi sử dụng stackoverflow vì vậy xin chào mọi người! Vì vậy, đây là lý do tại sao tôi hỏi điều này: Tôi đang cố gắng nhân hai ma trận thưa thớt mà không có chức năng Numpy hoặc các chức năng khác có thể giúp tôi từ các thư viện Python. Tôi đang sử dụng một danh sách làm cấu trúc dữ liệu để lưu trữ các phần tử không phải là không. Mỗi phần tử không phải là một lớp có thuộc tính hàng, col và giá trị. Danh sách chỉ chứa những trường hợp của lớp _MatrixEuity. Tôi muốn thực hiện tính toán này không phải là sự phức tạp của O (n^3), vì không có ý nghĩa gì khi đi qua từng dòng của cả ma trận và làm toán sau vì hầu hết các phần tử là 0. Đây là đoạn mã Tôi đã viết cho đến nay:

 class _MatrixElement:
      def __init__(self, row ,col, value):
          self.row = row
          self.col = col
          self.value = value

 class SparseMatrix:
      def __init__(self, numRows, numCols):
          self._numRows = numRows
          self._numCols = numCols
          self._elementList = list()
    
      def numRows(self):
          return self._numRows
    
      def numCols(self):
          return self._numCols

      def __setitem__(self, ndxTuple, scalar):
          ndx = self._findPosition(ndxTuple[0], ndxTuple[1])
          if ndx is not None:
              if scalar != 0.0:
                  self._elementList[ndx].value = scalar
              else:
                  self._elementList.pop(ndx)
          else:
              if scalar != 0.0:
                  element = _MatrixElement(ndxTuple[0], ndxTuple[1], scalar)
                  self._elementList.append(element)

      def __getitem__(self, row, col):
          assert row >= 0 and row < self.numRows(), "Subscript out of range"
          assert col >= 0 and col < self.numCols(), "Subscript out of range"
          ndx = self._findPosition(row, col)
          if ndx is not None:
              return self._elementList[ndx]
          else:
              raise Exception("The element is not in the matrix")

      def _findPosition(self, row, col):
          """Find the position of the non zero element in the list, using the row and col as parameters"""
          n = len(self._elementList)
          for i in range(n):
              if (row == self._elementList[i].row and
                  col == self._elementList[i].col):
                  return i
         return None

      def transpose(self):
          newTransposeMatrix = SparseMatrix(numRows=self.numCols(), numCols=self.numRows())
          for elem in self._elementList:
              tmp_row = elem.row
              elem.row = elem.col
              elem.col = tmp_row
              newTransposeMatrix._elementList.append(elem)
          return newTransposeMatrix

      def __mul__(self, otherMatrix):
          assert isinstance(otherMatrix, SparseMatrix), "Wrong matrix type"
          assert self.numCols() == otherMatrix.numRows(), "The two matrices can't be multiplied"
          transpMatrix = otherMatrix.transpose()
          sparseNewMatrix = SparseMatrix(numRows=self.numRows(), numCols=otherMatrix.numRows())
          for apos in range(len(self._elementList)):
              r = self._elementList[apos].row
              for bpos in range(len(transpMatrix._elementList)):
                   c = transpMatrix._elementList[bpos].row
                   tmpa = apos
                   tmpb = bpos
                   the_sum = 0
                   while (tmpa < len(self._elementList) and (tmpb < len(transpMatrix._elementList)) and (self._elementList[tmpa].row == r
                                                                                                  and transpMatrix._elementList[tmpb].row == c)):
                         if self._elementList[tmpa].col > transpMatrix._elementList[tmpb].col:
                               tmpa += 1
                          elif self._elementList[tmpa].col < transpMatrix._elementList[tmpb].col:
                               tmpb += 1
                          else:
                               the_sum += self._elementList[tmpa].value * transpMatrix._elementList[tmpb].value
                               tmpa += 1
                               tmpb += 1
            if the_sum != 0:
                sparseNewMatrix.add(_MatrixElement(r, c, the_sum))
         return sparseNewMatrix

Chỉnh sửa sau: Tôi đã cải thiện thuật toán của mình bằng cách sử dụng thuật toán từ WebSitelink này ở đây và sau khi tôi chạy chương trình của mình, kết quả là phần sau:

1 2 10
1 1 96
2 1 2
2 2 5
2 1 16

Trong các dòng lớn, kết quả là chính xác. Vấn đề duy nhất là tôi không thể hiểu tại sao chương trình không tổng hợp 2 1 2 với 2 1 1 16. Kết quả xuất phát từ đầu vào sau:

Row Col Val      Row Col Val
1   2   10       1   1   2
1   3   12       1   2   5
2   1   1        2   2   1
2   3   2        3   1   8

Sau khi ma trận thứ hai được chuyển đổi, chúng ta sẽ có:

Row Col Val      Row Col Val
1   2   10       1   1   2
1   3   12       1   3   8
2   1   1        2   1   5
2   3   2        2   2   1

Kết quả nên là:

1   1   96 
1   2   10 
2   1   18  
2   2   5

Tuy nhiên kết quả của tôi khác với kết quả tôi nên nhận được. Ai đó có thể giải thích tại sao số tiền đó không được thực hiện?

Nếu ai đó có thể giúp đỡ, tôi sẽ rất biết ơn! Cảm ơn bạn đã dành thời gian!

Làm thế nào để bạn tạo ra một ma trận thưa thớt trong Python?

Làm thế nào để bạn tạo một ma trận thưa thớt trong Python?

Làm thế nào để Python xử lý ma trận thưa thớt?

Làm thế nào để bạn nhân ma trận trong Python mà không bị numpy?