sparse_matrix.py

class SparseVector:
	def __init__(self, values, indexes, length):
		self.values = values
		self.indexes = indexes
		self.length = length

	def items(self):
		indexes = enumerate(self.indexes)
		i, index = next(indexes, (-1, -1))
		for j in range(self.length):
			if index == j:
				yield self.values[i]
				i, index = next(indexes, (-1, -1))
			else:
				yield 0

	def __getitem__(self, key):
		for i, index in enumerate(self.indexes):
			if index == key:
				return self.values[i]
			if key < index:
				break
		return 0

	def __str__(self):
		return f'[{", ".join(str(i) for i in self.items())}]'


class SparseMatrix:
	def __init__(self, data):
		self.width = len(data[0])
		self.v, self.col_index, self.row_index = self.sparsify(data)

	def sparsify(self, data):
		v, col_index, row_index = [], [], [0]
		for row in data:
			for i, field in enumerate(row):
				if field != 0:
					v.append(field)
					col_index.append(i)
			row_index.append(len(v))
		return v, col_index, row_index

	@property
	def height(self):
		return len(self.row_index) - 1

	def __len__(self):
		return self.width * self.height
	
	@property
	def zeros(self):
		return len(self) - self.nonzeros

	@property
	def nonzeros(self):
		return len(self.v)

	@property
	def sparsity(self):
		return self.zeros / len(self)

	def __getitem__(self, key):
		row_start = self.row_index[key]
		row_end = self.row_index[key + 1]
		return SparseVector(
			self.v[row_start:row_end],
			self.col_index[row_start:row_end],
			self.width
		)

	def rows(self):
		yield from (self[i] for i in range(self.height))

	def __str__(self):
		return '\n'.join(str(i) for i in self.rows())


m = SparseMatrix([
	[0, 0, 0, 0, 0, 0, 1],
	[2, 3, 0, 0, 4, 0, 0],
	[0, 0, 5, 0, 6, 7, 0],
	[0, 8, 0, 0, 0, 0, 0],
	[0, 0, 0, 0, 0, 0, 0],
	[0, 0, 0, 9, 0, 0, 0]
])
print(m)