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

1757511707.1047459

import time
time.time()

1757511715.5001187

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

1.01558518409729

start = time()
sum(range(10**6))
end = time()
print(end - start)

499999500000

0.05842185020446777

from time import time, sleep
def myTimer(f):
    start = time()
    f()
    end = time()
    return end-start

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

0.04969072341918945

from timeit import timeit
timeit(lambda: sum(range(10**6)))

---------------------------------------------------------------------------
KeyboardInterrupt                         Traceback (most recent call last)
<ipython-input-5-c797700594a6> in <module>
      1 from timeit import timeit
----> 2 timeit(lambda: sum(range(10**6)))

~\anaconda3\lib\timeit.py in timeit(stmt, setup, timer, number, globals)
    231            number=default_number, globals=None):
    232     """Convenience function to create Timer object and call timeit method."""
--> 233     return Timer(stmt, setup, timer, globals).timeit(number)
    234 
    235 def repeat(stmt="pass", setup="pass", timer=default_timer,

~\anaconda3\lib\timeit.py in timeit(self, number)
    175         gc.disable()
    176         try:
--> 177             timing = self.inner(it, self.timer)
    178         finally:
    179             if gcold:

~\anaconda3\lib\timeit.py in inner(_it, _timer, _stmt)

KeyboardInterrupt: 

from timeit import timeit
timeit(lambda: sum(range(10**6)),number=10)

0.4911172999999849

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

# globals allows timeit to reference any variables from the jupyter notebook

0.001134700000079647

2. Prelude: Timing list indexing

lst = [0] * 10**5

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

0.07848869999997987

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

0.07104440000000523

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

times[:10]

[2.779999999802385e-05,
 2.880000010918593e-05,
 2.5400000026820635e-05,
 1.44999999065476e-05,
 1.4000000078340236e-05,
 1.3899999999011925e-05,
 1.4500000020234438e-05,
 1.4100000043981709e-05,
 1.3899999999011925e-05,
 1.4299999975264654e-05]

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

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):   # we want to return index position
    # therefore we need an index on our loop (NOT for z in lst)
    for i in range(len(lst)):  # i is valid indexs in the lst
        if lst[i]==x:
            return i
    # if we exit the loop, thats a not found
    raise ValueError(x)      
    

lst = list(range(100))   # values match the index
index(lst, 10)

10

index(lst, 99)

99

index(lst, -1)

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

<ipython-input-22-e2a6a9e220c1> in index(lst, x)
      5             return i
      6     # if we exit the loop, thats a not found
----> 7     raise ValueError(x)
      8 

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

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!!!
    #  find mid index as (startIndex+endIndex)//2
    # startIndex and endIndex define the range of the current problem
    startIndex=0
    endIndex=len(lst)-1
    
    while (startIndex <=endIndex):  # I stillhave items I have not checked yet
    #    print(startIndex, " ", endIndex)
        midIndex=(startIndex+endIndex)//2
        if lst[midIndex]==x:
            return midIndex
        elif lst[midIndex]<x: #  i can elimiate the left part and work on the right part
            startIndex=midIndex+1
        else:    #  i can elimiate the right part and work on the left part
            endIndex=midIndex-1
    # do it again
    raise ValueError(x)
        

lst = list(range(1000))  # list index value is equal to the actual value
# lst is sorted
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)

0   999
0   498
0   248
0   123
0   60
0   29
0   13
0   5
0   1

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

<ipython-input-34-2cae5ffd9499> in index(lst, x)
     16             endIndex=midIndex-1
     17     # do it again
---> 18     raise ValueError(x)
     19 

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

def index(lst, x):
    # assume that lst is sorted!!!
    #  find mid index as (startIndex+endIndex)//2
    # startIndex and endIndex define the range of the current problem
    startIndex=0
    endIndex=len(lst)-1
    
    while (startIndex <=endIndex):  # I stillhave items I have not checked yet
    #    print(startIndex, " ", endIndex)
        midIndex=(startIndex+endIndex)//2
        if lst[midIndex]==x:
            return midIndex
        elif lst[midIndex]<x: #  i can elimiate the left part and work on the right part
            startIndex=midIndex+1
        else:    #  i can elimiate the right part and work on the left part
            endIndex=midIndex-1
    # do it again
#    raise ValueError(x)
    return None

