prog2_bitvec_rozwiazania_i_iteratory

1965 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 W tym celu, wykonajmy kilka mniejszych ćwiczeń: 
       
\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,|\phantom{x}\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{x}\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|W|\phantom{x}\verb|tym|\phantom{x}\verb|celu,|\phantom{x}\verb|wykonajmy|\phantom{x}\verb|kilka|\phantom{x}\verb|mniejszych|\phantom{x}\verb|ćwiczeń:| \end{array}
%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]
# To samo przepisane w konwencji producent-konsument # Przyklad 3 def to_bit_vector(lst): global k def consume(b,state): state.append(b) if len(state)==k: r = to_int(state) #state = [] #zle ! while len(state)>0: state.pop() return [r] else: return [] def consume_finalize(state): if len(state)>0: return [to_int(state)] return [] bvec=[] state=[] for b in lst: bvec.extend(consume(b,state)) bvec.extend(consume_finalize(state)) return bvec 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]
# Jak mozna uzyc itertools? from itertools import * # Ponizej przepis ze strony http://docs.python.org/2/library/itertools.html def grouper(n, iterable, fillvalue=None): "Collect data into fixed-length chunks or blocks" # grouper(3, 'ABCDEFG', 'x') --> ABC DEF Gxx args = [iter(iterable)] * n return izip_longest(fillvalue=fillvalue, *args) # Przyklad import numpy as np v=np.random.randint(2,size=10) print v list(grouper(3,v,0)) 
       
[0 0 1 0 0 1 0 0 1 1]
[(0, 0, 1), (0, 0, 1), (0, 0, 1), (1, 0, 0)]
# Przyklad 4 def to_bit_vector(lst): global k bvec = map(to_int, grouper(k,lst,0)) return bvec 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]
 
       
# Cwiczenie 5. na konsumenta-producenta # Wypisz inwersje w ciagu liczb dodatnich # [2,7,3,5,4,3,2] -> [(7,3),(5,4),(4,3),(3,2)] def inversions(lst): def consume(b): # consume(b,state): prev = state['prev'] state['prev'] = b if prev>b: return [(prev,b)] else: return [] state=dict(prev=-1) vec=[] for b in lst: vec.extend(consume(b)) return vec print inversions([2,7,3,5,4,3,2]) print inversions(reversed(range(5))) 
       
[(7, 3), (5, 4), (4, 3), (3, 2)]
[(4, 3), (3, 2), (2, 1), (1, 0)]
 
       
############################## Iteratory ############################## 
       
def plusone(iter): for i in iter: yield i+1 #return # Niepotrzebne for i in plusone([10,20,30,40]): print i 
       
11
21
31
41
it=plusone([10,20,30,40]) print it.next() print it.next() print it.next() print it.next() print it.next() # Ooops, Exception 
       
11
21
31
41
Traceback (click to the left of this block for traceback)
...
StopIteration
def ones(n): for i in range(n): yield 1 print [i for i in ones(5)] 
       
[1, 1, 1, 1, 1]
def ktimes(iter,k): for i in iter: for _ in range(k): yield i print [i for i in ktimes([10,20,30,40],3)] 
       
[10, 10, 10, 20, 20, 20, 30, 30, 30, 40, 40, 40]
def inversions_iter(it): prev = -1 for b in it: if prev>b: yield (prev,b) prev = b print list(inversions_iter([2,7,3,5,4,3,2])) print list(inversions_iter(reversed(range(5)))) 
       
[(7, 3), (5, 4), (4, 3), (3, 2)]
[(4, 3), (3, 2), (2, 1), (1, 0)]
# Cwiczenie 6: przepisz funkcje to_bit_vector # oraz bit_vector_to_list # tak aby były iteratorami def to_bit_vector(lst): return def bit_vector_to_list(bvec): return test_my_f() 
       
[0, 1, 0, 1, 0, 1]
None
None
[0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1]
None
None
# Cwiczenie 7 # Napisz iterator po wszystkich maksymalnych rosnących podciągach zadanej listy przykl=[5,2,4,8,3,5,2] #rosnace(przykl)-> [[5],[2,4,8],[3,5],[2]] def rosnace(iter): poprz = -1 # ciag = [] # for el in iter: if poprz>el: yield ciag ciag = [] poprz = el # ciag.append(el) # yield ciag print list(rosnace(przykl)) 
       
[[5], [2, 4, 8], [3, 5], [2]]
# Cwiczenie 8: # W Ipython poczytaj opisy dostępnych iteratorów z pakietu itertools import itertools as it print dir(it) 
       
['__doc__', '__file__', '__name__', '__package__', 'chain',
'combinations', 'count', 'cycle', 'dropwhile', 'groupby', 'ifilter',
'ifilterfalse', 'imap', 'islice', 'izip', 'izip_longest',
'permutations', 'product', 'repeat', 'starmap', 'takewhile', 'tee']
help(it.ifilter) 
       
# Cwiczenie # Rozwiąż zadanie Odrzucanie out-lierów (dół strony) # http://brain.fuw.edu.pl/edu/TI:Funkcje,_struktury_danych,_modu%C5%82y # Używając itertools.ifilter napisz iterator, którego argumentem jest lista, # który zwraca listę bez outlierów. # Dla wprawy, \sigma także policz przy pomocy iteratora: # napisz pomocniczy iterator sqr_diff który zwraca ciąg (x_i-m)^2 . def sqr_diff(it1,it2): ''' iterator that returns square differences of two iterators ''' # ... return def remove_outliers(lst,k=3): ''' Iterator which removes outliers outside k*\sigma k - how many sigmas to remove? ''' # ... return 
       
def