Python is the language of choice for many advanced data tasks for a very good reason. Python is one of the easiest advanced programming languages to learn. Intuitive structures and semantics mean that for people who are not computer scientists, but maybe biologists, statisticians, or the directors of a start-up, Python is a straightforward way to perform a wide variety of data tasks. It is not just a scripting language, but a full-featured object-oriented programming language.

In Python, there are many useful data structures and algorithms built in to the language. Also, because Python is an object-based language, it is relatively easy to create custom data objects. In this book, we will examine both Python internal libraries, some of the external libraries, as well as learning how to build your own data objects from first principles.

Algorithms and data structures are the most fundamental concepts in computing. They are the building blocks from which complex software is built. Having an understanding of these foundation concepts is hugely important in software design and this involves the following three characteristics:

• How algorithms manipulate information contained within data structures
• How data is arranged in memory
• What the performance characteristics of particular data structures are

In this book, we will examine this topic from several perspectives. Firstly, we will look at the fundamentals of the Python programming language from the perspective of data structures and algorithms. Secondly, it is important that we have the correct mathematical tools. We need to understand some fundamental concepts of computer science and for this we need mathematics. By taking a heuristics approach, developing some guiding principles means that, in general, we do not need any more than high school mathematics to understand the principles of these key ideas.

Another important aspect is evaluation. Measuring an algorithms performance involves understanding how each increase in data size affects operations on that data. When we are working on large datasets or real-time applications, it is essential that our algorithms and structures are as efficient as they can be.

Finally, we need a sound experimental design strategy. Being able to conceptually translate a real-world problem into the algorithms and data structures of a programming language involves being able to understand the important elements of a problem and a methodology for mapping these elements to programming structures.

To give us some insight into algorithmic thinking, let's consider a real-world example. Imagine we are at an unfamiliar market and we are given the task of purchasing a list of items. We assume that the market is laid out randomly, and each vendor sells a random subset of items, some of which may be on our list. Our aim is to minimize the price we pay for each item as well as minimize the time spent at the market. One way to approach this is to write an algorithm like the following:

Repeat for each vendor:

1. Does the vendor have items on my list and is the cost less than a predicted cost for the item?
2. If yes, buy and remove from list; if no, move on to the next vendor.
3. If no more vendors, end.

This is a simple iterator, with a decision and an action. If we were to implement this, we would need data structures to define both the list of items we want to buy as well as the list of items of each vendor. We would need to determine the best way of matching items in each list and we need some sort of logic to decide whether to purchase or not.

There are several observations that we can make regarding this algorithm. Firstly, since the cost calculation is based on a prediction, we don't know what the real average cost is; if we underpredict the cost of an item, we come to the end of the market with items remaining on our list. Therefore, we need an efficient way to backtrack to the vendor with the lowest cost.

Also, we need to understand what happens to the time it takes to compare items on our shopping list with items sold by each vendor as the number of items on our shopping list, or the number of items sold by each vendor, increases. The order in which we search through items and the shape of the data structures can make a big difference to the time it takes to do a search. Clearly, we would like to arrange our list, as well as the order we visit each vendor, in such a way that we minimize search time.

Also, consider what happens when we change the buy condition to purchase at thecheapest price, not just the below average price. This changes the problem entirely. Instead of sequentially going from one vendor to the next, we need to traverse the market once and, with this knowledge, we can order our shopping list with regards to the vendors we want to visit.

Obviously, there are many more subtleties involved in translating a real-world problem into an abstract construct such as a programming language. For example, as we progress through the market, our knowledge of the cost of a product improves, so our predicted average price variable becomes more accurate until, by the last stall, our knowledge of the market is perfect. Assuming any kind of backtracking algorithm incurs a cost, we can see cause to review our entire strategy. Conditions such as high price variability, the size and shape of our data structures, and the cost of backtracking all determine the most appropriate solution.

A feature of the Python environment is its interactive console allowing you to both use Python as a desktop programmable calculator and also as an environment to write and test snippets of code. Theread-evaluate-print loop of the console is a very convenient way to interact with a larger code base, such as to run functions and methods or to create instances of classes. This is one of the major advantages of Python over compiled languages such as C/C++ or Java, where thewrite-compile-test-recompile cycle can increase development time considerably compared to Python's read - evaluate - print loop. Being able to type in expressions and get an immediate response can greatly speed up data science tasks.

