Multiple Assignment with Dictionaries

Combining built in function items to transform dictionary into a list of tuples, tuple assignment and for loop you can create nice code pattern for traversing the keys and values of a dictionary in a single loop. Using the code from lecture Dictionaries and Tuples.

d = {'a':10, 'b':20, 'c': 30}
l = list()
for key,val in d.items():
    print key, val
    l.append((key,val))
print "l = " + str(l)
l.sort(reverse = True)
print "List of tuples after applying sort()function"
print "l = " + str(l)

Output of previous code is given below.

a 10
c 30
b 20
l = [('a', 10), ('c', 30), ('b', 20)]
List of tuples after applying sort()function
l = [('c', 30), ('b', 20), ('a', 10)]

The for loop has two iteration variable because items returns a list of tuples and key, val is a tuple assignment that successively iterates through each of the key/value pairs in the dictionary. For each iteration through the loop, both key and value are advanced to the next key/value pair in the dictionary.

Dictionaries and Tuples

Dictionaries have a method called items that returns a list of tuples, where each tuple is a key-value pair.

d = {'a':10, 'b':20, 'c': 30}
t = d.items()
print t
[('a', 10), ('c', 30), ('b', 20)]

As you can see from previous example, the items are in no particular order. So in this example we’ve started from defining a dictionary and then using built in function itmes() transformed the dictionary in into a tuple. Since the list of tuples is a list we can apply sort function on a list of tuples. Converting a dictionary to a list of tuples is a way to output the contents of a dictionary sorted by key. 

d = {'a':10, 'b':20, 'c': 30}
t = d.items()
print "t = " + str(t)
t.sort()
print "list of tuples using sort() function"
print " t = " + str(t)

The output of previous example is given below.

t = [('a', 10), ('c', 30), ('b', 20)]
list of tuples using sort() function
t = [('a', 10), ('b', 20), ('c', 30)]

The new list is sorted in ascending order by the key value. 

Comparing Tuples

Comparison operator work with tuples and other sequences. For example let’s define two tuples.

>>> t1 = (0, 1, 2)
>>>t2 = (0, 4, 5)
>>> t1 < t2 
True 
>>>t1 > t2
False 

When we type t1 < t2 the Python starts comparing the first element from each sequence. If the first element is equal in both sequences the Python is comparing next sequence elements until it finds those elements that differ. So in first statement t1 < t2 Python starts by comparing first element of t1 and first element of t2. Since they are both equal the Python is comparing the second element of t1 (1) and t2 (4). The 1 is less than 4 so that’s True. The final comparison is the third element of t1 (2) and t2 (5) and the answer is True which means that in deed the t1 is less than t2. The second statement t1 > t2 is False because elements of tuple t1 are smaller than elements in t2. The sort function can be also applied on tuples. It sorts primarily by first element, but in the case of a tie, it sorts by second element. This feature lends itself to a pattern called DSU and DSU stands for: 

DECORATE – sequence by building a list of tuples with one or more sort key preceding the elements from the sequence, 

SORT – the list of tuples using Python built-in sort, and 

UNDECORATE – by extracting the sorted elements of the sequence. 

Try typing the following code. 

txt = "Python is a programming language that lets you work quickly  and integrate systems more effectively." 
words = txt.split()
t = list()
for word in words: 
    t.append((len(word),word))
print 't = ' + str(t)
t.sort(reverse=True)
res = list()
for length, word in t: 
    res.append(word)

print res

Output is given below.

t = [(6, 'Python'), (2, 'is'), (1, 'a'), (11, 'programming'), (8, 'language'), (4, 'that'), 

(4, 'lets'), (3, 'you'), (4, 'work'), (7, 'quickly'), (3, 'and'), (9, 'integrate'), 

(7, 'systems'), (4, 'more'), (12, 'effectively.')]
['effectively.', 'programming', 'integrate', 'language', 'systems', 'quickly', 

'Python', 'work', 'that', 'more', 'lets', 'you', 'and', 'is', 'a']

