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()

1788356271.840584

import time
time.time()

1788356281.0076146

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

1.007502794265747

def myTimeIt(f):
    start=time()
    f()
    end=time()
    return end-start
    

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

0.03487253189086914

def myTimeIt1(f, count):
    totalTime=0
    for _ in range(count):
        start=time()
        f()
        end=time()
        totalTime+=(end-start)
        
    return  totalTime/count   #return the avg elapsed time for "count" calls

myTimeIt1(lambda: sum(range(10**6)),100000)

---------------------------------------------------------------------------
KeyboardInterrupt                         Traceback (most recent call last)
<ipython-input-12-b57a04a966d4> in <module>
----> 1 myTimeIt1(lambda: sum(range(10**6)),100000)

<ipython-input-11-98c0eb2971cd> in myTimeIt1(f, count)
      3     for _ in range(count):
      4         start=time()
----> 5         f()
      6         end=time()
      7         totalTime+=(end-start)

KeyboardInterrupt: 

2. Prelude: Timing list indexing

lst = [0] * 10**5

import timeit
timeit.timeit(stmt='lst[0]', globals=globals())

0.09256860000004963

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

0.08202890000029583

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

times[:10]

[1.849999989644857e-05,
 1.6899999991437653e-05,
 1.6599999980826396e-05,
 1.75999998646148e-05,
 2.4700000267330324e-05,
 1.6899999991437653e-05,
 1.699999984339229e-05,
 1.649999967412441e-05,
 1.6599999980826396e-05,
 2.7499999760038918e-05]

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

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

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):   #search for value x in unsorted lst, return index position of first find
    i=0
    while i<len(lst) and lst[i]!=x:
        i+=1
    # why did we leave the loop?   end of lst OR found item?
    if i==len(lst):
        return None
    else:
        return i

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 0x21d8996ae20>]

def index1(lst, x):   #search for value x in unsorted lst, return index position of first find
    i=0
    while i<len(lst) and lst[i]!=x:
        i+=1
    # why did we leave the loop?   end of lst OR found item?
    if i==len(lst):
        raise ValueError(x)
    else:
        return i

index1(lst, 99)

99

index1(lst, -1)

---------------------------------------------------------------------------
ValueError                                Traceback (most recent call last)
<ipython-input-35-9e4e3b7364c4> in <module>
----> 1 index1(lst, -1)

<ipython-input-30-f8ad93ca3c49> in index1(lst, x)
      5     # why did we leave the loop?   end of lst OR found item?
      6     if i==len(lst):
----> 7         raise ValueError(x)
      8     else:
      9         return i

ValueError: -1

def index1(lst, x):   #search for value x in unsorted lst, return index position of first find
    i=0
    while i<len(lst) and lst[i]!=x:
        i+=1
    # why did we leave the loop?   end of lst OR found item?
    if i<len(lst):
        return i
    raise ValueError(x)
        

index1(lst, 99)
index1(lst, -1)

99

---------------------------------------------------------------------------
ValueError                                Traceback (most recent call last)
<ipython-input-37-56979a5ba27a> in <module>
      1 index1(lst, 99)
----> 2 index1(lst, -1)

<ipython-input-36-31cd20671d45> in index1(lst, x)
      6     if i<len(lst):
      7         return i
----> 8     raise ValueError(x)
      9 

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!!!
    lowIndex=0
    highIndex=len(lst)-1
    
    while lowIndex<=highIndex:
       # print(lowIndex," ",highIndex)
        middleIndex=(lowIndex+highIndex)//2
        if lst[ middleIndex]== x:
            return  middleIndex
        elif lst[ middleIndex] < x:   # search the upper half
            lowIndex=middleIndex+1
        else:# search the lower half
            highIndex=middleIndex-1
            
#    raise ValueError(x)
    return -1

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

0   999
0   498
0   248
0   123
0   60
0   29
0   13
7   13

10

index(lst, 999)

0   999
500   999
750   999
875   999
938   999
969   999
985   999
993   999
997   999
999   999

999

index(lst, -1)

---------------------------------------------------------------------------
ValueError                                Traceback (most recent call last)
<ipython-input-41-893b85c8f574> in <module>
----> 1 index(lst, -1)

<ipython-input-38-416c81a4c0ec> in index(lst, x)
     13             highIndex=middleIndex-1
     14 
---> 15     raise ValueError(x)

ValueError: -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 0x21d89a065e0>]

import timeit
#lst = list(range(1000))  # [ 0 1 2 3 4 5 . . . . 998 999]
times = []
for size in range(1000, 100000, 100):
    lst = list(range(size))
    times.append(timeit.timeit(stmt='index(lst, -1)',
                               globals=globals(),
                               number=1000))

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

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

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 0x14a8ccae3d0>]

import timeit
times = []
for e in range(5, 20):
    lst = list(range(1,(2**e)+1))
    times.append(timeit.timeit(stmt='index(lst, {})'.format(2**(e-1)),
                               globals=globals(),
                               number=100000))
    
    # what is the middle item from 0 to 2^5, 0 to 31?  16   2^4
     # what is the middle item from 0 to 2^e,   2^(e-1)
    #stmt='index(lst, {})'.format(x), 
    

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

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

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)

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

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

def insertion_sort(lst):
    # outer loop to keep track of which item we are walking down  from index 1 to last index of lst
    for i in range(1, len(lst)):
        j = i
        # inner loop to do the walk it down, until I find where it goes or reach the index 0
        while j>=1 and lst[j]<lst[j-1]:
            #swap  lst[j] and lst[j-1]
            lst[j],lst[j-1] = lst[j-1], lst[j]
            j-=1
        # sometimes think about special processing depending on which reason for leaving the loop
            

insertion_sort(lst)

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

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

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 0x14a8cdc3370>]

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

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

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

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

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

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