To translate a real-world problem into one that can be solved by an algorithm, there are two interrelated tasks. Firstly, select the variables, and secondly, find the expressions that relate to these variables. Variables are labels attached to objects; they are not the object itself. They are not containers for objects either. A variable does not contain the object, rather it acts as a pointer or reference to an object. For example, consider the following code:

Here we have created a variable,a, which points to a list object. We create another variable,b, which points to this same list object. When we append an element to this list object, this change is reflected in botha andb.

Python is a dynamically typed language. Variable names can be bound to different values and types during program execution. Each value is of a type, a string, or integer for example; however, the name that points to this value does not have a specific type. This is different from many languages such as C and Java where a name represents a fixed size, type, and location in memory. This means when we initialize variables in Python, we do not need to declare a type. Also, variables, or more specifically the objects they point to, can change type depending on the values assigned to them, for example:

It is important to understand the scoping rules of variables inside functions. Each time a function executes, a new local namespace is created. This represents a local environment that contains the names of the parameters and variables that are assigned by the function. To resolve a namespace when a function is called, the Python interpreter first searches the local namespace (that is, the function itself) and if no match is found, it searches the global namespace. This global namespace is the module in which the function was defined. If the name is still not found, it searches the built-in namespace. Finally, if this fails then the interpreter raises aNameError exception. Consider the following code:

    a=10; b=20
    def my_function():
        global a
        a=11; b=21
    my_function()
    print(a) #prints 11
    print(b) #prints 20

Here is the output of the preceding code:

In the preceding code, we define two global variables. We need to tell the interpreter, using the keywordglobal, that inside the function, we are referring to a global variable. When we change this variable to11, these changes are reflected in the global scope. However, the variableb we set to21 is local to the function, and any changes made to it inside the function are not reflected in the global scope. When we run the function and printb, we see that it retains its global value.

Python programs consist of a sequence of statements. The interpreter executes each statement in order until there are no more statements. This is true if both files run as the main program as well as files that are loaded viaimport. All statements, including variable assignment, function definitions, class definitions, and module imports, have equal status. There are no special statements that have higher priority than any other and every statement can be placed anywhere in a program. There are two main ways of controlling the flow of program execution, conditional statements and loops.

Theif, else, andelif statements control the conditional execution of statements. The general format is a series ofif andelif statements followed by a finalelse statement:

    x='one'
    if x==0:
        print('False')
    elif x==1:
        print('True')
    else: print('Something else')
    #prints 'Something else'

Note the use of the== operator to test for the same values. This returnstrue if the values are equal; it returnsfalse otherwise. Note also that settingx to a string will returnsomething else rather than generate a type error as may happen in languages that are not dynamically typed. Dynamically typed languages such as Python allow flexible assignment of objects with different types.

The other way of controlling program flow is with loops. They are created using thewhile orfor statements, for example:

Python contains 12 built-in data types. These include four numeric types (int,float,complex,bool), four sequence types (str,list,tuple,range), one mapping type (dict), and two set types. It is also possible to create user-defined objects such as functions or classes. We will look at thestring and thelist data types in this chapter and the remaining built-in types in the next chapter.

All data types in Python areobjects. In fact, pretty much everything is an object in Python, including modules, classes, and functions, as well as literals such as strings and integers. Each object in Python has atype, avalue, and anidentity. When we writegreet = "hello world" we are creating an instance of a string object with the value"hello world" and the identity ofgreet. The identity of an object acts as a pointer to the object's location in memory. The type of an object, also known as the object's class, describes the object's internal representation as well as the methods and operations it supports. Once an instance of an object is created, its identity and type cannot be changed.

We can get the identity of an object by using the built-in functionid(). This returns an identifying integer and on most systems this refers to its memory location, although you should not rely on this in any of your code.

Also, there are a number of ways to compare objects, for example:

    if a== b: #a and b have the same value

    if a is b: # if a and b are the same object
    if type(a) is type(b): # a and b are the same type