The first loop builds a list of tuples, where each tuple is preceded by its length. Sort compare the first element, length, first and only considers the second element to break ties. The keyword argument reverse = True tells sort to go in decreasing order. 

Tuple assignment

Tuples have unique syntactic features in Python programming language and that is the ability to have a tuple on the left hand side of an assignment statement. This allows you to assign more than one variable at a time when the left hand side is a sequence. In this example we have a two element list (this is a sequence) and assign the first and second elements of the list to variables x and y in a single statement. 

a = ['Python', 'language']
x,y = a 
print x 
print y 

Output of previous script is given below.

Python 
language 

Python translates the tuple assignment to be the following:

a = ['Python', 'language']
x = a[0]
y = a[1]
print x 
print y 

Output is the same as in previous example.When we use a tuple on the left hand side of the assignment statement, we omit the parentheses, but the following is an equally valid syntax: 

a = ['Python', 'language']
(x,y) = a
print x 
print y 

A particularly clever application of tuple assignment allows us to swap the values of two variables in a single statement. 

x,y = y,x

In previous example both statements are tuples, but the left side is a tuple of variables while the right side is a tuple of expressions. Each value on the right side is assigned to its respective variable on the left side. All the expressions on the right side are evaluated before any of the assignments.

The number of variables on the left and the number of values on the right have to be the same otherwise you’ll get ValueError. 

a, b = 1,2,3
Traceback (most recent call last):
  File "", line 1, in 
ValueError: too many values to unpack

Introduction to Tuples

Tuple is a sequence of values much like a list. The values stored in a tuple can be any type, and they are indexed by integers. The important difference is that tuples are immutable. Tuples are also comparable and hashable so we can sort lists of them and use tuples as key values in Python dictionaries.

Syntactically, a tuple is a comma separated list of values: 

>>> t ='a','b', 'c', 'd','e'
>>> t
('a', 'b', 'c', 'd', 'e')
>>> type(t)
< type 'tuple'>

To create a tuple with a single element, you have to include comma after final element.

>>> t1 = ('a',)
>>> print t1
('a',)
>>> type(t1)
< type 'tuple'>

Without that final comma in parenthesis the Python would treat this declaration as a string.

>>>t1 = ('a')
>>>type(t1)
< type 'str'>

Another way to create a tuple is with using the built-in function tuple. With no argument, this function will create an empty tuple.

>>>t1 = tuple()
>>>type(t1)
< type 'tuple'>

If the argument is a sequence (string, list or tuple), the result of the call to tuple is tuple with the elements of a sequence: 

>>>word = tuple("Python is awesome")
>>>print word 
('P', 'y', 't', 'h', 'o', 'n', ' ', 'i', 's', ' ', 'a', 'w', 'e', 's', 'o', 'm','e')

Because tuple is a name of constructor, you should avoid using it as a variable name. Most list operators also work on tuples. The bracket operator indexes an element: 

>>>z = ('a', 'b', 'c', 'd')
>>>print z[0]
a
>>>print z[1]
b
>>>i = 0
>>>while i < len(z):
...   print z[i]
...   i = i + 1
...
a
b
c
d

And the slice operator selects a range of elements:

>>>z[1:3]
('b', 'c')

If you try to modify one of the tuples elements the TypeError exception will occur.

>>>z[0] = 'a'
Traceback (most recent call last):
 File "<stdin>",line 1, in <module>
TypeError: 'tuple' object does not support item assignment

You can modify the elements of a tuple, but you can replace one tuple with another.

>>>z = ('Z',) + z[1:]
>>>print z
('Z', 'b', 'c', 'd')

BIG O Notation

In algorithm analysis it’s important to quantify the number of operations or steps that algorithm will require in order to find or compute solution.

