python数据结构学习笔记-2016-10-22-03-稀疏矩阵

        4.5 应用：稀疏矩阵

        稀疏矩阵(Sparse Matrix)：一个矩阵中大部分元素都是零元素的矩阵(m × n)，即其非零元素个数k << m × n。

        与稀疏矩阵相反的是稠密矩阵。

        如果采用二维数组来实现稀疏矩阵，就意味着大部分的内存都会用来储存零元素，这就会造成内存的极大浪费，相关操作也会变得低效(?)。

        基于此，本节来考虑使用python列表来实现稀疏矩阵。稀疏矩阵中的每一个非零元素都以储存类实例存在，其属性包括所在行、所在列以及相应值，而python列表的每一项就是指向储存类实例的引用。

        4.1.2 基于列表的实现

#-*-coding: utf-8-*-

# 使用列表实现稀疏矩阵

class SparseMatrix(object):
    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 __getitem__(self, ndxTuple):
        ndx = self._findPosition(ndxTuple[0], ndxTuple[1])
        if ndx is not None:
            return self._elementList[ndx].value
        else:
            return 0

    def __setitem__(self, ndxTuple, scalar):
        ndx = self._findPosition(ndxTuple[0], ndxTuple[1])
        if ndx is not None: # 当指定索引是非零元素时
            if scalar != 0.0: # 新传入的值不是0，直接赋值
                self._elementList[ndx].value = scalar
            else: # 新传入的值为0时，只需从列表中删除这一项，即表明指定索引的值是0
                self._elementList.pop(ndx)
        else: # 当指定索引是0时
            if scalar != 0.0 # 传入值非零，即在底层列表中添加一项即可
                element = _MatrixElement(ndxTuple[0], ndxTuple[1], scalar)
                self._elementList.append(element)

    # 数乘运算
    def scaleBy(self, scalar):
        for element in self._elementList:
            element.value *= scalar

    # 矩阵加法
    def __add__(self, other):
        assert other.numRows() == self.numRows() and other.numCols() == self.numCols(), "Matrix sizes not compatible for the add operation."
        newMatrix = SparseMatrix(self.numRows(), self.numCols())
        # 将self中的所有非零项复制到newMatrix中
        for element in self._elementList:
            dupElement = _MatrixElement(element.row, element.col, element.value)
            newMatrix._elementList.append(dupElement)
        # 将other中的所有非零项加到newMatrix中
        for element in other._elementList:
            newMatrix[element.row, element.col] += element.value
        return newMatrix

    # 矩阵减法
    def __sub__(self, other):
        pass

    # 矩阵乘法
    def __mul__(self, other):
        pass

    # 辅助方法
    def _findPosition(self, row, col):
        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

# 储存类，储存非零元素的值，以及其在矩阵中的位置
class _MatrixElement(object):
    def __init__(self, row, col, value):
        self.row = row
        self.col = col
        self.value = value
           

        辅助方法_findPosition()，是将稀疏矩阵索引与列表索引一一对应起来。由于列表储存的实例对象中，已包含该非零项所在索引，所以稀疏矩阵的所有非零元素在列表中并不是按照特定顺序排列的。

        值得注意的是，在修改稀疏矩阵的值时，会出现以下四种情况：

• 原值非零，新值非零；
• 原值非零，新值是零；
• 原值是零，新值非零；
• 原值是零，新值是零。

        这四种情况在程序中得到了分别处理。

        还要值得注意的是稀疏矩阵的加法运算，程序中首先是创建新的系数矩阵，再将原有的稀疏矩阵所有非零项复制到新的稀疏矩阵中，再将另一个稀疏矩阵中的非零项加进来，最后一步依赖于__gettitem__()和__setitem__()的准确实现。

        4.5.2 效率分析

操作	矩阵	稀疏矩阵
构造器	O(n²)	O(1)
s.numRows()	O(1)	O(1)
s.numCols()	O(1)	O(1)
s.scaleBy(x)	O(n²)	O(k)
x = s[i, j]	O(1)	O(k)
s[i, j] = x	O(1)	O(k)
r = s + t	O(n²)	O(k²)

       假设矩阵是n × n，稀疏矩阵含有k个非零元素，_findPosition()的执行时间是O(k)。__gettitem__()和__setitem__()都调用了_findPosition()，所以执行时间都是O(k)，比起矩阵来说要慢。

       但是在构造器方面，矩阵是O(n²)，因为调用了clear()，而clear()中含有一个嵌套循环，而稀疏矩阵只是构造了一个空列表。

       数乘运算方面，矩阵是每一个元素都乘以相应的数值，需要遍历每一个元素，所以是O(n²)，而稀疏矩阵只需将列表中每一个值乘以给定的数值即可，因此是O(k)。

       在加法上，矩阵需要遍历每一个元素，并与对应元素相加，时间是O(n²)，而在稀疏矩阵中，复制所有项需要O(k)，在第二个循环中，要注意newMatrix[element.row, element.col]本身就需要O(k)，这一操作又要循环k次，所以时间是O(k) + O(k²) = O(k²)。两者效率的高低要取决于k。