Searching, Sorting, and Timing

Agenda

1. Timing
2. Prelude: Timing list indexing
3. Linear search
4. Binary search
5. Insertion sort

from IPython.core.interactiveshell import InteractiveShell
InteractiveShell.ast_node_interactivity = "all"

1. Timing

import time
time.time()

1738593557.3514287

import time
time.time()

1738593569.9776237

from time import time, sleep
start = time()
sleep(1)
end = time()
print(end - start)

1.0161705017089844

from time import time, sleep
start = time()
sum(range(10**6))
end = time()
print(end - start)

499999500000

0.05998063087463379

def myTimer(f):   # can add a loop 10000 times and divide the result by 10000
    start = time()
    f()
    end = time()
    return (end - start)

myTimer(lambda:sum(range(10**6)) )

0.046653032302856445

import timeit
timeit.timeit('sum(range(10**6))',number=100)

3.3793077999998786

timeit.timeit(setup='import random ; ',stmt='lst=[random.random() for _ in range(100)]; sorted(lst)')

13.229771899999832

---------------------------------------------------------------------------
NameError                                 Traceback (most recent call last)
<ipython-input-19-b5cada25ed2a> in <module>
----> 1 lst

NameError: name 'lst' is not defined

2. Prelude: Timing list indexing

lst = [0] * 10**5

import timeit
timeit.timeit(stmt='lst[0]', globals=globals())   
#globals means timeit can access lst created other in notebook

0.06350879999990866

timeit.timeit(stmt='lst[10**5-1]', globals=globals())

0.06539629999997487

times = [timeit.timeit(stmt='lst[{}]'.format(i), 
                       globals=globals(), 
                       number=100) 
         for i in range(10**5)]

times[:10]

[1.2799999694834696e-05,
 1.1500000255182385e-05,
 1.13999999484804e-05,
 1.13999999484804e-05,
 1.1900000117748277e-05,
 1.1699999959091656e-05,
 1.1300000096525764e-05,
 1.13999999484804e-05,
 1.1300000096525764e-05,
 1.1700000413839007e-05]

%matplotlib inline
import matplotlib.pyplot as plt
plt.plot(times, 'ro')
plt.show()

[<matplotlib.lines.Line2D at 0x182df433e80>]

Observation: accessing an element in a list by index takes a constant amount of time, regardless of position.

How? A Python list uses an array as its underlying data storage mechanism. To access an element in an array, the interpreter:

1. Computes an offset into the array by multiplying the element's index by the size of each array entry (which are uniformly sized, since they are merely references to the actual elements)
2. Adds the offset to the base address of the array

3. Linear Search

Task: to locate an element with a given value in a list (array).

def index(lst, x):  # unsorted list lst
    i=0
    while i<len(lst) and lst[i]!=x:
        i+=1
    if i<len(lst):
        return i
    else:
        return None

lst = list(range(100))
index(lst, 10)

10

index(lst, 99)

99

index(lst, -1)

import timeit
lst = list(range(1000))
times = [timeit.timeit(stmt='index(lst, {})'.format(x), 
                       globals=globals(), 
                       number=100)
         for x in range(1000)]

import matplotlib.pyplot as plt
plt.plot(times, 'ro')
plt.show()

[<matplotlib.lines.Line2D at 0x182db7a0790>]

def index(lst, x):  # unsorted list lst
    i=0
    while i<len(lst) and lst[i]!=x:
        i+=1
    if i<len(lst):
        return i
    else:
        raise ValueError(x)

index(lst, 10)
index(lst, 999)
index(lst, -1)

10

999

---------------------------------------------------------------------------
ValueError                                Traceback (most recent call last)
<ipython-input-48-fb70efbd77c9> in <module>
      1 index(lst, 10)
      2 index(lst, 999)
----> 3 index(lst, -1)

<ipython-input-47-59aeed86768c> in index(lst, x)
      6         return i
      7     else:
----> 8         raise ValueError(x)

ValueError: -1

4. Binary search

Task: to locate an element with a given value in a list (array) whose contents are sorted in ascending order.

def index(lst, x):       # assume that lst is sorted!!!
    #   start                           end
    start=0   # start end mid are index positions
    end=len(lst)-1
    mid = (start+end)//2
    
    while (start<=end):  # if start passes end, it must be a not found
        if lst[mid]==x:
            return mid
        else:
            if lst[mid]>x:   #look at the lower half
                end=mid-1
            else:
                start=mid+1
            mid = (start+end)//2
                
    #raise ValueError(x)
    return None

lst = list(range(1000))
index(lst, 10)