For each of these steps are considered to be a basic unit of computation then the execution time for an algorithm can be express as a number of steps required to solve the problem. Good basic unit of computation for sum algorithm is to count number of assignment statements perform to compute the sum. In this function the number of assignment statements is 1 which is total = 0 plus the value of n, the number of times we perform total = total + i.

T(n) = 1 + n

Where n is the size of the problem and the T(n) is the time it takes to solve the problem of size n namely 1 + n steps. The dominant term is what in the end is used for comparison. Order of magnitude functions describes the part of T(n) that increases the fastest as value of n increases.

Order of magnitude is often called Big-O notation and is written as O(f(n)). In case of T(n) = 1 +n if n is small then the number 1 plays significant role to the final result. As n gets larger the 1 becomes  insignificant to the final result. In that case we can drop 1 an say that running time is O(n).

For example if T(n) = 10 n^3 + 2105 when n is small then 2105 plays significant role but when the n is a large number than 2105 can be  negligible.

Sometimes the performance of algorithm depends on the exact values of data rather than simply the size of the problem. For these kinds of algorithms we need to characterize their performance in terms of best case, worst case and average case performance. The worst case is when algorithm performs poorly. In most cases the algorithm performs somewhere in between these two extremes which is an average case. 

How to perform Algorithm Analisys

Let's imagine a situation where we have two programs that solve a same problem and we have to find out which one of those two is better? Before we start algorithm analysis we’ll explain the difference between program and underlying algorithm that the program represents.

Program is an algorithm that has been encoded into some programming language.

Algorithm is a generic step-by-step list of instructions for solving a problem.

So there may be many programs for the same algorithm depending on the programmer and programming language being used.

Let’s start by creating a program that calculates sum of number n.

Function sumOfn is clearly better than function James so the conclusion of analyzing those two examples of a program pay attention to readability. Write programs that are easy to read and understand.

Algorithm analysis is concerned with comparing algorithms based upon the amount of computing resources that each algorithm uses.

Compare algorithms to see which one is better because it is more efficient in its use of resources or it simply uses fewer resources. We can conclude that those two functions above seem very similar because they both use some algorithm to solve summation problem essentially.

Computing resources 

Consider amount of space or memory an algorithm requires to solve a problem. The amount of space required by problem solution is typically dictated by a problem instance itself.

Analyze and compare algorithms based on the amount of time they require to execute this is called Execution time or Running time of algorithm

To measure execution time of function sumOfn is to perform Benchmark analysis.  

Python benchmark of algorithm using time module and calculation difference between starting time and ending time.

In the time module there is a function called time, that will return current system clock time in seconds since the same starting arbitrary point.

import time 
def sum_of_n_2(n):
    start = time.time()
    total = 0
    for i in range(1, n+1):
        total = total + i 
    end = time.time()
    timedifference = end - start
    return total, timedifference

print "Sum is %d required %10.15f seconds" % sum_of_n_2(10)
print "Sum is %d required %10.15f seconds" % sum_of_n_2(100)
print "Sum is %d required %10.15f seconds" % sum_of_n_2(1000)

The output is given below
Sum is 55 required 0.000000000000000 seconds

Sum is 5050 required 0.000000000000000 seconds
Sum is 500500 required 0.000000000000000 seconds
Sum is 50005000 required 0.000000000000000 seconds
Sum is 5000050000 required 0.006999969482422 seconds
Sum is 500000500000 required 0.093000173568726 seconds
Sum is 50000005000000 required 0.992999792098999 seconds
Sum is 5000000050000000 required 10.267999887466431 seconds

The function sum_of_n_2 is the same as function used in previous example, just with timing calls embedded before and after the summation. Function returns a tuple consisting of the result and amount of time in seconds required for the calculation.

Now we will construct the function with same purpose to sum n integers. Function sum_of_n_3 takes advantage of closed equation Sum(i) = n(n+1)/2

With this function we’ll avoid using loops to calculate the sum of n integers.

def sum_of_n_3(n):
    start = time.time()
    total = (n*(n+1))/2
    end = time.time()
    timedifference = end-start
    return total, timedifference 

