## How to profile a program in Python

In this video we will see how cProfile (default Python library) can help you to get run-times from your Python program.

## Queue vs Python lists

In this video we will compare the performance of a simple Queue implemented directly into Python (no optimisations) with the default Python list.

Can it compare with it on performance?

This is where time complexity analysis come into the picture. A Queue insert and deletion is O(1) time complexity. A Python list used as a queue has O(n) time complexity.

But does the performance and run-time show the same? Here we compare the run-time by using cProfile in Python.

Check out my Course on Linked Lists, Stacks and Queues

### Find the Nearest Smaller Element on Left Side in an Array – Understand the Challenge to Solve it Efficiently

The Nearest Smaller Element problem explained:

Given an array (that is a list) of integers, for each element find all the nearest element smaller on the left side of it.

The naive solution has time complexity O(n^2). Can you solve it in O(n)? Well, you need to have a Stack to do that.

The naive solution is for each element to check all the elements on the left of it, to find the first one which is smaller.

The worst case run time for that would be O(n^2). For an array of length n, it would take: 0 + 1 + 2 + 3 + … + (n-1) comparisons. = (n-1)*n/2 = O(n^2) comparisons.

But with a stack we can improve that.

Check out my Course on Linked Lists, Stacks and Queues

## Overview

After this these steps you will be able to automate the process of posting on Facebook by a Python script. In this example I will show how it is done on a Facebook brand page, Learn Python With Rune.

What you need.

• A graph API token, which you by registering as a developer on facebook and creating an App there.
• Make a simple Python program using the facebook library

## Step 2: Create an App

You need to create an App to get the graph API token.

Under My Apps you press Create App.

Press the Manage Pages, Ads or Groups.

You enter App Display Name, which will be the name that is used when posting from this App. Hence, chose a name that you like people to see in the post.

Fill out your email (probably it is automatically there) and press Create App ID.

## Step 3: Create Graph API token

Under tools choose Graph API explorer

Ensure that the right Facebook App is chosen. Then under User or Page chose get Page Access Token.

Agree with that.

Then you will get back to this screen.

## Step 4: Prolong you graph API token

The graph API token is quite short lived, so you want to extend it.

Press the info at the graph API token.

Where you in the bottom will find Extend Access Token. Press that.

## Step 6: Install facebook-sdk library

To make you life easy in Python, you need to install the facebook-sdk library.

```pip install facebook-sdk
```

## Step 7: The Python magic

```import facebook

facebook_page_id = "" # insert you page ID here.
```

That’s it. Enjoy.

## The challenge

You have a quote and an image.

```    quote = "Mostly, when you see programmers, they aren’t doing anything.  One of the attractive things about programmers is that you cannot tell whether or not they are working simply by looking at them.  Very often they’re sitting there seemingly drinking coffee and gossiping, or just staring into space.  What the programmer is trying to do is get a handle on all the individual and unrelated ideas that are scampering around in his head."
quote_by = "Charles M. Strauss"

len(quote) = 430
```

The quote is long (430 chars) and the picture might be too bright to write in white text. Also, it will take time to find the right font size.

Can you automate that getting a result that fits the Twitter recommended picture size?

Notice the following.

• The picture is dimmed to make the white text easy readable.
• The font size is automatically adjusted to fit the picture.
• The picture is cropped to fit recommended Twitter size (1024 x 512).

If this is what you are looking for, then this will automate that.

## Step 1: Find your background picture and quote

In this tutorial I will use the background image and quote given above. But you can change that to your needs.

If you chose a shorter quote the font size will adjust accordingly.

Example given here.

Notice that the following.

• The font size of the “quoted by” (here Learn Python With Rune) is adjusted to not fill more that half of the picture width.
• You can modify the margins as you like – say you want more space between the text and the logo.

## Step 2: Install the PILLOW library

The what? Install the pillow library. You can find installation documentation in their docs.

Or just type

```pip install pillow
```

The pillow library is the PIL fork, and PIL is the Python Imaging Library. Basically, you need it for processing images.

You can find various fonts in font.google.com.

For this purpose, I used the Balsamiq Sans font.