import timeit
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()
# plotting not found on larger and larger lists
# faster than linear   logarithmic

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()
# x axis is growing exponential 2^e, the runtime is growing linear
#therefore the binary search index is logarithmic

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)

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

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

def bubble_sort(lst):
    # outer loop   "to"  range  len(list)-1   downto  1
    #   inner loop does the bubble from item 0 to item "to"
    #       if the two items I am looking at are out of order, swap
    for to in range(len(lst)-1, 0, -1):
        for i in range(0, to):   # final index is "to"-1
            if (lst[i]>lst[i+1]):
                lst[i],lst[i+1]=lst[i+1],lst[i]

bubble_sort(lst)

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

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

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

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

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

times   # bubble sort experimental is n^2

[5.099999725644011e-06,
 0.007293099999969854,
 0.021216999999978725,
 0.0326521000001776,
 0.05546830000002956,
 0.0846345999998448,
 0.12189660000012736,
 0.16511300000001938,
 0.22187490000032994,
 0.2814578000002257,
 0.34926809999979014,
 0.4388603000002149,
 0.5755694999998013,
 0.6070758000000751,
 0.6781385999997838,
 0.7580864999999903,
 0.8719178000001193,
 0.9870993999998063,
 1.085393099999692,
 1.244017100000292,
 1.374317300000257,
 1.539512299999842,
 1.5970680999998876,
 1.7979765999998563,
 1.9815366000002541]

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

def insertion_sort(lst):
    # for every item from 1 to len(lst)-1
    #     walk it down
    for i in range(1, len(lst)):
        j=i
        while j>0 and lst[j-1]>lst[j]:   
            # on sorted data, inner loop never entered   linear growth
            # on random data, quadratic growth (n^2)
            # on reverse sorted, insertion sort does the most amount of work
            #  quadratic growth (n^2)
            lst[j],lst[j-1]=lst[j-1],lst[j]
            j-=1

insertion_sort(lst)

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

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

lst