An important distinction needs to be made betweenmutable andimmutable objects. Mutable object's such as lists can have their values changed. They have methods, such asinsert() orappend(), that change an objects value. Immutable objects, such as strings, cannot have their values changed, so when we run their methods, they simply return a value rather than change the value of an underlying object. We can, of course, use this value by assigning it to a variable or using it as an argument in a function.

Strings are immutable sequence objects, with each character representing an element in the sequence. As with all objects, we use methods to perform operations. Strings, being immutable, do not change the instance; each method simply returns a value. This value can be stored as another variable or given as an argument to a function or method.

The following table is a list of some of the most commonly used string methods and their descriptions:

Strings, like all sequence types, support indexing and slicing. We can retrieve any character from a string by using its indexs[i]. We can retrieve a slice of a string by usings[i:j], wherei andj are the start and end points of the slice. We can return an extended slice by using a stride, as in the following: s[i:j:stride]. The following code should make this clear:

The first two examples are pretty straightforward, returning the character located at index1 and the first seven characters of the string, respectively. Notice that indexing begins at0. In the third example, we are using a stride of2. This results in every second character being returned. In the final example, we omit the end index and the slice returns every second character in the entire string.

You can use any expression, variable, or operator as an index as long as the value is an integer, for example:

Another common operation is traversing through a string with a loop, for example:

Given that strings are immutable, a common question that arises is how we perform operations such inserting values. Rather than changing a string, we need to think of ways to build new string objects for the results we need. For example, if we wanted to insert a word into our greeting, we could assign a variable to the following:

As this code shows, we use the slice operator to split the string at index position5 and use+ to concatenate. Python never interprets the contents of a string as a number. If we need to perform mathematical operations on a string, we need to first convert them to a numeric type, for example:

Lists are probably the most used built-in data structures in Python because they can be composed of any number of other data types. They are a simple representation of arbitrary objects. Like strings, they are indexed by integers starting with zero. The following table contains the most commonly used list methods and their descriptions:

When we are working with lists, and othercontainer objects, it is important to understand the internal mechanism that Python uses to copy them. Python creates real copies only if it has to. When we assign the value of a variable to another variable, both of these variables point to the same memory location. A new slot in memory will only be allocated if one of the variables changes. This has important consequences for mutable compound objects such as lists. Consider the following code:

Here, both thelist1 andlist2 variables point to the same slot in memory. When we change they variable to4, we are changing the samey variable thatlist1 is pointing to.

An important feature of list's is that they can contain nested structures, that is, other lists, for example:

We can access the lists values using the bracket operators and since lists are mutable, they are copied in place. The following example demonstrates how we can use this to update elements; for example, here we are raising the price of flour by 20 percent:

A common and very intuitive way to create lists from expressions is usinglist comprehensions. This allows us to create a list by writing an expression directly into the list, for example:

List comprehensions can be quite flexible; for example, consider the following code. It essentially shows two different ways to performs a function composition, where we apply one function (x * 4) to another (x * 2). The following code prints out two lists representing the function composition off1 andf2 calculated first using afor loop and then using a list comprehension:

    def f1(x): return x*2
    def f2(x): return x*4

    lst = []
    for i in range(16):
        lst.append(f1(f2(i)))

    print(lst)

    print([f1(x)  for x in range(64) if x in [f2(j) for j in range(16)]])

The first line of output is from the for loop construct. The second is from the list comprehension expression:

List comprehensions can also be used to replicate the action of nested loops in a more compact form. For example, we multiply each of the elements contained withinlist1 with each other:

We can also use list comprehensions with other objects such as strings, to build more complex structures. For example, the following code creates a list of words and their letter count:

As we will see, lists form the foundation of many of the data structures we will look at. Their versatility, ease of creation, and use enables them to build more specialized and complex data structures.

In Python, it is not only data types that are treated as objects. Both functions and classes are what are known as first class objects, allowing them to be manipulated in the same ways as built-in data types. By definition, first class objects are:

• Created at runtime
• Assigned as a variable or in a data structure
• Passed as an argument to a function
• Returned as the result of a function