I have located the bold and the italic version in a font folder.

## Step 4: The actual Python code

This is the fun part. The actual code.

```from PIL import Image, ImageDraw, ImageFont, ImageEnhance

# picture setup - it is set up for Twitter recommendations
WIDTH = 1024
HEIGHT = 512
# the margin are set by my preferences
MARGIN = 50
MARGIN_TOP = 50
MARGIN_BOTTOM = 150
LOGO_MARGIN = 25

# font variables
FONT_SIZES = [110, 100, 90, 80, 75, 70, 65, 60, 55, 50, 45, 40, 35, 30, 25, 20]
FONT_QUOTE = 'font-text'
FONT_QUOTED_BY = 'font-quoted-by'
FONT_SIZE = 'font-size'
FONT_QUOTED_BY_SIZE = 'font-quoted-by-size'

# Font colors
WHITE = 'rgb(255, 255, 255)'
GREY = 'rgb(200, 200, 200)'

# output text
OUTPUT_QUOTE = 'quote'
OUTPUT_QUOTED_BY = 'quoted-by'
OUTPUT_LINES = 'lines'

def text_wrap_and_font_size(output, font_style, max_width, max_height):
for font_size in FONT_SIZES:
output[OUTPUT_LINES] = []
font = ImageFont.truetype(font_style[FONT_QUOTE], size=font_size, encoding="unic")
output[OUTPUT_QUOTE] = " ".join(output[OUTPUT_QUOTE].split())
if font.getsize(output[OUTPUT_QUOTE]) <= max_width:
output[OUTPUT_LINES].append(output[OUTPUT_QUOTE])
else:
words = output[OUTPUT_QUOTE].split()
line = ""
for word in words:
if font.getsize(line + " " + word) <= max_width:
line += " " + word
else:
output[OUTPUT_LINES].append(line)
line = word
output[OUTPUT_LINES].append(line)
line_height = font.getsize('lp')

quoted_by_font_size = font_size
quoted_by_font = ImageFont.truetype(font_style[FONT_QUOTED_BY], size=quoted_by_font_size, encoding="unic")
while quoted_by_font.getsize(output[OUTPUT_QUOTED_BY]) > max_width//2:
quoted_by_font_size -= 1
quoted_by_font = ImageFont.truetype(font_style[FONT_QUOTED_BY], size=quoted_by_font_size, encoding="unic")

if line_height*len(output[OUTPUT_LINES]) + quoted_by_font.getsize('lp') < max_height:
font_style[FONT_SIZE] = font_size
font_style[FONT_QUOTED_BY_SIZE] = quoted_by_font_size
return True

# we didn't succeed find a font size that would match within the block of text
return False

def draw_text(image, output, font_style):

draw = ImageDraw.Draw(image)
lines = output[OUTPUT_LINES]
font = ImageFont.truetype(font_style[FONT_QUOTE], size=font_style[FONT_SIZE], encoding="unic")
line_height = font.getsize('lp')

y = MARGIN_TOP
for line in lines:
x = (WIDTH - font.getsize(line)) // 2
draw.text((x, y), line, fill=WHITE, font=font)

y = y + line_height

quoted_by = output[OUTPUT_QUOTED_BY]
quoted_by_font = ImageFont.truetype(font_style[FONT_QUOTED_BY], size=font_style[FONT_QUOTED_BY_SIZE], encoding="unic")
# position the quoted_by in the far right, but within margin
x = WIDTH - quoted_by_font.getsize(quoted_by) - MARGIN
draw.text((x, y), quoted_by, fill=GREY, font=quoted_by_font)
return image

def generate_image_with_quote(input_image, quote, quote_by, font_style, output_image):
image = Image.open(input_image)

# darken the image to make output more visible
enhancer = ImageEnhance.Brightness(image)
image = enhancer.enhance(0.5)

# resize the image to fit Twitter
image = image.resize((WIDTH, HEIGHT))

# set logo on image
logo_im = Image.open("pics/logo.png")
l_width, l_height = logo_im.size
image.paste(logo_im, (WIDTH - l_width - LOGO_MARGIN, HEIGHT - l_height - LOGO_MARGIN), logo_im)

output = {OUTPUT_QUOTE: quote, OUTPUT_QUOTED_BY: quote_by}

# we should check if it returns true, but it is ignorred here
text_wrap_and_font_size(output, font_style, WIDTH - 2*MARGIN, HEIGHT - MARGIN_TOP - MARGIN_BOTTOM)

# now it is time to draw the quote on our image and save it
image = draw_text(image, output, font_style)
image.save(output_image)

def main():
# setup input and output image
input_image = "pics/background.jpg"
output_image = "quote_of_the_day.png"

# setup font type
font_style = {FONT_QUOTE: "font/BalsamiqSans-Bold.ttf", FONT_QUOTED_BY: "font/BalsamiqSans-Italic.ttf"}

quote = "Mostly, when you see programmers, they aren’t doing anything.  One of the attractive things about programmers is that you cannot tell whether or not they are working simply by looking at them.  Very often they’re sitting there seemingly drinking coffee and gossiping, or just staring into space.  What the programmer is trying to do is get a handle on all the individual and unrelated ideas that are scampering around in his head."
# quote = "YOU ARE AWESOME!"
quote_by = "Charles M. Strauss"
# quote_by = "Learn Python With Rune"

# generates the quote image
generate_image_with_quote(input_image, quote, quote_by, font_style, output_image)

if __name__ == "__main__":
main()
```

