prog2_bitvec_klasy

2070 days ago by macieksk

%jsmath Zadanie 1 Napisz w Python-ie klasę macierzy binarnych kodowanych bitowo: class BitMatrix W klasie BitMatrix macierz zapisana jest jako kolekcja (np. lista) wierszy. Każdy wiersz to wektor zero-jedynkowy kodowany bitowo, czyli kolekcja (lista) obiektow typu "int". Klasa BitMatrix powinna posiadać operacje pozwalające na: tworzenie macierzy, transformowanie do innych różnych reprezentacji macierzy, transponowanie macierzy, mnożenie macierzy, wykonanie operacji znalezienia silnie spójnych składowych grafu reprezentowanego przez macierz poprzez obliczenie M^N Wykorzystaj poprzednio napisane funkcje "to_bit_vector","bit_vector_to_list" i stwórz klasę o następującym interfejsie: 
       
\newcommand{\Bold}[1]{\mathbf{#1}}\begin{array}{l} \verb|Zadanie|\phantom{x}\verb|1|\\ \phantom{x}\\ \verb|Napisz|\phantom{x}\verb|w|\phantom{x}\verb|Python-ie|\phantom{x}\verb|klasę|\phantom{x}\verb|macierzy|\phantom{x}\verb|binarnych|\phantom{x}\verb|kodowanych|\phantom{x}\verb|bitowo:|\phantom{x}\verb|class|\phantom{x}\verb|BitMatrix|\\ \phantom{x}\\ \verb|W|\phantom{x}\verb|klasie|\phantom{x}\verb|BitMatrix|\phantom{x}\verb|macierz|\phantom{x}\verb|zapisana|\phantom{x}\verb|jest|\phantom{x}\verb|jako|\phantom{x}\verb|kolekcja|\phantom{x}\verb|(np.|\phantom{x}\verb|lista)|\phantom{x}\verb|wierszy.|\\ \verb|Każdy|\phantom{x}\verb|wiersz|\phantom{x}\verb|to|\phantom{x}\verb|wektor|\phantom{x}\verb|zero-jedynkowy|\phantom{x}\verb|kodowany|\phantom{x}\verb|bitowo,|\\ \verb|czyli|\phantom{x}\verb|kolekcja|\phantom{x}\verb|(lista)|\phantom{x}\verb|obiektow|\phantom{x}\verb|typu|\phantom{x}\verb|"int".|\\ \phantom{x}\\ \verb|Klasa|\phantom{x}\verb|BitMatrix|\phantom{x}\verb|powinna|\phantom{x}\verb|posiadać|\phantom{x}\verb|operacje|\phantom{x}\verb|pozwalające|\phantom{x}\verb|na:|\\ \phantom{xxxx}\verb|tworzenie|\phantom{x}\verb|macierzy,|\\ \phantom{xxxx}\verb|transformowanie|\phantom{x}\verb|do|\phantom{x}\verb|innych|\phantom{x}\verb|różnych|\phantom{x}\verb|reprezentacji|\phantom{x}\verb|macierzy,|\\ \phantom{xxxx}\verb|transponowanie|\phantom{x}\verb|macierzy,|\\ \phantom{xxxx}\verb|mnożenie|\phantom{x}\verb|macierzy,|\\ \phantom{xxxx}\verb|wykonanie|\phantom{x}\verb|operacji|\phantom{x}\verb|znalezienia|\phantom{x}\verb|silnie|\phantom{x}\verb|spójnych|\phantom{x}\verb|składowych|\\ \phantom{xxxxxxx}\verb|grafu|\phantom{x}\verb|reprezentowanego|\phantom{x}\verb|przez|\phantom{x}\verb|macierz|\phantom{x}\verb|poprzez|\phantom{x}\verb|obliczenie|\phantom{xx}\verb|M^N|\\ \phantom{x}\\ \phantom{x}\\ \verb|Wykorzystaj|\phantom{x}\verb|poprzednio|\phantom{x}\verb|napisane|\phantom{x}\verb|funkcje|\phantom{x}\verb|"to_bit_vector","bit_vector_to_list"|\\ \verb|i|\phantom{x}\verb|stwórz|\phantom{x}\verb|klasę|\phantom{x}\verb|o|\phantom{x}\verb|następującym|\phantom{x}\verb|interfejsie:| \end{array}
import numpy as np dir(np.ndarray) 
       
['T', '__abs__', '__add__', '__and__', '__array__',
'__array_finalize__', '__array_interface__', '__array_prepare__',
'__array_priority__', '__array_struct__', '__array_wrap__',
'__class__', '__contains__', '__copy__', '__deepcopy__',
'__delattr__', '__delitem__', '__delslice__', '__div__',
'__divmod__', '__doc__', '__eq__', '__float__', '__floordiv__',
'__format__', '__ge__', '__getattribute__', '__getitem__',
'__getslice__', '__gt__', '__hash__', '__hex__', '__iadd__',
'__iand__', '__idiv__', '__ifloordiv__', '__ilshift__', '__imod__',
'__imul__', '__index__', '__init__', '__int__', '__invert__',
'__ior__', '__ipow__', '__irshift__', '__isub__', '__iter__',
'__itruediv__', '__ixor__', '__le__', '__len__', '__long__',
'__lshift__', '__lt__', '__mod__', '__mul__', '__ne__', '__neg__',
'__new__', '__nonzero__', '__oct__', '__or__', '__pos__', '__pow__',
'__radd__', '__rand__', '__rdiv__', '__rdivmod__', '__reduce__',
'__reduce_ex__', '__repr__', '__rfloordiv__', '__rlshift__',
'__rmod__', '__rmul__', '__ror__', '__rpow__', '__rrshift__',
'__rshift__', '__rsub__', '__rtruediv__', '__rxor__', '__setattr__',
'__setitem__', '__setslice__', '__setstate__', '__sizeof__',
'__str__', '__sub__', '__subclasshook__', '__truediv__', '__xor__',
'all', 'any', 'argmax', 'argmin', 'argsort', 'astype', 'base',
'byteswap', 'choose', 'clip', 'compress', 'conj', 'conjugate',
'copy', 'ctypes', 'cumprod', 'cumsum', 'data', 'diagonal', 'dot',
'dtype', 'dump', 'dumps', 'fill', 'flags', 'flat', 'flatten',
'getfield', 'imag', 'item', 'itemset', 'itemsize', 'max', 'mean',
'min', 'nbytes', 'ndim', 'newbyteorder', 'nonzero', 'prod', 'ptp',
'put', 'ravel', 'real', 'repeat', 'reshape', 'resize', 'round',
'searchsorted', 'setfield', 'setflags', 'shape', 'size', 'sort',
'squeeze', 'std', 'strides', 'sum', 'swapaxes', 'take', 'tofile',
'tolist', 'tostring', 'trace', 'transpose', 'var', 'view']
import numpy as np class BitVector(np.ndarray): _int_type = np.int32 _k = 10 # Number of bits used @staticmethod def bvector(lst): ''' Statyczna metoda uzywana do tworzenia nowych BitVectorow ''' lst = list(lst) bv = BitVector((len(lst),)) for i in xrange(len(lst)): bv[i]=lst[i] return bv def __init__(self, shape, **dargs): ''' Interfejs __init__ powinien byc zgodny z tym z nadklasy "ndarray". Tworzymy pusty wektor (macierz 1-wymiarową) kodujący bit-wektorowo przy pomocy _k bitow w każdym elemencie int ''' self._length = shape[0] # Musimy policzyc dlugosc wektora kodujacego q,r = divmod(self._length, BitVector._k) int_shape = q+1 if r>0 else q dargs.update(dtype=BitVector._int_type) #Tworzymy 1-wymiarowy wektor np.ndarray.__init__(self, (int_shape,), **dargs) def __len__(self): return self._length def __setitem__(self, i, b): ''' x.__setitem__(i, b) <==> x[i]=b ''' if not b in [0,1]: raise Exception("BitVector can assign only 0,1") if not (0<=i<self._length): raise Exception("Index out of bounds") q,r = divmod(i, BitVector._k) bits = BitVector._int_type(np.ndarray.__getitem__(self, q)) bb=b<<r b1=1<<r newbits = (bits&(~b1))|bb # sets the r-th bit to b np.ndarray.__setitem__(self, q, newbits) def __getitem__(self, i): ''' x.__getitem__(i) <==> x[i] ''' q,r = divmod(i, BitVector._k) return BitVector._int_type(np.ndarray.__getitem__(self, q))>>r&1 def __iter__(self): for i in xrange(self._length): yield self[i] def tolist(self): return list(b for b in self) def __str__(self): return str(list(self)) def __repr__(self): return "BitVector("+str(self)+")" def __and__(self,bv): if isinstance(bv,int) and bv in [0,1]: if bv ==0 : return BitVector.bvector([0]*len(self)) else: return BitVector.bvector(list(self)) elif isinstance(bv,BitVector) and len(bv)==len(self): return BitVector.bvector([a&b for a,b in zip(self,bv)]) else: raise Exception("Cannot apply & to BitVector and "+str(bv)) def __mul__(self,bv): return self.__and__(bv) def __or__(self,bv): if isinstance(bv,int) and bv in [0,1]: if bv==1 : return BitVector.bvector([1]*len(self)) else: return BitVector.bvector(list(self)) elif isinstance(bv,BitVector) and len(bv)==len(self): return BitVector.bvector([a|b for a,b in zip(self,bv)]) else: raise Exception("Cannot apply | to BitVector and "+str(bv)) def __add__(self,bv): return self.__or__(bv) b=BitVector.bvector([1,0,1,0,1,1]) 
       
b=BitVector.bvector([1,0,1,0,1,1]) print b print len(b) b[1]=1 b 
       
[1, 0, 1, 0, 1, 1]
6
BitVector([1, 1, 1, 0, 1, 1])
       
(6,)
b & BitVector.bvector([0,0,0,1,0,0]) 
       
BitVector([0, 0, 0, 0, 0, 0])
b & BitVector.bvector([1,0,0,0,0,0]) 
       
BitVector([1, 0, 0, 0, 0, 0])
print b * 1 print b * 0 
       
[1, 1, 1, 0, 1, 1]
[0, 0, 0, 0, 0, 0]
b^b 
       
Traceback (click to the left of this block for traceback)
...
TypeError: unsupported operand type(s) for ^: 'float' and 'float'
# Poniżej interfejs z listą metod które trzeba przeslonic. # Przeslon inne metody, zastanow sie, ktore z nich maja sens class BitMatrix(np.ndarray): @staticmethod def bmatrix(lstoflist): TODO def __init__(self, shape, **dargs): ''' Interfejs __init__ powinien byc zgodny z tym z nadklasy "ndarray". Tworzymy pusty wektor (macierz 1-wymiarową) kodujący bit-wektorowo przy pomocy _k bitow w każdym elemencie int ''' self._length = shape[0] # Musimy policzyc dlugosc wektora kodujacego q,r = divmod(self._length, BitVector._k) int_shape = q+1 if r>0 else q dargs.update(dtype=BitVector._int_type) shape[0]=int_shape #Tworzymy 2-wymiarowa macierz 1-wymiarowych BitVectorow np.ndarray.__init__(self, shape, **dargs) def __getitem__(self,i): ''' x.__getitem__(i) <==> x[i] Zwraca i-ty wiersz jako BitVector ''' def __setitem__(self,i,y): ''' x.__setitem__(i, y) <==> x[i]=y ''' def transpose(self): ''' Napisz używajac wlasnosci x[i][j]==x.T[j][i] ''' TODO def _set_T(self,*a): raise Exception("Can't assign to T") T = property(transpose,_set_T) def dot(self,bm): TODO def __mul__(self, y): ''' x.__mul__(y) <==> x*y Użyj funkcji __and__ ''' def __pow__(self, n): ''' x.__pow__(n) <==> pow(x, n) <==> x**n ''' def __getslice__(self,i, j): ''' x.__getslice__(i, j) <==> x[i:j] ''' def __setslice__(self,i, j): ''' x.__setslice__(i, j, y) <==> x[i:j]=y ''' def __or__(self,y): ''' x.__or__(y) <==> x|y Czy tu działa metoda z nad klasy? ''' def prod(axis=None) ''' Return the product of the array elements over the given axis In case of BitMatrix it returns either 0 or 1 ''' pass # empty instruction -- marks the end of BitMatrix definition 
       
 
       
%python # Cw 2. # Napisz funkcję to_bit_vector(lst), która dostawszy na wejściu listę 0,1 dowolnej długości, # utworzy bit_vector odpowiadający tej liście. # Niech bit_vector to będzie lista długości "n" obiektów typu int. # Każdy z tych obiektów koduje "k" bitów (k z poprzedniego ćwiczenia). # Jeśli na liście zapisanych jest N bitów, czyli N=len(lst) to jakie musi być "n"? #global k=4 def to_int(lst): w=0 for i,b in enumerate(lst): w = w | (b<<i) return w # Rozwiazanie cwiczenia 6 (poniżej) na iteratory def to_bit_vector(lst): global k part=[] for b in lst: part.append(b) if len(part)==k: yield to_int(part) part=[] if len(part)>0: yield to_int(part) # Cw 2.1 # Napisz funkcję from_bit_vector(lst), ktora dostawszy na wejsciu bit_vector utworzy liste 0-1-kową def bit_vector_to_list(bvec): global k for n in bvec: for i in range(k): yield ((n>>i) & 1) # Przetestuj swoje funkcje. # Czy ich zlozenie jest idempotentne? def test_my_f(): v = [ (i%2) for i in range(6) ] print v print list(to_bit_vector(v)) print list(bit_vector_to_list(to_bit_vector(v) )) v=[ (i%2) for i in range(12) ] print v print list(to_bit_vector(v)) print list(bit_vector_to_list(to_bit_vector(v) )) return test_my_f() 
       
[0, 1, 0, 1, 0, 1]
[10, 2]
[0, 1, 0, 1, 0, 1, 0, 0]
[0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1]
[10, 10, 10]
[0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1]
 
       
%python # Cw 3 # Napisz funkcję, ktora dostawszy macierz w formacie array (numpy), wygeneruje listę wierszy które są bit_vector-ami # Przypomnienie: # Macierz numpy.array można stworzyć z listy list import numpy as np ar = np.array( [ [ int(i != j) for j in xrange(5)] for i in xrange(4)] ) print(ar) # Dostęp do elementów macierzy numpy: ar[0][1]==ar[0,1]==1 
       
[[0 1 1 1 1]
 [1 0 1 1 1]
 [1 1 0 1 1]
 [1 1 1 0 1]]
True
%python # Cw 5. # Wykonaj wizualizacje binarnej macierzy bit_vectorów import matplotlib.pyplot as plt ### Zmien opcje w.plt imshow na odpowiadające Tobie bardziej. p=plt.imshow(ar,interpolation='nearest') plt.savefig('matrixmap.png') #Tak wyswietlamy obrazki na sage # plt.show() # To wykonujemy lokalnie z konsoli # Sprawdź "obrazkowo" poprawność funkcji z 3 i 4 def visualize_bitmatrix(bm): return 
       
%python # Cw 5. # Napisz funkcję, ktora mnoży przez siebie dwie macierze bit_vector-ów. # Postaraj się użyć funkcji zip. # Wskazówka: Jak otrzymać element (M1*M2)[i,j] tylko przy pomocy operacji logicznych? # Wskazówka 2: # Cw 6. # Napisz funkcję, ktora transponuje macierz bit_vector-ów (pozostając w reprezentacji "lista wierszy" zamienia M(i,j) na M(j,i)). # Rozważ następujące metody wykonania zadania: # a) wykorzystanie numpy # b) wykorzystanie transponowania w pythonie: http://www.ehow.com/how_8448012_transpose-list-lists-python.html # c) napisanie funcje pomocniczą: def getitem_bv(bv,x,y): ''' Returns element (x,y) from a bit_vector. ''' return elem 
       
%python N=100 k=10 ar = np.array( [ [ (i==j or i==j+k or i==j-k) for j in xrange(N)] for i in xrange(N)] ) p=plt.imshow(ar,interpolation='nearest') plt.savefig('matrixmap.png') # Cw 8. # Wykorzystując mnożenie macierzy bit_vector-ów napisz funkcję, która policzy spójne składowe grafu reprezentowanego przez powyższą binarną symetryczną macierz. # Wskazówka: Do policzenia różnych składowych użyj typu "set", # ale pamiętaj, że nie można wrzucać do niego list tylko tuple. # tuple(lst) konwertuję listę do tuple. def connected_components(bv_matrix): return cc