print "Sum is %d required %10.15f seconds" % sum_of_n_3(10)
print "Sum is %d required %10.15f seconds" % sum_of_n_3(100)
print "Sum is %d required %10.15f seconds" % sum_of_n_3(1000)
print "Sum is %d required %10.15f seconds" % sum_of_n_3(10000)
print "Sum is %d required %10.15f seconds" % sum_of_n_3(100000)
print "Sum is %d required %10.15f seconds" % sum_of_n_3(1000000)
print "Sum is %d required %10.15f seconds" % sum_of_n_3(10000000)
print "Sum is %d required %10.15f seconds" % sum_of_n_3(100000000)

After executing the code we'll get following result. 

Sum is 55 required 0.000000000000000 seconds
Sum is 5050 required 0.000000000000000 seconds
Sum is 500500 required 0.000000000000000 seconds
Sum is 50005000 required 0.000000000000000 seconds
Sum is 5000050000 required 0.000000000000000 seconds
Sum is 500000500000 required 0.000000000000000 seconds
Sum is 50000005000000 required 0.000000000000000 seconds
Sum is 5000000050000000 required 0.000000000000000 seconds

As in previous example we did the same benchmark using different values of n. As we can see time required is 0 for each case. Second they are very consistent no matter the value of n is. Function is hardly impacted by the number of integers being added.

Iterative solution seen to be doing more work since the program is being repeated. This is a reason it is taking longer. Time required for iterative solution seems to increase the value of n. We need a better way of measuring the algorithm quality because the benchmark technique is dependent on system/computer we’re using. 

What is an Algorithm ?

Algorithm is any well-defined computational procedure that takes some value, or set of values as input and produces some value, or set of values, as an output. An algorithm is thus a sequence of computational steps that transforms the input into the output. Algorithm is also a tool for solving a well-specified computational problem. The statement of the problem specifies in general terms the desired input/output relationship. The algorithm describes a specific computational procedure for achieving that input/output relationship.

Example 1 – a sorting problem. Let’s say that we have a list or sequence of unsorted numbers and our task is to sort them out into non-decreasing order. Here is how the sorting problem is defined:

• Input: a sequence of n numbers a1,a2,a3,…,an
• Output: a permutation or ordering of the input sequence such that a1’ < a2’ < a3’ < an.

Let’s define a list of unsorted numbers in Python:

>>> l1 = [3324,212,3214,45, 500,213,12,34]

>>> l1.sort()

>>> l1

[12, 34, 45, 212, 213, 500, 3214, 3324]

As you can see first we’ve defined list l1 and then we’ve used a built-in Python function sort() without any arguments. The result of sorting is what we’ve been looking for and that is an ordered list from the lowest number 12 to the highest number 3324.

Sorting is a fundamental operation in computer science, and as a result a large number of good sorting algorithms have been developed. Which algorithm is best for given application depends on:

• Number of items to be sorted
• The extent to which the items are already sorted
• Possible restrictions on the item values.
• Kind of storage device to be used such as memory, disk or other.

Algorithm is correct if, for every input it halts with the correct output. We say that the correct algorithm solves a given computation problem. Incorrect algorithm might not halt at all on some input instances, or it might halt with an answer other than the desired one. Sometimes the incorrect algorithms might be useful if their error rate can be controlled.

In English language an algorithm might be specified as computer program or hardware design but it must provide precise description of the computational procedure to be followed.

Objects and Class

It’s time to learn about core functionality of Python programming language and that is Python objects and classes. In this lesson you’ll learn how to create it and use it in your Python program. As mentioned many times before Python is an object oriented programming language just like C++ and many others. Just to clarify the difference between procedural and object oriented programming the emphasis in procedural programming is on functions while in object oriented programming the main focus are objects.

Collection of data (variables) and methods (functions) that act on those data are what make objects. We can think of a class as a sketch or prototype. Class is like a sketch of a car because it contains all the details about tires, engine, lights, seats … Based on this description a car is built and the car is an object.