Notice that you can change the input and output image names and locations in the main() function. Also, there you can setup the font for the quote and the quoted-by.

Finally, and obviously, you can change the quote and quote-by in the main() function.

## Step 1: Install the Pillow library

We need the Pillow library in order to manipulate images. It can be installed by using pip.

```pip install Pillow
```

This enables us to use PIL (Python Imaging Library) library.

You can browse fonts free to download from Google Font Library. In this example I use the Balsamic Sans.

Place the download in the same folder as you want to work from.

## Step 3: Find an awesome picture

I use Pexels to find free awesome pictures to use.

And place that image in your same location.

## Step 4: Create you Python program to add your awesome text

```from PIL import Image, ImageDraw, ImageFont

# Open the image (change name and location if needed)
image = Image.open('pics/background.jpg')
draw = ImageDraw.Draw(image)

# Import the font(change name and location if needed, also change font size if needed)
font = ImageFont.truetype('font/BalsamiqSans-Bold.ttf', size=200)
black = 'rgb(0, 0, 0)'  # black color

# Draw the text - change position if needed
message = "This is great!"
draw.text((1000, 200), message, fill=black, font=font)

# Draw the text - change position if needed
name = 'You are AWESOME!'
draw.text((1100, 500), name, fill=black, font=font)

image.save('greeting_card.png')

```

## What will you learn?

• What is a Substitution Cipher?
• How to implement the Substitution Cipher in Python
• Understand the key space of Substitution Cipher
• The weakness and how to break the Substitution Cipher

## What is a Substitution Cipher

Imagine you receive this message: IQL WPV WCVJQEV

What does it mean?

You were told it is a Substitution Cipher, but how will that help you?

First of all, we need to understand what a Substitution Cipher is. Basically, it is just rearranging the characters. That is every time you write an A, you exchange that with, say, Q. And B with G. C with, hey, let’s keep the C.

See the mapping in the picture below.

That seems pretty solid. Right?

But can we figure out what your message means?

First, let’s try to implement a Substitution Cipher.

## Implementing Substitution Cipher in Python

We will use the random library to generate random keys. We’ll get back to how many keys are there.

```import random

def generate_key():
alphabet = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
chars = list(alphabet)
key = {}
for c in alphabet:
key[c] = chars.pop(random.randint(0, len(chars) - 1))
return key

def print_key(key):
for c in "ABCDEFGHIJKLMNOPQRSTUVWXYZ":
print(c, key[c])

def encrypt(key, message):
cipher = ""
for c in message:
if c in key:
cipher += key[c]
else:
cipher += " "
return cipher

def get_decrypt_key(key):
dkey = {}
for k in key:
dkey[key[k]] = k
return dkey

key = generate_key()
print(key)
cipher = encrypt(key, "YOU ARE AWESOME")
print(cipher)
dkey = get_decrypt_key(key)
message = encrypt(dkey, cipher)
print(message)
```

