Advanced Data Structures

We will start this chapter by discussing advanced data structures. Initially, we will be revisiting lists. Then, we will construct a stack and a queue, explore multiple-element membership checking to check whether the data is accurate, and throw a bit of functional programming in for good measure. Don't worry if all of this sounds intimidating. We will take things step by step, and you will feel confident about handling advanced data structures once you have finished this chapter.

Before we jump into constructing data structures, we'll look at a few methods to manipulate them.

Iterator

Iterators in Python are very useful when dealing with data as they allow you to parse the data one unit at a time. Iterators are stateful, which means it will be helpful to keep track of the previous state. An iterator is an object that implements the next method—meaning an iterator can iterate over collections such as lists, tuples, dictionaries, and more. Practically, this means that each time we call the method, it gives us the next element from the collection; if there is no further element in the list, then it raises a StopIteration exception.

Note

A StopIteration exception occurs with the iterator's next method when there are no further values to iterate.

If you are familiar with a programming language such as C, C++, Java, JavaScript, or PHP, you may have noticed the difference between the for loop implementation in those languages, which consists of three distinct parts (the initiation, the increment, and the termination condition), and the for loop in Python. In Python, we do not use that kind of a for loop. What we use in Python is more like a foreach loop:

for i in list_1

This is because, under the hood, the for loop is using an iterator, and thus we do not need to do all the extra steps. The iterator does them for us.

Let's learn about the various functions we can use with itertools. As you execute each line of the code after the import statement, you will be able to see details about what that particular function does and how to use it:

from itertools import (permutations, combinations, \

                       dropwhile, repeat, zip_longest)

permutations?

combinations?

dropwhile?

repeat?

zip_longest?

For example, after executing zip_longest?, we'll see the following output:

Figure 2.1: Help file for the zip_longest function

The preceding screenshot shows how the zip_longest function could be used from the itertools module.

Note

To look up the definition of any function, type the function name, followed by ?, and then press Shift + Enter in a Jupyter Notebook.

Let's go through the following exercise to understand how to use an iterator to iterate through a list.

Exercise 2.01: Introducing to the Iterator

In this exercise, we're going to generate a long list containing numbers. We will first check the memory occupied by the generated list. We will then check how we can use the iterator module to reduce memory utilization, and finally, we will use this iterator to loop over the list. To do this, let's go through the following steps:

