UNB/ CS/ David Bremner/ teaching/ cs2613/ labs/ Lab 18

Python Background

Octave Background

Most of the octave material here is covered in the Gnu Octave Beginner's Guide, in particular

For some parts, we will refer to the GNU Octave Manual

We'll refer to the online text by Robert Beezer for linear algebra background. We can happily ignore the stuff about complex numbers.

Before the lab

One of the main features of Octave we will discuss is vectorization. To understand it, we need some background material on Linear Algebra. If you've taken a linear algebra course recently, this should be easy, otherwise you will probably need to review

If you don't have time before this lab, make sure you review any needed linear algebra before the next lab.

Counter, generators, and classes

Time
15 minutes
Activity
Demo

Recall our generator based counter from L17.

def make_counter(x):
    print('entering make_counter')
    while True:
        yield x
        print('incrementing x')
        x = x + 1

In Lab 17 we almost simulated the generator behaviour with a closure, except that next(counter) was replaced by counter(). We can provide a compatible interface by using a python class.

class Counter:
    "Simulation of generator using only __next__ and __init__"
    def __init__(self,x):
        self.x = x
        self.first = x

    def __next__(self):




        self.x = self.x + 1
        return self.x - 1

print('first')
counter = Counter(100)
print('second')
print(next(counter))
print('third')
print(next(counter))
print('last')

Fibonacci, again

Time
35 minutes
Activity
individual

Save the generator based Fibonacci example as ~/fcshome/cs2613/L18/fibgen.py

Save the following in ~/fcshome/cs2613/L18/fib.py

#!/usr/bin/python3
class Fib:
    def __init__(self,max):
        self.max = max
        self.a = 0
        self.b = 1

    def __next__(self):
        if self.a < self.max:



        else:
            raise StopIteration

Complete the definition of __next__ so that following test passes. Hint: Consider following the closure based version from Lab 17

from fib import Fib
from fibgen import fibgen

def test_fib_list():

    genfibs=list(fibgen(100))
    fibber=Fib(100)

    fibs=[]
    while True:
        try:
            fibs.append(next(fibber))
        except:
            break

    assert genfibs == fibs

We may wonder why this odd looking while loop is used to build fibs rather than some kind of list comprehension. The following simpler version currently fails:

def test_fib_list_2():
    genfibs=list(fibgen(100))
    classfibs=list(Fib(100))
    assert genfibs==classfibs

This failure is due the fact that we haven't really built an iterator yet. Remember Python works by duck-typing, which means that an iterator is something that provides the right methods.

Add the following method to your Fib class. Observe the test above now passes.

    def __iter__(self):
        return self

In addition to signal to the Python runtime that some object is an iterator, the __iter__ serves to restart the traversal of our "virtual list". If we want iterators to act as lists, then the following should really print the same list of Fibonacci numbers twice

if __name__ == '__main__':
    fibber = Fib(100)
    for n in fibber:
        print(n)
    for n in fibber:
        print(n)

Since it doesn't, let's formalize that as a test. Modify the __init__ and (especially) the __iter__ method so that following test passes.

def test_fib_restart():
    fibobj = Fib(100)
    list1 = list(fibobj)
    list2 = list(fibobj)
    assert list1 == list2

Running Octave

Fibonacci

Time
15 minutes
Activity
Demo/Group programming.

Let's dive in to programming in Octave with a straight-forward port of our Python Fibonacci function. Save the following in ~/fcshome/cs2613/labs/L19/fib.m. It turns out to be important that the function name is the same as the file name.

function ret = fib(n)
  a = 0;
  b = 1;
  for i=0:n



  endfor
endfunction

%!assert (fib(0) == 0);
%!assert (fib(1) == 1);
%!assert (fib(2) == 1);
%!assert (fib(3) == 2);
%!assert (fib(4) == 3);
%!assert (fib(5) == 5);

Fibonaccci as matrix multiplication

Time
20 minutes
Activity
individual

The following is a well known identity about the Fibonacci numbers F(i).

[ 1, 1;
  1, 0 ]^n = [ F(n+1), F(n);
               F(n),   F(n-1) ]

Since matrix exponentiation is built-in to octave, this is particularly easy to implement in octave

Save the following as ~/fcshome/cs2613/labs/L19/fibmat.m, fill in the two matrix operations needed to complete the algorithm

function ret = fibmat(n)
  A = [1,1; 1,0];


endfunction

%!assert (fibmat(0) == 0);
%!assert (fibmat(1) == 1);
%!assert (fibmat(2) == 1);
%!assert (fibmat(3) == 2);
%!assert (fibmat(4) == 3);
%!assert (fibmat(5) == 5);
%!assert (fibmat(6) == 8);
%!assert (fibmat(25) == 75025);

Performance comparison

Time
10 minutes
Activity
Demo / discussion

We can expect the second Fibonacci implementation to be faster for two distinct reasons

Of course, the first rule of performance tuning is to carefully test any proposed improvement. The following code gives an extensible way to run simple timing tests, in a manner analogous to the Python timeit method, whose name it borrows.

# Based on an example from the Julia microbenchmark suite.

function timeit(func, argument, reps)
    times = zeros(reps, 1);

    for i=1:reps
      tic(); func(argument); times(i) = toc();
    end

    times = sort(times);
    fprintf ('%s\tmedian=%.3fms mean=%.3fms total=%.3fms\n',func2str(func), median(times)*1000,
             mean(times)*1000, sum(times)*1000);
endfunction

What are the new features of octave used in this sample code?

We can either use timeit from the octave command line, or build a little utility function like

function bench
  timeit(@fib, 42, 100000)
  timeit(@fibmat, 42, 100000)
endfunction