So if the class is a blueprint for building a car we can conclude that we can create many objects from this class. You will find in literature that object is an instance of a class and the process of creating this object is called instantiation.

How to Create a Class? 

Now let’s start with something simple. Let’s create a simple class in Python. To define a class use the keyword class. After the class, give a name of the class and the first line after class declaration is usually used for a brief description about the class. This line (string) is called docstring and while it’s not mandatory it is usually recommended (just to know why you created this class).

class myFirstclass:

      "This line is a docstring and it usualy say something about a class"

      Pass

A class creates a new local namespace where all its attributes are defined. Attributes may be data or functions. There are special attributes that can be used and they begin with double underscore ‘__’. An example of that attribute is __doc__ and it gives us the docstring of that class.

>>> class myFirstclass: ...       "This line is a docstring and it usualy say something about a class" ...       pass ... >>> myFirstclass.__doc__

'This line is a docstring and it usualy say something about a class'

When we create a class, a new class object is created with the same name. This class object allows us to access the different attributes as well as to instantiate new objects of that class.

class mySecondclass:

    "This is my second class"

    a = 50

    def function(self):

        print('Hello')

print 'a = ' + str (mySecondclass.a)

a = 50

print mySecondclass.function

print "DOCSTRING = " + str(mySecondclass.__doc__)

DOCSTRING = This is my second class

 How to Create an Object? 

We saw that the class object could be used to access different attributes. It can also be used to create new object instances (instantation) of that class. The procedure of creating an object is similar to a function call.

obj = mySecondclass()

This command will create a new instance of an object named obj. We can access attributes of objects using the object name as prefix.

class mySecondclass:

    "This is my second class"

    a = 50

    def function(self):

        print('Hello')

obj = mySecondclass()

"

"

Self - parameter is parameter that will always be used as reference back to the object itself. The object itself is passed as first argument. So obj.function() translates to mySecondclass.func(obj). In general calling a method with a list of n arguments is equivalent to calling the corresponding function with an argument list that is created by inserting methods object before the first argument. For that reason the first argument of the function in the class must be object itself. 

Namespaces and Scope

Variable name also called identifier is simply a name given to objects. Everything in Python is an object. So name is a way to access specific object.  Let’s define a variable a and assign value of 5 (a = 5) . Here 5 is an object stored in primary memory or RAM (RAM is short for Random Access Memory) and a is the name we associate it with. We can get the address of some object through the built-in function id().

>>> a = 5

>>> print 'id(a) = ' + str(id(a))

id(a) = 8420656

Id value may be different on your computer. Besides variable a we can also check out the memory address of variable 5 .

>>> a = 5

>>> print 'id(a) = ' + str(id(a))

id(a) = 8420656

>>> print 'id(5) = ' + str(id(5))

id(5) = 8420656

As you can see they both refer to the same object. Now we will add a with 1 and then check the id() of variable a, and it’s value, and finally we’ll define new variable b and assign value of 5.

>>> a = 5

>>> print 'id(a) = ' + str(id(a))

id(a) = 8420656

>>> print 'id(5) = ' + str(id(5))

id(5) = 8420656

>>> a = a + 1

>>> print 'id(a) = ' + str(id(a))

id(a) = 8420644

>>> print 'id(6) = ' + str(id(6))

id(6) = 8420644

>>> b = 5

>>> print 'id(b) = ' + str(id(b))

id(b) = 8420656

First we’ve created object 5 and the name a is associated with it, when we add one to variable a, then a new object 6 is created and now a associates with this object. Id(a) and id(6) have the same value. When we created object 5 and assign value of b to it and then check it’s id. As you can see it has the same value as the number 5.

This is efficient as Python doesn’t have to create a new duplicate object. This property makes Python very powerful so name could refer to any type of object.

>>> a = 5

>>> print 'id(a) = ' + str(id(a))

id(a) = 8420656