Well, let’s understand the key-space. How secure is the Substitution Cipher?

## The key-space of the Substitution Cipher

Let’s examine how the keys are generated.

The first letter, A, can be mapped to 26 possibilities (including A itself). The next letter, B, can be mapped to 25 possibilities. The third letter, C, can be mapped to (difficult to guess) 24 possibilities. And so forth.

This generates a space of (read the large number in the picture above). That is right. It is more than 88 bits of security.

That is a lot.

88 bits of security? That is you need to try (more than) 309485009821345068724781056 possibilities.

A whole lot. And that, I promise you, should be considered secure.

But wait, Substitution Cipher is not used any more, why? Read on, and you will know in a moment.

## The weakness of Substitution Cipher

If the underlying language is English, then you can make a simple frequency analysis of how often the letters occur on average in English.

It turns out to be quite simple.

```letter_freq = {'a': 0.0817, 'b': 0.0150, 'c': 0.0278, 'd': 0.0425, 'e': 0.1270, 'f': 0.0223,
'g': 0.0202, 'h': 0.0609, 'i': 0.0697, 'j': 0.0015, 'k': 0.0077, 'l': 0.0403,
'm': 0.0241, 'n': 0.0675, 'o': 0.0751, 'p': 0.0193, 'q': 0.0010, 'r': 0.0599,
's': 0.0633, 't': 0.0906, 'u': 0.0276, 'v': 0.0098, 'w': 0.0236, 'x': 0.0015,
'y': 0.0197, 'z': 0.0007}
```

That is, the letter ‘a’ occurs 8.17% percent probability. ‘b’ with 1.5%. ‘c’ with 2.78%.

Hence, given the text: IQL WPV WCVJQEV

Well, we are out of luck, because it is too short to have any frequency analysis to have any significance.

But the following text.

```lrvmnir bpr sumvbwvr jx bpr lmiwv yjeryrkbi jx qmbm wi
bpr xjvni mkd ymibrut jx irhx wi bpr riirkvr jx
ymbinlmtmipw utn qmumbr dj w ipmhh but bj rhnvwdmbr bpr
yjeryrkbi jx bpr qmbm mvvjudwko bj yt wkbrusurbmbwjk
lmird jk xjubt trmui jx ibndt
wb wi kjb mk rmit bmiq bj rashmwk rmvp yjeryrkb mkd wbi
iwokwxwvmkvr mkd ijyr ynib urymwk nkrashmwkrd bj ower m
vjyshrbr rashmkmbwjk jkr cjnhd pmer bj lr fnmhwxwrd mkd
wkiswurd bj invp mk rabrkb bpmb pr vjnhd urmvp bpr ibmbr
jx rkhwopbrkrd ywkd vmsmlhr jx urvjokwgwko ijnkdhrii
ijnkd mkd ipmsrhrii ipmsr w dj kjb drry ytirhx bpr xwkmh
mnbpjuwbt lnb yt rasruwrkvr cwbp qmbm pmi hrxb kj djnlb
bpmb bpr xjhhjcwko wi bpr sujsru msshwvmbwjk mkd
wkbrusurbmbwjk w jxxru yt bprjuwri wk bpr pjsr bpmb bpr
riirkvr jx jqwkmcmk qmumbr cwhh urymwk wkbmvb
```

This has enough letters to make an analysis of the letters. Let’s try.

