<jupyter_start><jupyter_text>List<jupyter_code>for i in range(1000):
    li = []
    for i in range(1000):
        li += [i]
for i in range(1000):
    li = []
    for i in range(1000):
        li.append(i)
for i in range(1000):
    li = [x for x in range(1000)]
for i in range(1000):
    li = list(range(1000))<jupyter_output><empty_output><jupyter_text>![image.png](attachment:image.png)<jupyter_code>import timeit
popzero = timeit.Timer("x.pop(0)",
                       "from __main__ import x")
popend = timeit.Timer("x.pop()",
                      "from __main__ import x")



x = list(range(2000000))
popzero.timeit(number=1000)
x = list(range(2000000))
popend.timeit(number=1000)
popzero = timeit.Timer("x.pop(0)",
                "from __main__ import x")
popend = timeit.Timer("x.pop()",
               "from __main__ import x")
lizero = []
liend = []

print("%15.6s  %15.5s" %("pop(0)", "pop()"))
# for i in range(1000000,100000001,1000000):
for i in range(10000,1000001,10000):
    x = list(range(i))
    pt = popend.timeit(number=1000)
    liend.append(pt)
    x = list(range(i))
    pz = popzero.timeit(number=1000)
    lizero.append(pz)
    print("%15.5f, %15.5f" %(pz,pt))
%matplotlib inline
import matplotlib.pyplot as plt
plt.plot(liend, '.')
plt.plot(lizero, '.')<jupyter_output><empty_output><jupyter_text>Dictionary ![image.png](attachment:image.png)<jupyter_code>import timeit
import random

for i in range(10000,1000001,20000):
    t = timeit.Timer("random.randrange(%d) in x"%i,
                     "from __main__ import random,x")
    x = list(range(i))
    lst_time = t.timeit(number=1000)
    x = {j:None for j in range(i)}
    d_time = t.timeit(number=1000)
    print("%d,%10.3f,%10.3f" % (i, lst_time, d_time))<jupyter_output>10000,     0.073,     0.001
30000,     0.201,     0.004
50000,     0.389,     0.001
70000,     0.480,     0.001
90000,     0.690,     0.001
110000,     0.749,     0.001
130000,     0.918,     0.001
150000,     1.073,     0.001
170000,     1.187,     0.001
190000,     1.298,     0.001
210000,     1.563,     0.001
230000,     1.643,     0.001
250000,     1.848,     0.001
270000,     2.028,     0.001
290000,     2.092,     0.001
310000,     2.208,     0.001
330000,     2.478,     0.001
350000,     2.573,     0.001
370000,     2.749,     0.001
390000,     2.898,     0.005
410000,     3.006,     0.001
430000,     3.175,     0.001
450000,     3.231,     0.001
470000,     3.420,     0.001
490000,     3.589,     0.001
510000,     3.730,     0.001
530000,     4.076,     0.001
550000,     4.198,     0.001
570000,     4.109,     0.001
590000,     4.357,     0.001
610000,     4.515,     0.001
630000,     4.437,     0.001
650000,     4.702,     0.001
670000,     4.692,     0.001
690000,     5.290, [...]<jupyter_text>Programming Exercises 1. Devise an experiment to verify that the list index operator is O(1)<jupyter_code>times = []
for i in range(1000):
    t = timeit.Timer("x[%d]" %i, 
                     "from __main__ import x")
    x = list(range(1000))
    time = t.timeit(number=10000)
    times.append(time)
plt.ylim((0, 0.001))
plt.plot(times, '.')<jupyter_output><empty_output><jupyter_text>2. Devise an experiment to verify that get item and set item are O(1) for dictionaries.<jupyter_code>get_times = []
set_times = []
for i in range(1000):
    t = timeit.Timer("d[%d]=%d" %(i, i), 
                     "from __main__ import d")
    t2 = timeit.Timer("d[%d]" %i, 
                     "from __main__ import d")
    d = {x[i]: 0 for i in range(1000)}
    get_time = t.timeit(number=1000)
    get_times.append(get_time)
    set_time = t2.timeit(number=1000)
    set_times.append(set_time)
plt.ylim((0, 0.0001))
plt.plot(get_times, '.')
plt.plot(set_times, '.')<jupyter_output><empty_output><jupyter_text>3. Devise an experiment that compares the performance of the del operator on lists and dictionaries.<jupyter_code>for i in range(10000):
    li = list(range(1000))
    del li[random.randrange(1000)]
for i in range(10000):
    d = {x:None for x in range(1000)}
    del d[random.randrange(1000)]<jupyter_output><empty_output><jupyter_text>4. Given a list of numbers in random order, write an algorithm that works in O(nlog(n)) to find the kth smallest number in the list.<jupyter_code>li = [random.randrange(1000) for i in range(10)]
print(li)
def find_smallest_k(li, k=0):
    return sorted(li)[k-1]
find_smallest_k(li, 3)
sorted(li)<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.1510920963746904, 'fraction_numerical': 0.16054942580499887, 'mean_word_length': 2.7548605240912933, 'pattern_counts': {'":': 0, '<': 28, '<?xml version=': 0, '>': 28, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 1, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '7', 'dir': 'jupyter-structured-clean-dedup', 'id': '418160', 'license': 'MIT', 'n_tokens_mistral': 2203, 'n_tokens_neox': 1748, 'n_words': 399, 'path': 'dsa/Analysis/List and Dictionary.ipynb', 'repo_name': 'callmexss/learn-python', 'size': '4441'}