In Python, the termfirst class object is a bit of a misnomer since it implies some sort of hierarchy, whereas all Python objects are essentially first class.

To have a look at how this works, let's define a simple function:

    def greeting(language):
    if language== 'eng':
             return 'hello world'
       if language  == 'fr'
             return 'Bonjour le monde'
       else: return 'language not supported'

Since user-defined functions are objects, we can do things such as include them in other objects, such as lists:

Functions can also be used as arguments for other functions. For example, we can define the following function:

Here, callf() takes a function as an argument, sets a language variable to'eng', and then calls the function with the language variable as its argument. We could see how this would be useful if, for example, we wanted to produce a program that returns specific sentences in a variety of languages, perhaps for some sort of natural language application. Here we have a central place to set the language. As well as ourgreeting function, we could create similar functions that return different sentences. By having one point where we set the language, the rest of the program logic does not have to worry about this. If we want to change the language, we simply change the language variable and we can keep everything else the same.

Functions that take other functions as arguments, or that return functions, are calledhigher order functions. Python 3 contains two built-in higher order functions,filter() andmap(). Note that in earlier versions of Python, these functions returned lists; in Python 3, they return an iterator, making them much more efficient. Themap() function provides an easy way to transform each item into an iterable object. For example, here is an efficient, compact way to perform an operation on a sequence. Note the use of thelambda anonymous function:

Similarly, we can use thefilter built-in function to filter items in a list:

Note that both map andfilter perform the identical function as to what can be achieved by list comprehensions. There does not seem to be a great deal of difference in the performance characteristics apart from a slight performance advantage when using the in built functionsmap andfilter without thelambda operator, compared to list comprehensions. Despite this, most style guides recommend the use of list comprehensions over built-in functions, possibly because they tend to be easier to read.

Creating our own higher order functions is one of the hallmarks of functional programming style. A practical example of how higher order functions can be useful is demonstrated by the following. Here we are passing thelen function as the key to thesort function. This way, we can sort a list of words by length:

Here is another example for case-insensitive sorting:

Note the difference between thelist.sort() method and thesorted built-in function.list.sort(), a method of thelist object, sorts the existing instance of a list without copying it. This method changes the target object and returnsNone. It is an important convention in Python that functions or methods that change the object returnNone to make it clear that no new object was created and that the object itself was changed.

On the other hand, the sorted built-in function returns a new list. It actually accepts any iterable object as an argument, but it will always return a list. Bothlist sort andsorted take two optional keyword arguments as key.

A simple way to sort more complex structures is to use the index of the element to sort using thelambda operator, for example:

Here we have sorted the items by price.

Recursion is one of the most fundamental concepts of computer science. In Python, we can implement a recursive function simply by calling it within its own function body. To stop a recursive function turning into an infinite loop, we need at least one argument that tests for a terminating case to end the recursion. This is sometimes called the base case. It should be pointed out that recursion is different from iteration. Although both involve repetition, iteration loops through a sequence of operations, whereas recursion repeatedly calls a function. Both need a selection statement to end. Technically, recursion is a special case of iteration known as tail iteration, and it is usually always possible to convert an iterative function to a recursive function and vice versa. The interesting thing about recursive functions is that they are able to describe an infinite object within a finite statement.

The following code should demonstrate the difference between recursion and iteration. Both these functions simply print out numbers betweenlow andhigh, the first one using iteration and the second using recursion:

Notice, iterTest, the iteration example, we use awhile statement to test for the condition, then call theprint method, and finally increment thelow value. The recursive example tests for the condition, prints, then calls itself, incrementing thelow variable in its argument. In general, iteration is more efficient; however, recursive functions are often easier to understand and write. Recursive functions are also useful for manipulating recursive data structures such as linked lists and trees, as we will see.