```cipher = """lrvmnir bpr sumvbwvr jx bpr lmiwv yjeryrkbi jx qmbm wi
bpr xjvni mkd ymibrut jx irhx wi bpr riirkvr jx
ymbinlmtmipw utn qmumbr dj w ipmhh but bj rhnvwdmbr bpr
yjeryrkbi jx bpr qmbm mvvjudwko bj yt wkbrusurbmbwjk
lmird jk xjubt trmui jx ibndt
wb wi kjb mk rmit bmiq bj rashmwk rmvp yjeryrkb mkd wbi
iwokwxwvmkvr mkd ijyr ynib urymwk nkrashmwkrd bj ower m
vjyshrbr rashmkmbwjk jkr cjnhd pmer bj lr fnmhwxwrd mkd
wkiswurd bj invp mk rabrkb bpmb pr vjnhd urmvp bpr ibmbr
jx rkhwopbrkrd ywkd vmsmlhr jx urvjokwgwko ijnkdhrii
ijnkd mkd ipmsrhrii ipmsr w dj kjb drry ytirhx bpr xwkmh
mnbpjuwbt lnb yt rasruwrkvr cwbp qmbm pmi hrxb kj djnlb
bpmb bpr xjhhjcwko wi bpr sujsru msshwvmbwjk mkd
wkbrusurbmbwjk w jxxru yt bprjuwri wk bpr pjsr bpmb bpr
riirkvr jx jqwkmcmk qmumbr cwhh urymwk wkbmvb"""

alphabet = "abcdefghijklmnopqrstuvwxyz"
freq = {}
for c in alphabet:
freq[c] = 0

cnt = 0
for c in cipher:
if c in alphabet:
freq[c] += 1
cnt += 1

for c in freq:
freq[c] = round(freq[c]/cnt, 4)

print(freq)
```

Will give you the following output.

```{'a': 0.0077, 'b': 0.1053, 'c': 0.0077, 'd': 0.0356, 'e': 0.0077, 'f': 0.0015, 'g': 0.0015, 'h': 0.0356, 'i': 0.0635, 'j': 0.0743, 'k': 0.0759, 'l': 0.0124, 'm': 0.096, 'n': 0.0263, 'o': 0.0108, 'p': 0.0464, 'q': 0.0108, 'r': 0.13, 's': 0.0263, 't': 0.0201, 'u': 0.0372, 'v': 0.0341, 'w': 0.0728, 'x': 0.031, 'y': 0.0294, 'z': 0.0}
```

This gives you some hints on how the letters are mapped.

## What will we cover?

• Understand what Caesar Cipher is
• Implement Caesar Cipher in Python
• Understand the weakness of Caesar Cipher

## What is Caesar Cipher

Caesar Cipher is a simple substitution cipher, which is limited to only shift the characters by fix number.

Imagine you got the message: BRX DUH DZHVRPH. What to make out of it. Makes no sense. Just ignore it, right?

Well, for the untrained eye, yes, ignore it. But why would anyone bother sending you that message? Aren’t you curious?

I would be. Let’s say your friend told you it was a Caesar Cipher with a 3-key shift. What does that mean?

In the picture below, you can see how the letters are shifted from the green letters (plain text), to the encrypted red letters (cipher text). As an example, A is encrypted to D, and B is encrypted to E, and so forth.

By using that strategy, you can also figure out that a cipher B (red letters) maps to the plain Y (green letters). A cipher R maps to the plain O. And so forth. That results in that your secret message decrypts to YOU ARE AWESOME.

What a nice message to get.

## Implementation of Caesar Cipher in Python

Below is an example of how you could implement the Caesar Cipher in Python.

```def generate_key(n):
chars = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
key = {}
cnt = 0
for c in chars:
key[c] = chars[(cnt + n) % len(chars)]
cnt += 1
return key

def encrypt(key, message):
cipher = ""
for c in message:
if c in key:
cipher += key[c]
else:
cipher += c
return cipher

def get_decrypt_key(key):
dkey = {}
for k in key:
dkey[key[k]] = k
return dkey

key = generate_key(3)
dkey = generate_key(23)
cipher = encrypt(key, "YOU ARE AWESOME")
print(cipher)
message = encrypt(dkey, cipher)
print(message)
dkey = get_decrypt_key(key)
print(encrypt(dkey, cipher))
```

There are some things to notice. First of all, the generate_key function comes in handy, when we extend our cipher function to the more general substitution cipher.

Also, notice, that encryption and decryption are done with the same function, just different keys. The decryption key of key-3 is key-23.

See that you can actually calculate the decryption key quite nice, as done in the get_decrypt_key function, which can be used if this is extended to a general substitution cipher.

## How to de-cipher a Caesar Cipher message