[0,
 1,
 2,
 3,
 4,
 5,
 6,
 7,
 8,
 9,
 10,
 11,
 12,
 13,
 14,
 15,
 16,
 17,
 18,
 19,
 20,
 21,
 22,
 23,
 24,
 25,
 26,
 27,
 28,
 29,
 30,
 31,
 32,
 33,
 34,
 35,
 36,
 37,
 38,
 39,
 40,
 41,
 42,
 43,
 44,
 45,
 46,
 47,
 48,
 49,
 50,
 51,
 52,
 53,
 54,
 55,
 56,
 57,
 58,
 59,
 60,
 61,
 62,
 63,
 64,
 65,
 66,
 67,
 68,
 69,
 70,
 71,
 72,
 73,
 74,
 75,
 76,
 77,
 78,
 79,
 80,
 81,
 82,
 83,
 84,
 85,
 86,
 87,
 88,
 89,
 90,
 91,
 92,
 93,
 94,
 95,
 96,
 97,
 98,
 99,
 100,
 101,
 102,
 103,
 104,
 105,
 106,
 107,
 108,
 109,
 110,
 111,
 112,
 113,
 114,
 115,
 116,
 117,
 118,
 119,
 120,
 121,
 122,
 123,
 124,
 125,
 126,
 127,
 128,
 129,
 130,
 131,
 132,
 133,
 134,
 135,
 136,
 137,
 138,
 139,
 140,
 141,
 142,
 143,
 144,
 145,
 146,
 147,
 148,
 149,
 150,
 151,
 152,
 153,
 154,
 155,
 156,
 157,
 158,
 159,
 160,
 161,
 162,
 163,
 164,
 165,
 166,
 167,
 168,
 169,
 170,
 171,
 172,
 173,
 174,
 175,
 176,
 177,
 178,
 179,
 180,
 181,
 182,
 183,
 184,
 185,
 186,
 187,
 188,
 189,
 190,
 191,
 192,
 193,
 194,
 195,
 196,
 197,
 198,
 199,
 200,
 201,
 202,
 203,
 204,
 205,
 206,
 207,
 208,
 209,
 210,
 211,
 212,
 213,
 214,
 215,
 216,
 217,
 218,
 219,
 220,
 221,
 222,
 223,
 224,
 225,
 226,
 227,
 228,
 229,
 230,
 231,
 232,
 233,
 234,
 235,
 236,
 237,
 238,
 239,
 240,
 241,
 242,
 243,
 244,
 245,
 246,
 247,
 248,
 249,
 250,
 251,
 252,
 253,
 254,
 255,
 256,
 257,
 258,
 259,
 260,
 261,
 262,
 263,
 264,
 265,
 266,
 267,
 268,
 269,
 270,
 271,
 272,
 273,
 274,
 275,
 276,
 277,
 278,
 279,
 280,
 281,
 282,
 283,
 284,
 285,
 286,
 287,
 288,
 289,
 290,
 291,
 292,
 293,
 294,
 295,
 296,
 297,
 298,
 299,
 300,
 301,
 302,
 303,
 304,
 305,
 306,
 307,
 308,
 309,
 310,
 311,
 312,
 313,
 314,
 315,
 316,
 317,
 318,
 319,
 320,
 321,
 322,
 323,
 324,
 325,
 326,
 327,
 328,
 329,
 330,
 331,
 332,
 333,
 334,
 335,
 336,
 337,
 338,
 339,
 340,
 341,
 342,
 343,
 344,
 345,
 346,
 347,
 348,
 349,
 350,
 351,
 352,
 353,
 354,
 355,
 356,
 357,
 358,
 359,
 360,
 361,
 362,
 363,
 364,
 365,
 366,
 367,
 368,
 369,
 370,
 371,
 372,
 373,
 374,
 375,
 376,
 377,
 378,
 379,
 380,
 381,
 382,
 383,
 384,
 385,
 386,
 387,
 388,
 389,
 390,
 391,
 392,
 393,
 394,
 395,
 396,
 397,
 398,
 399,
 400,
 401,
 402,
 403,
 404,
 405,
 406,
 407,
 408,
 409,
 410,
 411,
 412,
 413,
 414,
 415,
 416,
 417,
 418,
 419,
 420,
 421,
 422,
 423,
 424,
 425,
 426,
 427,
 428,
 429,
 430,
 431,
 432,
 433,
 434,
 435,
 436,
 437,
 438,
 439,
 440,
 441,
 442,
 443,
 444,
 445,
 446,
 447,
 448,
 449,
 450,
 451,
 452,
 453,
 454,
 455,
 456,
 457,
 458,
 459,
 460,
 461,
 462,
 463,
 464,
 465,
 466,
 467,
 468,
 469,
 470,
 471,
 472,
 473,
 474,
 475,
 476,
 477,
 478,
 479,
 480,
 481,
 482,
 483,
 484,
 485,
 486,
 487,
 488,
 489,
 490,
 491,
 492,
 493,
 494,
 495,
 496,
 497,
 498,
 499,
 500,
 501,
 502,
 503,
 504,
 505,
 506,
 507,
 508,
 509,
 510,
 511,
 512,
 513,
 514,
 515,
 516,
 517,
 518,
 519,
 520,
 521,
 522,
 523,
 524,
 525,
 526,
 527,
 528,
 529,
 530,
 531,
 532,
 533,
 534,
 535,
 536,
 537,
 538,
 539,
 540,
 541,
 542,
 543,
 544,
 545,
 546,
 547,
 548,
 549,
 550,
 551,
 552,
 553,
 554,
 555,
 556,
 557,
 558,
 559,
 560,
 561,
 562,
 563,
 564,
 565,
 566,
 567,
 568,
 569,
 570,
 571,
 572,
 573,
 574,
 575,
 576,
 577,
 578,
 579,
 580,
 581,
 582,
 583,
 584,
 585,
 586,
 587,
 588,
 589,
 590,
 591,
 592,
 593,
 594,
 595,
 596,
 597,
 598,
 599,
 600,
 601,
 602,
 603,
 604,
 605,
 606,
 607,
 608,
 609,
 610,
 611,
 612,
 613,
 614,
 615,
 616,
 617,
 618,
 619,
 620,
 621,
 622,
 623,
 624,
 625,
 626,
 627,
 628,
 629,
 630,
 631,
 632,
 633,
 634,
 635,
 636,
 637,
 638,
 639,
 640,
 641,
 642,
 643,
 644,
 645,
 646,
 647,
 648,
 649,
 650,
 651,
 652,
 653,
 654,
 655,
 656,
 657,
 658,
 659,
 660,
 661,
 662,
 663,
 664,
 665,
 666,
 667,
 668,
 669,
 670,
 671,
 672,
 673,
 674,
 675,
 676,
 677,
 678,
 679,
 680,
 681,
 682,
 683,
 684,
 685,
 686,
 687,
 688,
 689,
 690,
 691,
 692,
 693,
 694,
 695,
 696,
 697,
 698,
 699,
 700,
 701,
 702,
 703,
 704,
 705,
 706,
 707,
 708,
 709,
 710,
 711,
 712,
 713,
 714,
 715,
 716,
 717,
 718,
 719,
 720,
 721,
 722,
 723,
 724,
 725,
 726,
 727,
 728,
 729,
 730,
 731,
 732,
 733,
 734,
 735,
 736,
 737,
 738,
 739,
 740,
 741,
 742,
 743,
 744,
 745,
 746,
 747,
 748,
 749,
 750,
 751,
 752,
 753,
 754,
 755,
 756,
 757,
 758,
 759,
 760,
 761,
 762,
 763,
 764,
 765,
 766,
 767,
 768,
 769,
 770,
 771,
 772,
 773,
 774,
 775,
 776,
 777,
 778,
 779,
 780,
 781,
 782,
 783,
 784,
 785,
 786,
 787,
 788,
 789,
 790,
 791,
 792,
 793,
 794,
 795,
 796,
 797,
 798,
 799,
 800,
 801,
 802,
 803,
 804,
 805,
 806,
 807,
 808,
 809,
 810,
 811,
 812,
 813,
 814,
 815,
 816,
 817,
 818,
 819,
 820,
 821,
 822,
 823,
 824,
 825,
 826,
 827,
 828,
 829,
 830,
 831,
 832,
 833,
 834,
 835,
 836,
 837,
 838,
 839,
 840,
 841,
 842,
 843,
 844,
 845,
 846,
 847,
 848,
 849,
 850,
 851,
 852,
 853,
 854,
 855,
 856,
 857,
 858,
 859,
 860,
 861,
 862,
 863,
 864,
 865,
 866,
 867,
 868,
 869,
 870,
 871,
 872,
 873,
 874,
 875,
 876,
 877,
 878,
 879,
 880,
 881,
 882,
 883,
 884,
 885,
 886,
 887,
 888,
 889,
 890,
 891,
 892,
 893,
 894,
 895,
 896,
 897,
 898,
 899,
 900,
 901,
 902,
 903,
 904,
 905,
 906,
 907,
 908,
 909,
 910,
 911,
 912,
 913,
 914,
 915,
 916,
 917,
 918,
 919,
 920,
 921,
 922,
 923,
 924,
 925,
 926,
 927,
 928,
 929,
 930,
 931,
 932,
 933,
 934,
 935,
 936,
 937,
 938,
 939,
 940,
 941,
 942,
 943,
 944,
 945,
 946,
 947,
 948,
 949,
 950,
 951,
 952,
 953,
 954,
 955,
 956,
 957,
 958,
 959,
 960,
 961,
 962,
 963,
 964,
 965,
 966,
 967,
 968,
 969,
 970,
 971,
 972,
 973,
 974,
 975,
 976,
 977,
 978,
 979,
 980,
 981,
 982,
 983,
 984,
 985,
 986,
 987,
 988,
 989,
 990,
 991,
 992,
 993,
 994,
 995,
 996,
 997,
 998,
 999]

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(1, 5000, 200)]

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

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

for i in range(10):  # to see if I can break a range
    print(i)
    if i==5:
        i=9

0
1
2
3
4
5
6
7
8
9

def bubble_sortImproved(lst):
    # outer loop   "to"  range  len(list)-1   downto  1
    #   inner loop does the bubble from item 0 to item "to"
    #       if the two items I am looking at are out of order, swap
#    for to in range(len(lst)-1, 0, -1):
    to=len(lst)-1 
    while to>0: 
        for i in range(0, to):   # final index is "to"-1
            if (lst[i]>lst[i+1]):
                lst[i],lst[i+1]=lst[i+1],lst[i]
                lastSwap=i+1
        to-=1
        if lastSwap<to:
            to=lastSwap
# this version has special case 
# already sorted is linear growth  O(n)
# but everything else is O(n^2)

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

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

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

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

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

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