Python Background
Octave Background
Most of the octave material here is covered in the Gnu Octave Beginner's Guide, in particular
- GOBG Chapter 2
- GOBG Chapter 4
- GOBG Chapter 5
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
Vector Operations, particularly
- Addition
- Subtraction
- Scalar multiplication
-
- Addition
- Subtraction
- Scalar multiplication
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')
- Observe that the implimentation is closer to the closure based version of L17 than the original generator version.
- It's a recurring theme in Python to have some
syntax/builtin-function tied to defining a special
__foo__
method
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
There is a GUI accessible from
Activities -> GNU Octave
, or by running from the command line% octave --gui
There is also a REPL accessible from the command line by running
% octave
To sanity check your octave setup, run the following plots
>> surf(peaks) >> countourf(peaks)
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);
We can avoid the need for a temporary variable by calling
deal
function, but it's not clear that would be faster. If you have time, try it.Note the
%! assert
. These are unit tests that can be run with>> test fib
The syntax for
%!assert
is a bit fussy, in particular the parentheses are needed around the logical test.
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
It's possible to compute matrix powers rather quickly (
O(log n)
comparedO(n)
), and since the fast algorithm is also simple, we can hope that octave implements it. Since the source to octave is available, we could actually check this.Octave is interpreted, so loops are generally slower than matrix operations (which can be done in a single call to an optimized library). This general strategy is called vectorization, and applies in a variety of languages, usually for numerical computations. In particular most PC hardware supports some kind of hardware vector facility.
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?
tic
,toc
, from GOBG8, GO 36.1- Function Handles
- what else?
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