# pypy / pypy / tool / algo / sparsemat.py

 ``` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74``` ```from __future__ import division EPSILON = 1E-12 class SparseMatrix: def __init__(self, height): self.lines = [{} for row in range(height)] def __getitem__(self, (row, col)): return self.lines[row].get(col, 0) def __setitem__(self, (row, col), value): if abs(value) > EPSILON: self.lines[row][col] = value else: try: del self.lines[row][col] except KeyError: pass def copy(self): m = SparseMatrix(len(self.lines)) for line1, line2 in zip(self.lines, m.lines): line2.update(line1) return m def solve(self, vector): """Solves 'self * [x1...xn] == vector'; returns the list [x1...xn]. Raises ValueError if no solution or indeterminate. """ vector = list(vector) lines = [line.copy() for line in self.lines] columns = [{} for i in range(len(vector))] for i, line in enumerate(lines): for j, a in line.items(): columns[j][i] = a lines_left = dict.fromkeys(range(len(self.lines))) nrows = [] for ncol in range(len(vector)): currentcolumn = columns[ncol] lst = [(abs(a), i) for (i, a) in currentcolumn.items() if i in lines_left] _, nrow = max(lst) # ValueError -> no solution nrows.append(nrow) del lines_left[nrow] line1 = lines[nrow] maxa = line1[ncol] for _, i in lst: if i != nrow: line2 = lines[i] a = line2.pop(ncol) #del currentcolumn[i] -- but currentcolumn no longer used factor = a / maxa vector[i] -= factor*vector[nrow] for col in line1: if col > ncol: value = line2.get(col, 0) - factor*line1[col] if abs(value) > EPSILON: line2[col] = columns[col][i] = value else: line2.pop(col, 0) columns[col].pop(i, 0) solution = [None] * len(vector) for i in range(len(vector)-1, -1, -1): row = nrows[i] line = lines[row] total = vector[row] for j, a in line.items(): if j != i: total -= a * solution[j] solution[i] = total / line[i] return solution ```
Tip: Filter by directory path e.g. /media app.js to search for public/media/app.js.
Tip: Use camelCasing e.g. ProjME to search for ProjectModifiedEvent.java.
Tip: Filter by extension type e.g. /repo .js to search for all .js files in the /repo directory.
Tip: Separate your search with spaces e.g. /ssh pom.xml to search for src/ssh/pom.xml.
Tip: Use ↑ and ↓ arrow keys to navigate and return to view the file.
Tip: You can also navigate files with Ctrl+j (next) and Ctrl+k (previous) and view the file with Ctrl+o.
Tip: You can also navigate files with Alt+j (next) and Alt+k (previous) and view the file with Alt+o.