Image you had received the message BRX DUH DZHVRPH, but didn’t know the key. What to do?

No worries, there is a way to solve that problem efficiently.

The scenario is that Alice wants to send Bob a secret message, but someone (you) get’s a copy of the message (and you are called Eve).

The secrecy of the message was intended to be, that you (Eve) does not know the Algorithm (how the encryption is done). That might seems naive today, but back in the time of Caesar, this was the state of the art, and people were not that knowledgable about the art of cryptography.

But you are in luck. Yes, I am talking to you Eve.

You know the Algorithm and you are soon to figure out, that the key space is quite small. Actually it only contains 26 possible keys.

That is in the reach of you manually trying out all possible keys.

But you are in more luck, because you realised that you also have Python. So let’s try to fix it in Python.

```def generate_key(n):
chars = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
key = {}
cnt = 0
for c in chars:
key[c] = chars[(cnt + n) % len(chars)]
cnt += 1
return key

def encrypt(key, message):
cipher = ""
for c in message:
if c in key:
cipher += key[c]
else:
cipher += c
return cipher

cipher = "BRX DUH DZHVRPH"
for i in range(26):
key = generate_key(i)
message = encrypt(key, cipher)
print(message)
```

That will generate the following output.

```CSY EVI EAIWSQI
DTZ FWJ FBJXTRJ
EUA GXK GCKYUSK
FVB HYL HDLZVTL
GWC IZM IEMAWUM
HXD JAN JFNBXVN
IYE KBO KGOCYWO
JZF LCP LHPDZXP
KAG MDQ MIQEAYQ
LBH NER NJRFBZR
MCI OFS OKSGCAS
NDJ PGT PLTHDBT
OEK QHU QMUIECU
PFL RIV RNVJFDV
QGM SJW SOWKGEW
RHN TKX TPXLHFX
SIO ULY UQYMIGY
TJP VMZ VRZNJHZ
UKQ WNA WSAOKIA
VLR XOB XTBPLJB
WMS YPC YUCQMKC
XNT ZQD ZVDRNLD
YOU ARE AWESOME
ZPV BSF BXFTPNF
AQW CTG CYGUQOG
```

That was awesome right.

## Conclusion

The security of Caesar Cipher was by keeping the Algorithm secret. That approach to security is not used anymore. Kerckhoffs’ Principle states that the adversary (Eve) should not be able to break the cipher even when she knows the Algorithm.

## What will we cover?

• What is Bubble sort and how does it work?
• How to implement it in Python
• How to evaluate the time complexity of the Bubble sort algorithm

## What is Bubble sort and how does it work?

In this video the Bubble sort algorithm is explained. On a high level, it takes an unsorted list and returns it sorted.

## How to implement Bubble sort in Python

Well, notice the above description. It is straight forward and simple to implement. That is one of the beauties of the algorithm. Simple to understand. Simple to implement.

```def bubble_sort(my_list):
for i in range(len(my_list), 1, -1):
for j in range(1, i):
if my_list[j-1] > my_list[j]:
my_list[j-1], my_list[j] = my_list[j], my_list[j-1]
```

An simple illustration of how you can use it.

```import random

def generate_random_list(n):
my_list = []
for i in range(n):
my_list.append(random.randint(0, n))
return my_list

def bubble_sort(my_list):
for i in range(len(my_list), 1, -1):
for j in range(1, i):
if my_list[j-1] > my_list[j]:
my_list[j-1], my_list[j] = my_list[j], my_list[j-1]

my_list = generate_random_list(20)
print(my_list)
bubble_sort(my_list)
print(my_list)

```

## Evaluating the performance of Bubble sort

First of the algorithm has two for-loops. An outer and an inner for-loop. With an input of a list of length N, the loops will be iterated the following number of times.

• Outer for-loop: N times
• Inner for-loop: N-1 + N-2 + N-3 + … + 1 + 0 times

Knowing the formula

• N-1 + N-2 + … + 1 + 0 = (N-1)*N/2

We can add that the time complexity of Bubble sort is O(n^2).

But let’s try to experiment with real running data, to see if we can confirm that complexity.

