Recitation 8a (Dec 26, 2011)
Welcome (Fall 2011/2012) » Recitation Logs (Fall 2011/2012) » Recitation 8a (Dec 26, 2011)
Table of Contents
Code examples
Example 1: Matrix class
- now using Strassen's matrix multiplication algorithm;
- new save method;
- new load static method.
import random class Matrix: """ Represents a rectangular matrix with n rows and m columns. """ def __init__(self, n,m): """ Create an n-by-m matrix of zeros. """ assert n > 0 and m > 0 self.rows = [[0]*m for i in range(n)] def dim(self): return len(self.rows), len(self.rows[0]) def __repr__(self): return "<Matrix {}>".format(self.rows) def __eq__(self, other): return isinstance(other, Matrix) and self.rows == other.rows # cell/sub-matrix access/assignment #################################### def __getitem__(self, ij): i,j = ij if isinstance(i, int) and isinstance(j, int): return self.rows[i][j] elif isinstance(i, slice) and isinstance(j, slice): M = Matrix(1,1) # to be overwritten M.rows = [row[j] for row in self.rows[i]] return M else: return NotImplemented def __setitem__(self, ij, val): i,j = ij if isinstance(i,int) and isinstance(j,int): assert isinstance(val, (int, float, complex)) self.rows[i][j] = val elif isinstance(i, slice) and isinstance(j,slice): assert isinstance(val, Matrix) n,m = val.dim() s_rows = self.rows[i] assert n == len(s_rows) and m == len(s_rows[0][j]) for s_row, v_row in zip(s_rows, val.rows): s_row[j] = v_row else: return NotImplemented # arithmetic operations ######################## def __add__(self, other): if not isinstance(other, Matrix): return NotImplemented assert self.dim() == other.dim() n,m = self.dim() M = Matrix(n,m) for i in range(n): for j in range(m): M[i,j] = self[i,j] + other[i,j] return M def __sub__(self, other): if not isinstance(other, Matrix): return NotImplemented assert self.dim() == other.dim() n,m = self.dim() M = Matrix(n,m) for i in range(n): for j in range(m): M[i,j] = self[i,j] - other[i,j] return M def __neg__(self): n,m = self.dim() return Matrix(n,m) - self def __mul__(self, other): if isinstance(other, Matrix): return self.multiply_by_matrix(other) elif isinstance(other, (int, float, complex)): return self.multiply_by_scalar(other) else: return NotImplemented __rmul__ = __mul__ def multiply_by_scalar(self, val): n,m = self.dim() M = Matrix(n,m) for i in range(n): for j in range(m): M[i,j] = self[i,j] * val return M def multiply_by_matrix_naive(self, other): assert isinstance(other, Matrix) n,m = self.dim() n2,m2 = other.dim() assert m == n2 M = Matrix(n,m2) for i in range(n): for j in range(m2): M[i,j] = sum(self[i,k] * other[k,j] for k in range(m)) return M def multiply_by_matrix_Strassen(self, other): n,m = self.dim() n2,m2 = other.dim() assert n == m == n2 == m2 # we deal with square matrices only if n==1: result = Matrix(1,1) result[0,0] = self[0,0] * other[0,0] return result else: assert n % 2 == 0 # we deal with power of two values only k = n//2 A11 = self[:k,:k] A12 = self[:k,k:] A21 = self[k:,:k] A22 = self[k:,k:] B11 = other[:k,:k] B12 = other[:k,k:] B21 = other[k:,:k] B22 = other[k:,k:] M1 = (A11 + A22)*(B11 + B22) M2 = (A21 + A22)*B11 M3 = A11*(B12 - B22) M4 = A22*(B21 - B11) M5 = (A11 + A12)*B22 M6 = (A21 - A11)*(B11 + B12) M7 = (A12 - A22)*(B21 + B22) C11 = M1 + M4 - M5 + M7 C12 = M3 + M5 C21 = M2 + M4 C22 = M1 - M2 + M3 + M6 result = Matrix(n,n) result[:k,:k] = C11 result[:k,k:] = C12 result[k:,:k] = C21 result[k:,k:] = C22 return result multiply_by_matrix = multiply_by_matrix_Strassen # Input/output ############### def save(self, filename): f = open(filename, 'w') n,m = self.dim() print(n,m, file=f) for row in self.rows: #print(" ".join(str(x) for x in row), file=f) print(*row, file=f) f.close() @staticmethod def load(filename): f = open(filename) n,m = [int(x) for x in f.readline().split()] result = Matrix(n,m) for i in range(n): line = f.readline() row = [int(x) for x in line.split()] assert len(row) == m result.rows[i] = row return result
Download (right click -> save link as "matrix.py")
Example 2: output files
stam
hello worldgoodbye
stam2.txt
hello 17
matrix.txt
3 4
-5 -2 -8 -8
-4 -5 -5 4
7 5 1 -2
Interpreter session log
Python 3.2 (r32:88445, Feb 20 2011, 21:29:02) [MSC v.1500 32 bit (Intel)] on win32
Type "copyright", "credits" or "license()" for more information.
>>> ================================ RESTART ================================
>>>
>>> def random_matrix(n, m):
M = Matrix(n, m)
for i in range(n):
for j in range(m):
M[i,j] = random.randint(-10,10)
return M
>>> impotr random
SyntaxError: invalid syntax
>>>
>>> import random
>>> M1 = random_matrix(8,8)
Traceback (most recent call last):
File "<pyshell#10>", line 1, in <module>
M1 = random_matrix(8,8)
File "<pyshell#6>", line 2, in random_matrix
M = Matrix(n, m)
File "C:\Documents and Settings\ranihod\Desktop\matrix.py", line 12, in __init__
assert n > 0 and m > 0
NameError: global name 'gt' is not defined
>>> ================================ RESTART ================================
>>>
>>> import random
>>> def random_matrix(n, m):
M = Matrix(n, m)
for i in range(n):
for j in range(m):
M[i,j] = random.randint(-10,10)
return M
>>> M1 = random_matrix(8,8)
>>> M2 = random_matrix(8,8)
>>> M1.multiply_by_matrix_naive(M2)
<Matrix [[27, 45, -84, -20, -50, -40, 32, 86], [-246, -151, 6, 211, 21, -31, 56, 170], [53, -6, 79, 17, -41, 28, -196, 140], [-27, 72, -110, -79, 58, -141, 108, 133], [166, 87, 78, -40, -76, -23, -200, 113], [-244, -58, -80, 122, 48, -125, 74, 200], [117, 55, 83, -4, -55, 51, -212, 12], [182, 79, 88, 13, 13, 33, -225, -71]]>
>>> M1 * M2
<Matrix [[27, 45, -84, -20, -50, -40, 32, 86], [-246, -151, 6, 211, 21, -31, 56, 170], [53, -6, 79, 17, -41, 28, -196, 140], [-27, 72, -110, -79, 58, -141, 108, 133], [166, 87, 78, -40, -76, -23, -200, 113], [-244, -58, -80, 122, 48, -125, 74, 200], [117, 55, 83, -4, -55, 51, -212, 12], [182, 79, 88, 13, 13, 33, -225, -71]]>
>>> M1 * M2 == M1.multiply_by_matrix_naive(M2)
True
>>> open(r'C:\Documents and Settings\ranihod\Desktop\matrix.py')
<_io.TextIOWrapper name='C:\\Documents and Settings\\ranihod\\Desktop\\matrix.py' mode='r' encoding='cp1255'>
>>> f = _
>>> f.readline()
'ן»¿import random\n'
>>> f.readline()
'\n'
>>> f.readline()
'class Matrix:\n'
>>> f.read(4)
' '
>>> f.read(4)
'"""\n'
>>> x = f.read(10**6)
>>> len(x)
4387
>>> f.read(10)
''
>>> f.readline()
''
>>> f=open(r'C:\Documents and Settings\ranihod\Desktop\matrix.py')
>>> f.readline()
'ן»¿import random\n'
>>> f=open(r'C:\Documents and Settings\ranihod\Desktop\matrix.py')
>>> f.readline()
'ן»¿import random\n'
>>> f.write('fbfbfsb')
Traceback (most recent call last):
File "<pyshell#34>", line 1, in <module>
f.write('fbfbfsb')
io.UnsupportedOperation: not writable
>>> g = open(r'C:\Documents and Settings\ranihod\Desktop\stam', 'w')
>>> g.write('hello world')
11
>>> g.write('goodbye')
7
>>> g.close()
>>> g = open(r'C:\Documents and Settings\ranihod\Desktop\stam2.txt', 'w')
>>> print("hello", 17, file=g)
>>> g.flush()
>>> type(g)
<class '_io.TextIOWrapper'>
>>> g
<_io.TextIOWrapper name='C:\\Documents and Settings\\ranihod\\Desktop\\stam2.txt' mode='w' encoding='cp1255'>
>>> f
<_io.TextIOWrapper name='C:\\Documents and Settings\\ranihod\\Desktop\\matrix.py' mode='r' encoding='cp1255'>
>>> x=[1,4,5,6]
>>> print(x)
[1, 4, 5, 6]
>>> print(1,4,5,6)
1 4 5 6
>>> print(*x)
1 4 5 6
>>> print((1,4,5,6))
(1, 4, 5, 6)
>>> x=[1,4,(6,7),6]
>>> print(*x)
1 4 (6, 7) 6
>>> print(*x, sep='meow')
1meow4meow(6, 7)meow6
>>> ================================ RESTART ================================
>>>
>>> def random_matrix(n, m):
M = Matrix(n, m)
for i in range(n):
for j in range(m):
M[i,j] = random.randint(-10,10)
return M
>>> random_matrix(3,4)
<Matrix [[-5, -2, -8, -8], [-4, -5, -5, 4], [7, 5, 1, -2]]>
>>> M=_
>>> M.save('matrix.txt')
>>> import os
>>> os.getcwd()
'C:\\Documents and Settings\\ranihod\\Desktop'
>>> [int(x) for x in ["10","20"]]
[10, 20]
>>> n,m=[int(x) for x in ["10","20"]]
>>> n
10
>>> m
20
>>> ================================ RESTART ================================
>>>
>>> M
Traceback (most recent call last):
File "<pyshell#64>", line 1, in <module>
M
NameError: name 'M' is not defined
>>> load_matrix('matrix.txt')
<Matrix [[-5, -2, -8, -8], [-4, -5, -5, 4], [7, 5, 1, -2]]>
>>> M = _
>>> type(M)
<class '__main__.Matrix'>
>>> Matrix.load('matrix.txt')
Traceback (most recent call last):
File "<pyshell#68>", line 1, in <module>
Matrix.load('matrix.txt')
AttributeError: type object 'Matrix' has no attribute 'load'
>>> Matrix.dim(M)
(3, 4)
>>> ================================ RESTART ================================
>>>
>>> Matrix.load('matrix.txt')
<Matrix [[-5, -2, -8, -8], [-4, -5, -5, 4], [7, 5, 1, -2]]>
>>> Matrix.load
<function load at 0x014EB198>
>>> Matrix.dim
<function dim at 0x014E4DB0>
>>> type(Matrix.dim)
<class 'function'>
>>> type(Matrix.load)
<class 'function'>
>>> M=Matrix.load('matrix.txt')
>>> M.dim
<bound method Matrix.dim of <Matrix [[-5, -2, -8, -8], [-4, -5, -5, 4], [7, 5, 1, -2]]>>
>>> M.load
<function load at 0x014EB198>
>>>