>>> a = 'Hello World!'

>>> print 'id(a) = ' + str(id(a))

id(a) = 38299392

>>> a = [1, 2, 3, 4, 5, 6]

>>> print 'id(a) = ' + str(id(a))

id(a) = 38366864

Three different types of objects have been assign to variable a and each time the id value was different, because the data is temporarily stored on different memory address.

Functions are also objects, so the name of the function can refer to them as well. Now we’ll define a function call printHello(). From the name of the function you can guess what the function does.

>>> def printHello():

...     print 'Hello'

...

>>> a = printHello()

Hello

Our name a can refer to a function ad we can call the function through it, pretty neat. 

What is a namespace?

Now that you’ve understood what names are, we’re moving on to the concept of namespaces. Strictly speaking a namespace is a collection of names. In Python you can imagine a namespaces as a mapping of every name, you have defined, to corresponding objects. Different namespaces can co-exist at a given time but are completely isolated. When we start Python a namespace containing all the built-in names is created and exists as long as we don’t exit the Python.

Built-in function such as id(), print(), type(), list(), dict()  and others are always at disposal to us from any part of the program. Each module creates its own global namespace. These different namespace are isolated so the same name that may exist in different modules do not collide.

Modules can have various functions and classes. A local namespace is created when a function is called, which has all the names defined in it. Similar, is the case with class

What is scope?

Although there are various unique namespaces defined, we may not be able to access all of them from every part of the program. It’s time to introduce variable scope.

Scope is a portion of the program from where a namespace can be accessed directly without any prefix. At any given moment there are at least three nested scopes.

1. Scope of the current function which has local names
2. Scope of the module which has global names
3. Outermost scope which has built-in names.

When a reference is made inside the function, the name is searched in the local namespace, then in the global namespace and finally in the built-in namespace. If we have function inside the function which is called a nested function then a new scope is nested inside the local scope. The example is shown below.

>>> def outerfunction():

...     b = 20

...     def innerfunction():

...         c = 30

...

>>> a = 10

In previous example the variable a is in the global namespace, variable b is in the local namespace of outerfunction() and c is in the nested local namespace of innerfunction(). When we’re inside the innerfunction(), variable c is local variable, while variable b is nonlocal and a is global variable. We can read as well as assign new values to c but can only read b and c from innerfunction(). If we try to assign as a value to b, a new variable b is created in the local namespace which is different than the nonlocal b. Same thing happen when we assign a value to a. However, if we declare a as global, all the reference and assignment go to global a. Similarly, if we want to rebind the variable b, it must be declared as nonlocal. The following example will further clarify this.

>>> def outerfunction():

...     a = 20

...     def innerfunction():

...         a = 30

...     print 'a = ', a

...

>>> outerfunction()

a =  20

Assertions

An assertion is a sanity-check that you can turn on or turn off when you have finish testing the program. An expression is tested, and if the result comes up false, an exception is raised. Assertion are carried out through use of assert statement.

print 1 assert 2 + 2 == 4 print 2 assert 1 + 1 == 3 print 3

1 2 AssertionError

Good practice is to place assertions at the start of a function to check for valid input and after a function call to check for valid output.

Example: what is the highest number printed by this code ?

print 0 assert 'h' != 'w' print 1 assert False print 2 assert True print 3

0 1 AssertionError

Assertion can take a second argument that is passed to the AssertionError raised if the assertion fails. AssertionError expectations can be caught and handled like another exception using the try-except statement, but if not handled, this type of exception will terminate the program.

a = - 10 assert(a >= 0), 'Colder than absolute zero'

AssertionError: Colder than absolute zero

Example: Fill in the blanks to define function that takes one argument. Assert the argument to be positive.

___ function1(x):     _____ x > 0, 'Error!'     _____ x userinput = _________ ("Enter a value: ") val = int(_________) print function1(______)

First run: Enter a value: -10 AssertionError: Error! Second run: Enter a value: 10 10 None