# coding: utf-8
# # Table of contents
# 1. [What is an Algorithm?](#algorithm)
# 2. [Algorithms and Programming](#programming)
# 3. [Performance Measurement of Sorting Algorithms](#performance)
# 5. [JIT Optimization](#jit)
# 6. [Stack Overflow](#overflow)
# # What is an Algorithm?
#
# At its most basic level, an algorithm is a step-by-step procedure for solving a problem or specifying tasks to be done. Although you can theoretically use an algorithm for almost any application, it is commonly used in computer science and mathematics.
#
# The following picture is a basic example of an algorithm:
#
#
#
# ## Practical example
# Let us introduce you to Bob. Bob has a walnut tree in his garden and he loves walnuts. He knows that there are walnuts from his tree in his garden. While some of them are already rotten, the others are ready for picking and consuming. Bob knows, that over the next week, more and more walnuts will fall from the tree onto the ground. Bob now wants to solve the problem of collecting the walnuts. Since he's a computer scientist, he tackels the problem as a proper computer scientist would:
#
# 1. Bob tries to understand the problem:
# * Bob wants to collect the walnuts. Some are still in the tree getting ripe, others are lying on the ground in the moisty grass, fresh and rotten ones. In addition, the nuts are hard to spot in the grass and to distinguish between fresh and rotten, Bob has to pick them up to get a closer look. Bob also has a bucket for collecting where he will put the fresh nuts. A way of structuring the problem is to use the "divide and conquer" method."Collecting walnuts" divides to "find the nuts" and "pick them up". "Find the nuts" divides to "search for the nuts", that can be solved by searching for them with your feet in the grass, using your hands or by looking closely. Also, Bob has to be clear about his goal. Does he want as many non-rotten nuts as possible or will he be statisfied with a large quantity?
#
# 2. Bob thinks about different ways to solve the problem of collecting nuts:
# * A: Bob could go to the tree and stay there with his bucket, observing the nuts falling down and collecting them one by one.
# * B: Bob goes to the tree each day. Crouch-walks under the tree through the grass. When he finds a nut, he decides whether it is rotten or not and puts the non-rotten nuts in his bucket.
# * C: Bob walks through the grass with his bucket, trying to feel the nuts with his feet, then bends over and collects them each time he finds one. When the bucket is full, he sorts through them and throws the rotten ones away.
#
# 3. Bob maps it out, using psuedo-code, a flowchart, or something similar:
# * This helps Bob to visualize and evaluate his solutions. While **A** would garantee Bob getting close to all the nuts, it would take very long. **B** would be less time consuming but more exhausting. If Bob does it this way, the workload will grow from day to day, since he has to reevaluate more and more rotten ones, since he doesn't pick them up, the number of evaluations each day will increase. So Bob goes for **C**: a quick way, no bending over and a more or less steady number of evaluations. Surely he will not get the highest amount of fresh nuts, but still enough. Work smart, not hard. All the possible solutions have their pros and cons.
# # Algorithms and programming
#
# Algorithms are the cornerstone of the programming world, as every program revolves around the use of algorithms. Furthermore, algorithms are created independently from underlying languages and can therefore be implemented in every programming language. The following is a basic outline of how to create an algorithm for computer science:
# 1. Understand the problem
# 2. Think of different ways to solve it, and pick what you believe to be the most efficient way
# 3. Map it out, using psuedo-code, a flowchart, or something similar
# 4. Implement the solution, i.e. translate your method into the actual coding language
# 5. Test and debug your code
#
# ## Algorithm Implementation
# Today, we want to focus on the fourth step of algorithm creation: implementation. In this step, we want to translate our method into our coding method of choice, and ensure that it is written in an elegant and an optimal way. In other words, we want to make sure that the program is compact and fast. Oftentimes, these goals are aligned, but sometimes they are not. These ideas are talked about in terms of time complexity and space complexity. These are defined as follows:
# - **Time complexity**: the amount of time it takes to run an algorithm as a function of the amount of input
# - **Space complexity**: the amount of space/memory taken by an algorithm as a function of the amount of input
#
# In this tutorial, we will primarily discuss time. Although time complexity is extremely difficult to measure, in Python we can get a rough idea of the time demands of an algorithm by using the time library. The time library can measure many different types of time, but we need to focus on wall-clock time and CPU time, i.e. natural and processing time. Wall-clock time is the time we, as humans, are familiar with. In other words, this is the time a stopwatch would read if you started it at the beginning of the process and ended it exactly as it finished. CPU time is the time the computer dedicates to the process. As computers are running multiple processes at a time, not 100% of the wall-clock time will be dedicated to the specific process you are measuring. CPU time avoids this issue, and allows a more comparable measure.
#
# ## Introduction to the problem
# In the endeavor of visualizing the implementation of algorithms, we will define a problem and then try to solve it with three different algorithm implementations. The code you see below is creating a set amount of different integers and inserting them into a list. The problem at hand now will be to sort the list so that our result will be a list ordered from the least integer to the greatest. There is actually an already built-in function in Python to `sort()` a list but in order to visualize the implementation of algorithms, we will not use `sort()`.
# In[1]:
#Here we create an list that will then be sorted by our algorithms
import random as rdm #Here we import a library which has a function that will be used when generating the list
N = 10000 #How many numbers that should be sorted
lowerBound = 1 #Lower bound for the generated numbers
upperBound = N*5 #Upper bound for the genereated numbers
tutorial_list = []
tutorial_list.extend(rdm.sample(range(int(lowerBound), int(upperBound)), int(N)))
jit_list = tutorial_list #We will come back to this list later...
# The code above generates the list which we will be used when executing our sorting algorithms. The list consists of N randomly selected unique integers from the range 1 to Nx5. The reason why the upperbound is Nx5 is because of the function `rdm.sample()`, which will draw an integer from the range withut reinserting it. So, to not run out of numbers to pick, the range has to be grater than N.
#
# When the random selection has been made the list will be saved to tutorial_list which we will use in our implementation of algorithms.
# ### Insertion Sort
# In[2]:
insertion_list = tutorial_list
def isort(insertion_list):
for i in range(1, len(insertion_list)):
value = insertion_list[i]
spot = i
while spot > 0 and insertion_list[spot-1] > value:
insertion_list[spot] = insertion_list[spot-1]
spot = spot-1
insertion_list[spot] = value
# Code inspired by this [source](http://interactivepython.org/courselib/static/pythonds/SortSearch/TheInsertionSort.html?fbclid=IwAR1dTXxY6dgWzmRoo9ZCIq2iRrghxf_JeTrqWt0BcdUTa-my_vsR7iFcRtQ "interactivepython.org")
#
# The above function is an implementation of a so-called insertion sort algorithm. What the basically does is dividing the list into two sublists. One that is sorted and one that is not. First, it assumes that the first element in the list is sorted, then it will compare the first position to the second position. Given that the integer in the second position is lesser the algorithm will switch position of the two integer so that the lesser integer ends up in the first spot. The “sorted list” now consists of two integers. Because of the while loop, the procedure will be repeated for all the numbers until every number is a part of the sorted list.
# ### Shell Sort
# In[3]:
shell_list = tutorial_list
def shell_sort(shell_list):
gap = len(shell_list) // 2
while gap > 0:
for start_position in range(gap):
gap_insertion_sort(shell_list, start_position, gap)
gap = gap // 2
def gap_insertion_sort(shell_list, start_position, gap):
for i in range(start_position+gap, len(shell_list), gap):
current_value = shell_list[i]
position = i
while position >= gap and shell_list[position-gap] > current_value:
shell_list[position] = shell_list[position - gap]
position = position-gap
shell_list[position] = current_value
# Code inspired by this [source](http://www.zaxrosenberg.com/must-know-sorting-algorithms-in-python/?fbclid=IwAR3kUYFi70WLoPgBvUBxxy0kKhHrUPGxTZNUgO24uX__0c-dOEyQWDwWkv4 "zaxrosenberg.com")
#
# A shell sort improves on the insertion sort by dividing the original list into smaller sublists which are then sorted by insertion sort. Therefore, this sorting method uses the "divide and conquer" strategy. It starts by comparing pairs of elements far apart from each other and sorting them while reducing the comparison gap between them. The shellsort is heavily dependent on what type of gap sequence it uses. Our gap sequence is the original from 1959. The comparison continues until the gap is filled - ending the sort.
# ### Bubble Sort
# In[4]:
bubble_list = tutorial_list
def bubblesort(bubble_list):
# Swap the elements to arrange in order
for i in range(len(bubble_list)-1,0,-1):
for idx in range(i):
if bubble_list[idx] > bubble_list[idx+1]:
temp = bubble_list[idx]
bubble_list[idx] = bubble_list[idx+1]
bubble_list[idx+1] = temp
# Code inspired by this [source](http://interactivepython.org/runestone/static/pythonds/SortSearch/TheBubbleSort.html "interactivepython.org")
#
# The function above is an implementation of a style of sorting algorithm called a bubble algorithm. In essence, this is the simplest sorting algorithm. The way that it works is by repeatedly running through a list or array and swapping the elements that are next to each other if they are in the incorrect order. Take, for example, this list: [1, 3, 2, 9, 6]. First, the function will compare the first two elements: 1 and 3. It sees that they are in order, and thus will not do anything. Next, it will compare 3 and 2, and seeing that they are not in order, will swap their positions, changing the list to [1, 2, 3, 9, 6]. The algorithm will continue this pattern for the rest of the list and then restart from the beginning to ensure that everything is in order, ending with the sorted list of [1, 2, 3, 6, 9]. The bubble sort is a popular implementation because of its simplicity, but it can be quite time intensive with longer lists or arrays.
# # Performance measurement of sorting algorithms
#
# Now when we have defined three algorithms for our problem it is time to consider the performance of our code. To measure performance we can use the so-called "time" package. To measure performance, we will see how much time that passes between the start and finish of the algorithm. To do this there are two useful functions in the package: `time.time()` and `time.clock()`.
#
# What `time.time()` does is measuring wallclock time between two points in the code, e.g. how many actual seconds that passes from start to finish. This method though is not entirely optimal. The reason for this is that the computer might be working on other tasks during the same time one is trying to measure the performance of the code. This means that memory in the CPU might be occupied and therefore slowing down the process. To solve this problem one can use `time.clock()` instead.
#
# `time.clock()` has not been updated for a while though and is not the best way of determining dedicated CPU time. The new, updated versions of `time.clock()` are `time.perf_counter()` and `time.process_time()`.
#
# In our examples below, we will use the updated CPU timer with fractional seconds called `time.process_time()`.
# In[5]:
import time
#measuring isort performance
start_isort = time.process_time()
isort(tutorial_list)
end_isort = time.process_time()
#measuring shellsort performance
start_shellsort = time.process_time()
shell_sort(tutorial_list)
end_shellsort = time.process_time()
#measuring bubblesort performance
start_bubblesort = time.process_time()
bubblesort(tutorial_list)
end_bubblesort = time.process_time()
print('isort sorted the tutorial list in {} seconds'.format(end_isort-start_isort))
print('shellsort sorted the tutorial list in {} seconds'.format(end_shellsort-start_shellsort))
print('bubblesort sorted the tutorial list in {} seconds'.format(end_bubblesort-start_bubblesort))
# ## Results
# As we can see from the results above the shell short is more efficent than the other two less complex sorting algorithms. The question is though, will the shell short algorithm always be the better choice when one needs to sort a list? Well that depends...
#
# When considering a programming solution for a problem one thing to keep in mind is the pay-off between the time invested in optimizing the code and the actual time saved when one is later using the code. For example, let us assume that we have the knowledge to write the simpler bubble-sort algorithm, but lack the knowledge to write something more efficient. If there is a problem that consists of a shorter list that only needs to be sorted once, it might be wiser to just use the simpler algorithm, even though it is less efficient. Because the payoff for investing time in optimizing the code and learning more efficient ways to do a sorting algorithm might be very low. On the other hand, if we are facing a more complex problem, where our sorting algorithm will be run a considerable amount of times, it might be worth investing time in optimizing the code to save a lot of time later when the program is running.
#
# So, when deciding how to implement an algorithm solution to a problem one should always keep in mind the purpose of the implementation and then make a decision about the complexity of the code.
# # Optimizing algorithms further with `@jit`
#
# `numba` is a *Just-In-Time* compiler for Python which means that whenever you call a function in Python, all or part of your code will convert to machine code "just-in-time" for execution and run on your local machine code speed.
#
# With the help of Numba, you can speed up your calculations and algorithms. There are other compilers for Python such as `pypy` and `cython`, so why use Numba? The easiest answer is that with Numba, you don't have to change your code at all for basic speed-up. The only thing you have to do is add a Python functionality, a *decorator* (wrapper), around your functions. We have chosen to partly compile our sorting algorithms using the `@jit` decorator.
#
# Pyhton is a "high-level" language that is easy for humans to work with and understand but is far away from the language that computers use to understand. The most basic explanation of how it works is that your Python function is taken, optimized and converted into a language that is easier for the computer to read. If you want to read more about this, please visit this [website](https://towardsdatascience.com/speed-up-your-algorithms-part-2-numba-293e554c5cc1 "towardsdatascience.com") or google JIT.
# In[6]:
#When measuring performance of JIT, we will use the copied list called jit_list and JIT every algorithm
import time
from numba import jit
#Algorithm 1, the insertion sort, now with JIT decorator
insertion_list2 = jit_list
@jit
def isort(insertion_list2):
for i in range(1, len(insertion_list2)):
value = insertion_list2[i]
spot = i
while spot > 0 and insertion_list2[spot-1] > value:
insertion_list2[spot] = insertion_list2[spot-1]
spot = spot-1
insertion_list2[spot] = value
#Algorithm 2, the shell sort, now with JIT decorator
shell_list2 = jit_list
@jit
def shell_sort(shell_list2):
gap = len(shell_list2) // 2
while gap > 0:
for start_position in range(gap):
gap_insertion_sort(shell_list2, start_position, gap)
gap = gap // 2
@jit
def gap_insertion_sort(shell_list2, start_position, gap):
for i in range(start_position+gap, len(shell_list2), gap):
current_value = shell_list2[i]
position = i
while position >= gap and shell_list2[position-gap] > current_value:
shell_list2[position] = shell_list2[position - gap]
position = position-gap
shell_list2[position] = current_value
#Algorithm 3, the buuble sort, now with JIT decorator
bubble_list2 = jit_list
@jit
def bubblesort(bubble_list2):
# Swap the elements to arrange in order
for i in range(len(bubble_list2)-1,0,-1):
for idx in range(i):
if bubble_list2[idx] > bubble_list2[idx+1]:
temp = bubble_list2[idx]
bubble_list2[idx] = bubble_list2[idx+1]
bubble_list2[idx+1] = temp
#measuring isort performance with JIT
start_isort2 = time.process_time()
isort(jit_list)
end_isort2 = time.process_time()
#measuring shellsort performance with JIT
start_shellsort2 = time.process_time()
shell_sort(jit_list)
end_shellsort2 = time.process_time()
#measuring bubblesort performance with JIT
start_bubblesort2 = time.process_time()
bubblesort(jit_list)
end_bubblesort2 = time.process_time()
#remember that we made a copy of the tutorial list and called it "jit list" for this exercise
print('isort sorted the JIT list in {} seconds'.format(end_isort2-start_isort2))
print('shellsort sorted the JIT list in {} seconds'.format(end_shellsort2-start_shellsort2))
print('bubblesort sorted the JIT list in {} seconds'.format(end_bubblesort2-start_bubblesort2))
# ## Results from using `@jit`
#
# As we can see, two of the three algorithms have tremendous performance improvement. By using the `@jit` wrapper, the algortihms could be processed much quicker than before. An interesting observation is that our `shell_sort()` algorithm is slower than before. This may be because of our original "gap sequence" being slower with the `numba` package or that the shell sort as a function works slower with JIT.
#
# When using already defined functions, which is made by other users, there is a problem of not knowing excactly what the function does. As illustrated above with the use if JIT, the results from the shell short was not excactly what we were excpecting. There can be massive performance improvements but at the same time a problem can occur we did not excpect. So, when choosing wether to use `numba` compiler *JIT*, or maybe `sort()`, when solving a problem one should consider what the impact would be if the function does something else than expected. If the impact would be low and easily fixable, on can use the already defined functions. If the impact would be huge and very costly to fix, one should consider writing the code oneself.
# # Stack overflow and how to avoid it
#
# The last thing you should be aware of when writing algorithms is stack overflow. We will briefly discuss this problem and tell you how to avoid it.
#
# Local variables and parameters live on a thing called **stack**. The stack lives on the *top* of your adress space (memory cell for instance) and as it is being used, it is heading towards the *bottom* of your adress space (towards zero). The most common cause of a stack overflow is a bad recursive call. If your function does not contain the proper terminating condition (making your function to stop), the function will call itself forever. A stack overflow means that your function is demanding more space than it has dedicated. When this happens, you usually get an error message saying that the "maximum recursion is met", meaning that the process cannot access more space to find a solution. To solve this problem, go over your code and check whether you are using a proper terminating condition.
# In[7]:
#Stack overflow example
#define a function that recurs upon itself
def so():
return so()
#call the function
so()
#you should get an error of a maximum recursion