10

index(lst, 999)

999

index(lst, -1)

import timeit
lst = list(range(1000))
times = [timeit.timeit(stmt='index(lst, {})'.format(x), 
                       globals=globals(), 
                       number=1000)
         for x in range(1000)]

import matplotlib.pyplot as plt
plt.plot(times, 'ro')
plt.show()

[<matplotlib.lines.Line2D at 0x182db7c9580>]

import timeit
times = []
for size in range(1000, 100000, 100):
    lst = list(range(size))
    times.append(timeit.timeit(stmt='index(lst, -1)',   # worst case, not found
                               globals=globals(),
                               number=1000))

import matplotlib.pyplot as plt
plt.plot(times, 'ro')
plt.show()

[<matplotlib.lines.Line2D at 0x182dca60f40>]

import timeit
times = []
for e in range(5, 20):
    lst = list(range(2**e))
    times.append(timeit.timeit(stmt='index(lst, -1)',
                               globals=globals(),
                               number=100000))

import matplotlib.pyplot as plt
plt.plot(times, 'ro')
plt.show()

[<matplotlib.lines.Line2D at 0x182db8736a0>]

5. Insertion sort

Task: to sort the values in a given list (array) in ascending order.

import random
lst = list(range(1000))
random.shuffle(lst)

def insertion_sort(lst):
    for i in range(len(lst)):   # 0 to length-1   COULD CHANGE TO range(1,)
        current=i
        # walk it down
        while current>0 and lst[current]<lst[current-1]:
            lst[current],lst[current-1]=lst[current-1],lst[current]
            current-=1              
    
    
    

import matplotlib.pyplot as plt
plt.plot(lst, 'ro')
plt.show()

[<matplotlib.lines.Line2D at 0x1bc90e16a00>]

insertion_sort(lst)

plt.plot(lst, 'ro')
plt.show()

[<matplotlib.lines.Line2D at 0x1bc911b66d0>]

import timeit
import random
times = [timeit.timeit(stmt='insertion_sort(lst)',
                       setup='lst=list(range({})); random.shuffle(lst)'.format(size),
                       globals=globals(),
                       number=1)
         for size in range(100, 5000, 250)]

plt.plot(times, 'ro')
plt.show()

[<matplotlib.lines.Line2D at 0x1bc91209eb0>]

import timeit   # best case
import random
times = [timeit.timeit(stmt='insertion_sort(lst)',
                       setup='lst=list(range({}));'.format(size),
                       globals=globals(),
                       number=100)
         for size in range(100, 5000, 250)]

plt.plot(times, 'ro')
plt.show()

[<matplotlib.lines.Line2D at 0x1bc912c8fd0>]

list(range(10,0,-1))

[10, 9, 8, 7, 6, 5, 4, 3, 2, 1]

import timeit   #worst case
import random
times = [timeit.timeit(stmt='insertion_sort(lst)',
                       setup='lst=list(range({},0,-1));'.format(size),
                       globals=globals(),
                       number=10)
         for size in range(100, 5000, 250)]

plt.plot(times, 'ro')
plt.show()

[<matplotlib.lines.Line2D at 0x1bc913482b0>]

def bubbleSort(lst):   # best case and worst case O(n^2)
    for stopIndex in range(len(lst)-1,0,-1):  # n n-1 n-2 . . . . 3 2 1
        #print(lst)
        for i in range(stopIndex):   # 0 1 2 3 . . . stopIndex-1
            if lst[i]>lst[i+1]:
                lst[i],lst[i+1]=lst[i+1],lst[i]                

import random
lst = list(range(1000))
random.shuffle(lst)
bubbleSort(lst)
plt.plot(lst, 'ro')
plt.show()

[<matplotlib.lines.Line2D at 0x1bc91457b80>]

def bubbleSort(lst):  #improvement, best case O(n)
    # get out of the for loop if swap==false
    swap=True
#    for stopIndex in range(len(lst)-1,-1):,0  # n n-1 n-2 . . . . 3 2 1
    stopIndex=len(lst)-1
    while swap and stopIndex>0:
        swap=False
        for i in range(stopIndex):   # 0 1 2 3 . . . stopIndex-1
            if lst[i]>lst[i+1]:
                lst[i],lst[i+1]=lst[i+1],lst[i]
                swap=True
        stopIndex-=1

import random
lst = list(range(1000))
random.shuffle(lst)
bubbleSort(lst)
plt.plot(lst, 'ro')
plt.show()

[<matplotlib.lines.Line2D at 0x1bc914c1370>]