We can create functions that do not just return one result, but rather an entire sequence of results, by using theyield statement. These functions are calledgenerators. Python contains generator functions, which are an easy way to create iterators and they are especially useful as a replacement for unworkably long lists. A generator yields items rather than build lists. For example, the following code shows why we might choose to use a generator as opposed to creating a list:

    # compares the running time of a list compared to a generator
    import time
    #generator function creates an iterator of odd numbers between n and m
    def oddGen(n, m):
        while n < m:
            yield n
            n += 2
    #builds a list of odd numbers between n and m
    def oddLst(n,m):
        lst=[]
        while n<m:
            lst.append(n)
            n +=2
        return lst
    #the time it takes to perform sum on an iterator
    t1=time.time()
    sum(oddGen(1,1000000))
    print("Time to sum an iterator: %f" % (time.time() - t1))

    #the time it takes to build and sum a list
    t1=time.time()
    sum(oddLst(1,1000000))
    print("Time to build and sum a list: %f" % (time.time() - t1))

This prints out the following:

As we can see, building a list to do this calculation takes significantly longer. The performance improvement as a result of using generators is because the values are generated on demand, rather than saved as a list in memory. A calculation can begin before all the elements have been generated and elements are generated only when they are needed.

In the preceding example, thesum method loads each number into memory when it is needed for the calculation. This is achieved by the generator object repeatedly calling the__next__() special method. Generators never return a value other thanNone.

Typically, generator objects are used infor loops. For example, we can make use of theoddcount generator function created in the preceding code to print out odd integers between1 and10:

    for i in oddcount(1,10):print(i)

We can also create agenerator expression, which, apart from replacing square brackets with parentheses, uses the same syntax and carries out the same operation as list comprehensions. Generator expressions, however, do not create a list, they create agenerator object. This object does not create the data, but rather creates that data on demand. This means that generator objects do not support sequence methods such asappend() andinsert(). You can, however, change a generator into a list using thelist() function:

Classes are a way to create new kinds of objects and they are central to object-oriented programming. A class defines a set of attributes that are shared across instances of that class. Typically, classes are sets of functions, variables, and properties.

The object-oriented paradigm is compelling because it gives us a concrete way to think about and represent the core functionality of our programs. By organizing our programs around objects and data rather than actions and logic, we have a robust and flexible way to build complex applications. The actions and logic are still present of course, but by embodying them in objects, we have a way to encapsulate functionality, allowing objects to change in very specific ways. This makes our code less error-prone, easier to extend and maintain, and able to model real-world objects.

Classes are created in Python using theclass statement. This defines a set of shared attributes associated with a collection of class instances. A class usually consists of a number of methods, class variables, and computed properties. It is important to understand that defining a class does not, by itself, create any instances of that class. To create an instance, a variable must be assigned to a class. The class body consists of a series of statements that execute during the class definition. The functions defined inside a class are calledinstance methods. They apply some operations to the class instance by passing an instance of that class as the first argument. This argument is calledself by convention, but it can be any legal identifier. Here is a simple example:

    class Employee(object):
        numEmployee = 0
        def __init__(self, name, rate):
            self.owed = 0
            self.name = name
            self.rate=rate
            Employee.numEmployee += 1

        def __del__(self):
            Employee.numEmployee -= 1

        def hours(self, numHours):
            self.owed += numHours * self.rate
            return("%.2f hours worked" % numHours)

        def pay(self):
            self.owed = 0
            return("payed %s " % self.name)

Class variables, such asnumEmployee, share values among all the instances of the class. In this example,numEmployee is used to count the number of employee instances. Note that theEmployee class implements the__init__ and__del__ special methods, which we will discuss in the next section.

We can create instances of theEmployee objects, run methods, and return class and instance variables by doing the following:

We can use thedir(object) function to get a list of attributes of a particular object. The methods that begin and end with two underscores are calledspecial methods. Apart from the following exception, special method, are generally called by the Python interpreter rather than the programmer; for example, when we use the+ operator, we are actually invoking a call to__add__(). For example, rather than using my_object.__len__() we can use len(my_object) usinglen() on a string object is actually much faster because it returns the value representing the object's size in memory, rather than making a call to the object's__len__ method. The only special method we actually call in our programs, as common practice, is the__init__ method, to invoke the initializer of the superclass in our own class definitions. It is strongly advised not to use the double underscore syntax for your own objects because of potential current or future conflicts with Python's own special methods.