1. Open a new Jupyter Notebook and generate a list that will contain 10000000 ones. Then, store this list in a variable called big_list_of_numbers:

   big_list_of_numbers = [1 for x in range (0, 10000000)]

   big_list_of_numbers

   The output (partially shown) is as follows:

   [1,

   1,

   1,

   1,

   1,

   1,

   1,

   1,

   1,

   1,

2. Check the size of this variable:

   from sys import getsizeof

   getsizeof(big_list_of_numbers)

   The output should be as follows:

   81528056

   The value shown is 81528056 (in bytes). This is a huge chunk of memory occupied by the list. And the big_list_of_numbers variable is only available once the list comprehension is over. It can also overflow the available system memory if you try too big a number.

3. Let's use the repeat() method from itertools to get the same number but with less memory:

   from itertools import repeat

   small_list_of_numbers = repeat(1, times=10000000)

   getsizeof(small_list_of_numbers)

   The output should be:

   56

   The last line shows that our list small_list_of_numbers is only 56 bytes in size. Also, it is a lazy method, a technique used in functional programming that will delay the execution of a method or a function by a few seconds. In this case, Python will not generate all the elements initially. It will, instead, generate them one by one when asked, thus saving us time. In fact, if you omit the times keyword argument in the repeat() method in the preceding code, then you can practically generate an infinite number of ones.

4. Loop over the newly generated iterator:

   for i, x in enumerate(small_list_of_numbers):

       print(x)

       if i > 10:

           break

   The output is as follows:

   1

   1

   1

   1

   1

   1

   1

   1

   1

   1

   1

   1

We use the enumerate function so that we get the loop counter, along with the values. This will help us break the loop once we reach a certain number (10, for example).

Note

To access the source code for this specific section, please refer to https://packt.live/2N8odTH.

You can also run this example online at https://packt.live/3fAPFGa.

In this exercise, we first learned how to use the iterator function to reduce memory usage. Then, we used an iterator to loop over a list. Now, we'll see how to create stacks.

Stacks

A stack is a very useful data structure. If you know a bit about CPU internals and how a program gets executed, then you will know that a stack is present in many such cases. It is simply a list with one restriction, Last In First Out (LIFO), meaning an element that comes in last goes out first when a value is read from a stack. The following illustration will make this a bit clearer:

Figure 2.2: A stack with two insert elements and one pop operation

As you can see, we have a LIFO strategy to read values from a stack. We will implement a stack using a Python list. Python lists have a method called pop, which does the exact same pop operation that you can see in the preceding illustration. Basically, the pop function will take an element off the stack, using the Last in First Out (LIFO) rules. We will use that to implement a stack in the following exercise.

Exercise 2.02: Implementing a Stack in Python

In this exercise, we'll implement a stack in Python. We will first create an empty stack and add new elements to it using the append method. Next, we'll take out elements from the stack using the pop method. Let's go through the following steps:

1. Import the necessary Python library and define an empty stack:

   import pandas as pd

   stack = []

   Note

   pandas is an open source data analysis library in Python.

2. Use the append method to add multiple elements to the stack. Thanks to the append method, the element will always be appended at the end of the list:

   stack.append('my_test@test.edu')

   stack.append('rahul.subhramanian@test.edu')

   stack.append('sania.test@test.edu')

   stack.append('alec_baldwin@test.edu')

   stack.append('albert90@test.edu')

   stack.append('stewartj@test.edu')

   stack

   The output is as follows:

   ['my_test@test.edu',

   'rahul.subhramanian@test.edu',

   'sania.test@test.edu',

   'alec_baldwin@test.edu',

   'albert90@test.edu',

   'stewartj@test.edu']

3. Let's read a value from our stack using the pop method. This method reads the current last index of the list and returns it to us. It also deletes the index once the read is done:

   tos = stack.pop()

   tos

   The output is as follows:

   'stewartj@test.edu'

   As you can see, the last value of the stack has been retrieved. Now, if we add another value to the stack, the new value will be appended at the end of the stack.

4. Append Hello@test.com to the stack:

   stack.append("Hello@test.com")

   stack

   The output is as follows:

   ['my_test@test.edu',

   'rahul.subhramanian@test.edu',

   'sania.test@test.edu',

   'alec_baldwin@test.edu',

   'albert90@test.edu',

   'Hello@test.com']

   Note

   To access the source code for this specific section, please refer to https://packt.live/3hACc2B.

   You can also run this example online at https://packt.live/2Yb4uct.

From the exercise, we can see that the basic stack operations, append and pop, are pretty easy to perform.

Let's visualize a problem where you are scraping a web page and you want to follow each URL present there (backlinks). Let's split the solution to this problem into three parts. In the first part, we would append all the URLs scraped off the page into the stack. In the second part, we would pop each element in the stack, and then lastly, we would examine every URL, repeating the same process for each page. We will examine a part of this task in the next exercise.

Exercise 2.03: Implementing a Stack Using User-Defined Methods

In this exercise, we will continue the topic of stacks from the last exercise. This time, we will implement the append and pop functions by creating user-defined methods. We will implement a stack, and this time with a business use case example (taking Wikipedia as a source). The aim of this exercise is twofold. In the first few steps, we will extract and append the URLs scraped off a web page in a stack, which also involves the string methods discussed in the last chapter. In the next few steps, we will use the stack_pop function to iterate over the stack and print them. This exercise will show us a subtle feature of Python and how it handles passing list variables to functions. Let's go through the following steps:

1. First, define two functions: stack_push and stack_pop. We renamed them so that we do not have a namespace conflict. Also, create a stack called url_stack for later use:

   def stack_push(s, value):

       return s + [value]

   def stack_pop(s):

       tos = s[-1]

       del s[-1]

       return tos

   url_stack = []

   url_stack

   The output is as follows:

   []

   The first function takes the already existing stack and adds the value at the end of it.

   Note

   Notice the square brackets around the value to convert it into a one-element list using the + operation. The second function reads the value that's currently at the -1 index of the stack, then uses the del operator to delete that index, and finally returns the value it read earlier.

   Now, we are going to have a string with a few URLs in it.

2. Analyze the string so that we push the URLs in the stack one by one as we encounter them, and then use a for loop to pop them one by one. Let's take the first line from the Wikipedia article (https://en.wikipedia.org/wiki/Data_mining) about data science:

   wikipedia_datascience = """Data science is an interdisciplinary field that uses scientific methods, processes, algorithms and systems to extract knowledge [https://en.wikipedia.org/wiki/Knowledge] and insights from data [https://en.wikipedia.org/wiki/Data] in various forms, both structured and unstructured,similar to data mining [https://en.wikipedia.org/wiki/Data_mining]"""

   For the sake of the simplicity of this exercise, we have kept the links in square brackets beside the target words.

3. Find the length of the string:

   len(wikipedia_datascience)

   The output is as follows:

   347

4. Convert this string into a list by using the split method from the string, and then calculate its length:

   wd_list = wikipedia_datascience.split()

   wd_list

   The output is as follows (partial output):

   ['Data',

   'science',

   'is',

   'an',

   'interdisciplinary',

   'field',

   'that',

   'uses',

   'scientific',

   'methods,',

5. Check the length of the list:

   len(wd_list)

   The output is as follows:

   34

6. Use a for loop to go over each word and check whether it is a URL. To do that, we will use the startswith method from the string, and if it is a URL, then we push it into the stack:

   for word in wd_list:

       if word.startswith("[https://"):

           url_stack = stack_push(url_stack, word[1:-1])

           print(word[1:-1])

   The output is as follows:

   https://en.wikipedia.org/wiki/Knowledge

   https://en.wikipedia.org/wiki/Data

   https://en.wikipedia.org/wiki/Data_mining

   Notice the use of string slicing to remove the surrounding double quotes "[" "]".

7. Print the value in url_stack:

   print(url_stack)

   The output is as follows:

   ['https://en.wikipedia.org/wiki/Knowledge',

   'https://en.wikipedia.org/wiki/Data',

   'https://en.wikipedia.org/wiki/Data_mining']

8. Iterate over the list and print the URLs one by one by using the stack_popz function:

   for i in range(0, len(url_stack)):

       print(stack_pop(url_stack))

   The output is as follows:

   

   Figure 2.3: Output of the URLs that are printed using a stack

9. Print it again to make sure that the stack is empty after the final for loop:

   print(url_stack)

   The output is as follows:

   []

   Note

   To access the source code for this specific section, please refer to https://packt.live/2Y7oXyT.

   You can also run this example online at https://packt.live/3e9Smhz.

In this exercise, we have noticed a strange phenomenon in the stack_pop method. We passed the list variable there, and we used the del operator inside the function in step 1, but it changed the original variable by deleting the last index each time we called the function. If you use languages like C, C++, and Java, then this is a completely unexpected behavior as, in those languages, this can only happen if we pass the variable by reference, and it can lead to subtle bugs in Python code. So, be careful when using the user-defined methods.

Lambda Expressions

In general, it is not a good idea to change a variable's value inside a function. Any variable that is passed to the function should be considered and treated as immutable. This is close to the principles of functional programming. However, in that case, we could use unnamed functions that are neither immutable nor mutable and are typically not stored in a variable. Such an expression or function, called a lambda expression in Python, is a way to construct one-line, nameless functions that are, by convention, side-effect-free and are loosely considered as implementing functional programming.

Let's look at the following exercise to understand how we use a lambda expression.

Exercise 2.04: Implementing a Lambda Expression

In this exercise, we will use a lambda expression to prove the famous trigonometric identity:

Figure 2.4: Trigonometric identity

Let's go through the following steps to do this:

1. Import the math package:

   import math

2. Define two functions, my_sine and my_cosine, using the def keyword. The reason we are declaring these functions is the original sin and cos functions from the math package take radians as input, but we are more familiar with degrees. So, we will use a lambda expression to define a wrapper function for sine and cosine, then use it. This lambda function will automatically convert our degree input to radians and then apply sin or cos on it and return the value:

   def my_sine():

       return lambda x: math.sin(math.radians(x))

   def my_cosine():

       return lambda x: math.cos(math.radians(x))

3. Define sine and cosine for our purpose:

   sine = my_sine()

   cosine = my_cosine()

   math.pow(sine(30), 2) + math.pow(cosine(30), 2)

   The output is as follows:

   1.0

Notice that we have assigned the return value from both my_sine and my_cosine to two variables, and then used them directly as the functions. It is a much cleaner approach than using them explicitly. Notice that we did not explicitly write a return statement inside the lambda function; it is assumed.

Note

To access the source code for this specific section, please refer to https://packt.live/3fJW9mb.

You can also run this example online at https://packt.live/30Pn8by.

Now, in the next section, we will be using lambda functions, also known as anonymous functions, which come from lambda calculus. Lambda functions are useful for creating temporary functions that are not named. The lambda expression will take an input and then return the first character of that input.

Exercise 2.05: Lambda Expression for Sorting

In this exercise, we will be exploring the sort function to take advantage of the lambda function. What makes this exercise useful is that you will be learning how to create any unique algorithm that could be used for sorting a dataset. The syntax for a lambda function is as follows:

lambda x : <do something with x>

A lambda expression can take one or more inputs. A lambda expression can also be used to reverse sort by using the parameter of reverse as True. We'll use the reverse functionality as well in this exercise. Let's go through the following steps:

1. Let's store the list of tuples we want to sort in a variable called capitals:

   capitals = [("USA", "Washington"), ("India", "Delhi"), ("France", "Paris"), ("UK", "London")]

2. Print the output of this list:

   capitals

   The output will be as follows:

   [('USA', 'Washington'),

   ('India', 'Delhi'),

   ('France', 'Paris'),

   ('UK', 'London')]

3. Sort this list by the name of the capitals of each country, using a simple lambda expression. The following code uses a lambda function as the sort function. It will sort based on the first element in each tuple:

   capitals.sort(key=lambda item: item[1])

   capitals

   The output will be as follows:

   [('India', 'Delhi'),

   ('UK', 'London'),

   ('France', 'Paris'),

   ('USA', 'Washington')]

As we can see, lambda expressions are powerful if we master them and use them in our data wrangling jobs. They are also side-effect-free—meaning that they do not change the values of the variables that are passed to them in place.

Note

To access the source code for this specific section, please refer to https://packt.live/2AzcTxv.

You can also run this example online at https://packt.live/3hDpe4o.

We will now move on to the next section, where we will discuss membership checking for each element. Membership checking is commonly used terminology in qualitative research and describes the process of checking that the data present in a dataset is accurate.

Exercise 2.06: Multi-Element Membership Checking

In this exercise, we will create a list of words using for loop to validate that all the elements in the first list are present in the second list. Let's see how:

1. Create a list_of_words list with words scraped from a text corpus:

   list_of_words = ["Hello", "there.", "How", "are", "you", "doing?"]

   list_of_words

   The output is as follows:

   ['Hello', 'there.', 'How', 'are', 'you', 'doing?']

2. Define a check_for list, which will contain two similar elements of list_of_words:

   check_for = ["How", "are"]

   check_for

   The output is as follows:

   ['How', 'are']

   There is an elaborate solution, which involves a for loop and a few if/else conditions (and you should try to write it), but there is also an elegant Pythonic solution to this problem, which takes one line and uses the all function. The all function returns True if all elements of the iterable are True.

3. Use the in keyword to check membership of the elements in the check_for list in list_of_words:

   all(w in list_of_words for w in check_for)

   The output is as follows:

   True

   Note

   To access the source code for this specific section, please refer to https://packt.live/3d5pyVT.

   You can also run this example online at https://packt.live/2C7GPB1.

It is indeed elegant and simple to reason about, and this neat trick is very important while dealing with lists. Basically, what we are doing is looping over the first list with the comprehension and then looping over the second list using the for loop. What makes this elegant is how compactly we can represent this complex process. Caution should be taken when using very complex list comprehension—the more complex you make it, the harder it is to read.

Let's look at the next data structure: a queue.

Queue

Apart from stacks, another high-level data structure type that we are interested in is queues. A queue is like a stack, which means that you continue adding elements one by one. With a queue, the reading of elements obeys the First in First Out (FIFO) strategy. Check out the following diagram to understand this better:

Figure 2.5: Pictorial representation of a queue

We will accomplish this first using list methods and will show you that, for this purpose, they are inefficient. Then, we will learn about the dequeue data structure from the collections module of Python. A queue is a very important data structure. We can think of a scenario on a producer-consumer system design. When doing data wrangling, you will often come across a problem where you must process very big files. One of the ways to deal with this problem is to split the chunk the contents of the file into smaller parts and then push them into a queue while creating small, dedicated worker processes, to read off the queue and process one small chunk at a time. This is a very powerful design, and you can even use it efficiently to design huge multi-node data wrangling pipelines.

Exercise 2.07: Implementing a Queue in Python

In this exercise, we'll implement a queue in Python. We'll use the append function to add elements to the queue and use the pop function to take elements out of the queue. We'll also use the deque data structure and compare it with the queue in order to understand the wall time required to complete the execution of an operation. To do so, perform the following steps:

1. Create a Python queue with the plain list methods. To record the time the append operation in the queue data structure takes, we use the %%time command:

   %%time

   queue = []

   for i in range(0, 100000):

       queue.append(i)

   print("Queue created")

   queue

   Note

   %%time is a regular built-in magic command in Python to capture the time required for an operation to execute.

   The output (partially shown) is as follows:

   

   Figure 2.6: Wall time recorded for the append function in the queue

2. If we were to use the pop function to empty the queue and check the items in it:

   for i in range(0, 100000):

       queue.pop(0)

   print("Queue emptied")

   The output would be as follows:

   Queue emptied

   However, this time, we'll use the %%time magic command while executing the preceding code to see that it takes a while to finish:

   %%time

   for i in range(0, 100000):

       queue.pop(0)

   print("Queue emptied")

   queue

   The output is as follows:

   

   Figure 2.7: Wall time recorded for the pop function in the queue

   Note

   If you are working on Google Colab or other virtual environments, you will see an additional line indicating the CPU time present in the output. This is the CPU time of the server on which Google Colab (or any other virtual environment) is running on. However, if you are working on your local system, this information will not be a part of the output.

   In a modern MacBook, with a quad-core processor and 8 GB of RAM, it took around 1.20 seconds to finish. With Windows 10, it took around 2.24 seconds to finish. It takes this amount of time because of the pop(0) operation, which means every time we pop a value from the left of the list (the current 0 index), Python has to rearrange all the other elements of the list by shifting them one space left. Indeed, it is not a very optimized implementation.

3. Implement the same queue using the deque data structure from Python's collections package and perform the append and pop functions on this data structure:

   %%time

   from collections import deque

   queue2 = deque()

   for i in range(0, 100000):

       queue2.append(i)

   print("Queue created")

   for i in range(0, 100000):

       queue2.popleft()

   print("Queue emptied")

   The output is as follows:

   

Figure 2.8: Wall time measured for deque

With the specialized and optimized queue implementation from Python's standard library, the time that this should take for both the operations is only approximately 27.9 milliseconds. This is a huge improvement on the previous one.

Note

To access the source code for this specific section, please refer to https://packt.live/30R69Wc.

You can also run this example online at https://packt.live/3dazIEL.

We will end the discussion on data structures here. What we discussed here is just the tip of the iceberg. Data structures are a fascinating subject. There are many other data structures that we did not touch on and that, when used efficiently, can offer enormous added value. We strongly encourage you to explore data structures more. Try to learn about linked lists, trees, graphs, and all the different variations of them as much as you can; you will find there are many similarities between them and you will benefit greatly from studying them. Not only do they offer the joy of learning, but they are also the secret mega-weapons in the arsenal of a data practitioner that you can bring out every time you are challenged with a difficult data wrangling job.

Activity 2.01: Permutation, Iterator, Lambda, and List

In this activity, we will be using permutations to generate all possible three-digit numbers that can be generated using 0, 1, and 2. A permutation is a mathematical way to represent all possible outcomes. Then, we'll loop over this iterator and also use isinstance and assert to make sure that the return types are tuples. Use a single line of code involving dropwhile and lambda expressions to convert all the tuples to lists while dropping any leading zeros (for example, (0, 1, 2) becomes [1, 2]). Finally, we will write a function that takes a list like before and returns the actual number contained in it.

These steps will guide you as to how to solve this activity:

1. Look up the definition of permutations and dropwhile from itertools.
2. Write an expression to generate all the possible three-digit numbers, using 0, 1, and 2.
3. Loop over the iterator expression you generated before. Print each element returned by the iterator. Use assert and isinstance to make sure that the elements are of the tuple type.
4. Write the loop again, using dropwhile, with a lambda expression to drop any leading zeros from the tuples. As an example, (0, 1, 2) will become [0, 2]. Also, cast the output of dropwhile to a list.
5. Check the actual type that dropwhile returns.
6. Combine the preceding code into one block; this time, write a separate function where you will pass the list generated from dropwhile and the function will return the whole number contained in the list. As an example, if you pass [1, 2] to the function, it will return 12. Make sure that the return type is indeed a number and not a string. Although this task can be achieved using other tricks, treat the incoming list as a stack in the function and generate the number by reading the inpidual digits from the stack.

   The final output should look like this:

   12.0

   21.0

   102.0

   120.0

   201.0

   210.0

   Note

   The solution for this activity can be found on page 458.

With this activity, we have finished this topic and will move on to the next topic, which involves basic file-level operations.

Note

We encourage you to think about a solution to the preceding problem without using all the advanced operations and data structures we have used here. You will soon realize how complex the solution is, and how much more detailed it must be. Then, you will understand how much value these data structures and operations bring.