To get run-times from the algorithm the cProfile library comes in handy. It is easy to use and gives good insights. A simple way to get run-times is to set it like this.

```import random
import cProfile

def generate_random_list(n):
return [random.randint(0, 4*n) for i in range(n)]

def bubble_sort(my_list):
for i in range(len(my_list), 1, -1):
for j in range(1, i):
if my_list[j-1] > my_list[j]:
my_list[j-1], my_list[j] = my_list[j], my_list[j-1]

def profile_bubble_sort(n):
my_list = generate_random_list(n)
bubble_sort(my_list)

cProfile.run("profile_bubble_sort(10000)")
```

It will result in an output in the following manner.

```         56372 function calls in 11.056 seconds

Ordered by: standard name

ncalls  tottime  percall  cumtime  percall filename:lineno(function)
1    0.000    0.000   11.056   11.056 <string>:1(<module>)
1    0.000    0.000   11.055   11.055 BubbleSortProfiling.py:16(profile_bubble_sort)
1    0.000    0.000    0.034    0.034 BubbleSortProfiling.py:5(generate_random_list)
1    0.008    0.008    0.034    0.034 BubbleSortProfiling.py:6(<listcomp>)
1   11.021   11.021   11.021   11.021 BubbleSortProfiling.py:9(bubble_sort)
10000    0.010    0.000    0.022    0.000 random.py:200(randrange)
10000    0.005    0.000    0.027    0.000 random.py:244(randint)
10000    0.007    0.000    0.012    0.000 random.py:250(_randbelow_with_getrandbits)
1    0.000    0.000   11.056   11.056 {built-in method builtins.exec}
1    0.000    0.000    0.000    0.000 {built-in method builtins.len}
10000    0.001    0.000    0.001    0.000 {method 'bit_length' of 'int' objects}
1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}
16364    0.003    0.000    0.003    0.000 {method 'getrandbits' of '_random.Random' objects}
```

You get the time spend in Bubble sort by looking the highlighted line. In the column cumtime you get the time spend in total in the function.

By collecting the run-time for various sizes of lists, we get the following graph.

The graph has a O(n^2) growth as expected.

### How to Implement a Stack in Python and Check the Run-time Performance

• What is a Stack – a short introduction
• How to implement a Stack in Python
• Investigate the run-time performance

## What is a Stack

A Stack is a useful concept that is used in daily life, and hence, a concept that is important to understand and master as a programmer.

To understand Stacks just think of a stack of plates. There are two main operations you can do. First, you can add a plate on top of the stack. That operation is called push adds the element on top of the stack. Second, you can remove the top plate of the stack. That operation is called pop, and returns the top element of the stack.

In the diagram below a Stack is pictured. It contains of a Stack of element on the left side. The operation push of the element 03 is executed and results is pictured on the right side. Notice, that the push operation puts the element on top of the stack.

Below the operation pop is executed. Notice, that the pop operation takes from the top of the stack.

## Implementation of a Stack in Python

It is a good idea to have a helper class Node that represents the elements on the stack.

```class Node:
def __init__(self, element=None, next_node=None):
self.element = element
self.next_node = next_node
```

The actual functionality of the Stack is kept in a Stack class.

```class Stack:
def __init__(self):
self.stack = None

def push(self, element):
self.stack = Node(element, self.stack)

def pop(self):
element = self.stack.element
self.stack = self.stack.next_node
return element

def is_empty(self):
return self.stack is None

```

Now you can use your stack. Like the example below.

```s = Stack()
for i in range(5):
s.push(i)
while not s.is_empty():
print(s.pop())

```

Will give the following output.

```4
3
2
1
0
```

Notice the order of the element being removed from the stack by pop.

## Run-time Performance

If we look at how the stack perform in order of the data size. To investigate the run-time performance the cProfile library is a good choice and simple to use. The following piece of code will help you investigate the performance.

```import cProfile

def profile_stack(n):
s = Stack()
for i in range(n):
s.push(i)
while not s.is_empty():
s.pop()

cProfile.run("profile_stack(100000)")
```

See the following graph.

As you see, the push and pop operations are constant, O(1), resulting in a linear performance of n push and pop operations as in the above experiment.