We may, however, want to implement special methods in custom objects, to give them some of the behavior of built-in types. In the following code, we create a class that implements the__repr__ method. This method creates a string representation of our object that is useful for inspection purposes:

    class my_class():
        def __init__(self, greet):
            self.greet = greet
        def __repr__(self):
            return 'a custom object (%r)' % (self.greet)

When we create an instance of this object and inspect it, we can see we get our customized string representation. Notice the use of the%r format placeholder to return the standard representation of the object. This is useful and best practice, because, in this case, it shows us that thegreet object is a string indicated by the quotation marks:

It is possible to create a new class that modifies the behavior of an existing class through inheritance. This is done by passing the inherited class as an argument in the class definition. It is often used to modify the behavior of existing methods, for example:

    class specialEmployee(Employee):
        def hours(self, numHours):
            self.owed += numHours * self.rate * 2
            return("%.2f hours worked" % numHours)

An instance of thespecialEmployee class is identical to anEmployee instance except for the changedhours() method.

For a subclass to define new class variables, it needs to define an__init__() method, as follows:

    class specialEmployee(Employee):
        def __init__(self,name,rate, bonus):
            Employee.__init__(self, name, rate) #calls the base classes
            self.bonus = bonus

        def hours(self, numHours):
            self.owed += numHours * self.rate + self.bonus
            return("%.2f hours worked" % numHours)

Notice that the methods of the base class are not automatically invoked and it is necessary for the derived class to call them. We can test for class membership using the built-in functionisintance(obj1, obj2). This returns true ifobj1 belongs to the class ofobj2 or any class derived fromobj2.

Within a class definition, it is assumed that all methods operate on the instance, but this is not a requirement. There are, however, other types of methods: static methods andclass methods. A static method is just an ordinary function that just happens to be defined in a class. It does not perform any operations on the instance and it is defined using the@staticmethod class decorator. Static methods cannot access the attributes of an instance, so their most common usage is as a convenience to group utility functions together.

Class methods operate on the class itself, not the instance, in the same way that class variables are associated with the classes rather than instances of that class. They are defined using the@classmethod decorator, and are distinguished from instance methods in that the class is passed as the first argument. This is namedcls by convention.

    class Aexp(object):
        base=2
        @classmethod
        def exp(cls,x):
            return(cls.base**x)

    class Bexp(Aexp):
            base=3

The classBexp inherits from theAexp class and changes the base class variable to3. We can run the parent class'sexp() method as follows:

Although this example is a little contrived, there are several reasons why class methods may be useful. For example, because a subclass inherits all the same features of its parent, there is the potential for it to break inherited methods. Using class methods is a way to define exactly what methods are run.

Unless otherwise specified, all attributes and methods are accessible without restriction. This also means that everything defined in a base class is accessible from a derived class. This may cause problems when we are building object-oriented applications where we may want to hide the internal implementation of an object. This can lead to namespace conflicts between objects defined in derived classes with the base class. To prevent this, the methods we define private attributes with have a double underscore, such as__privateMethod(). These method names are automatically changed to_Classname__privateMethod() to prevent name conflicts with methods defined in base classes. Be aware that this does not strictly hide private attributes, rather it just provides a mechanism for preventing name conflicts.

It is recommended to use private attributes when using a classproperty to define mutable attributes. A property is a kind of attribute that rather than returning a stored value, computes its value when called. For example, we could redefine theexp() property with the following:

    class Bexp(Aexp):
        __base=3
        def __exp(self):
            return(x**cls.base)

In this chapter, we have looked at some of the fundamentals of the Python programming language, from basic operations to functions, classes, and objects in Python. In the next chapter, we will examine, in detail, the built-in data structures of Python.

This chapter has given us a good foundation and introduction into Python programming. We covered the use of variables, lists, a couple of control structures, and learned how to use conditionals statement. The various kinds of objects were discussed, together with some materials on the object-oriented aspects of the Python language. We created our own objects and inherited from them.

There is still more that Python offers. As we prepare to examine the later chapters on some implementations of algorithms, the next chapter will focus on numbers, sequences, maps, and sets. These are also data types in Python that prove useful when organizing data for a series of operations.