Today's homework is to do some performance analysis of Python's hash tables, which are a key data structure used by the dict class. We're also going to do some miscellaneous tasks to help practice writing Python.
1. Use the time.perf_counter_ns() method to measure how many nanoseconds it takes for time.sleep() to run for the following durations: 10 milliseconds, 100 milliseconds, 1 second. Repeat for 100 times for each of those durations. The variation in timing is called jitter. Can you find any pattern to how the jitter varies for each of the different sleep durations? Binning the results and creating a histogram may help.
import time
durations = [0.01, 0.1, 1.0]
num_repetitions = 100
# Jitter for 10 milliseconds, 100 milliseconds, and 1 second
jitter_10ms = []
jitter_100ms = []
jitter_1s = []
def measure_jitter(duration):
start_time = time.perf_counter_ns()
time.sleep(duration)
end_time = time.perf_counter_ns()
return end_time - start_time
# Measure jitter for each duration and repeat for num_repetitions times
for duration in durations:
for _ in range(num_repetitions):
jitter = measure_jitter(duration)
if duration == 0.01:
jitter_10ms.append(jitter)
elif duration == 0.1:
jitter_100ms.append(jitter)
elif duration == 1.0:
jitter_1s.append(jitter)
# Create histograms for each duration's jitter
import matplotlib.pyplot as plt
plt.hist(jitter_10ms, bins=10, color='r', alpha=0.5, label='10ms')
plt.hist(jitter_100ms, bins=10, color='g', alpha=0.5, label='100ms')
plt.hist(jitter_1s, bins=10, color='b', alpha=0.5, label='1s')
plt.xlabel('Jitter (ns)')
plt.ylabel('Frequency')
plt.title('Jitter of time.sleep() for Different Durations')
plt.legend()
plt.show()
From the histogram shown above, we can say that jitter is expected to be more fluctuated for longer sleep duration, and the relationship between the sleep duration and jitter can fit a polynomial curve of degree 2 as being shown below. A possible reason for this may be the overhead of the function call and operating system scheduling.
import numpy as np
# Durations to measure in seconds
durations = [0.01, 0.1, 1.0]
# Number of repetitions
num_repetitions = 100
# Lists to store jitter and duration for each measurement
jitter = []
duration = []
# Function to measure jitter
def measure_jitter(duration):
start_time = time.perf_counter_ns()
time.sleep(duration)
end_time = time.perf_counter_ns()
return end_time - start_time
# Measure jitter for each duration and repeat for num_repetitions times
for dur in durations:
for _ in range(num_repetitions):
jitter.append(measure_jitter(dur))
duration.append(dur)
# Convert lists to NumPy arrays
jitter = np.array(jitter)
duration = np.array(duration)
# Fit a polynomial curve of degree 2
coeffs = np.polyfit(duration, jitter, 2)
poly_func = np.poly1d(coeffs)
# Generate data points for the curve
duration_range = np.linspace(min(duration), max(duration), 100)
jitter_fit = poly_func(duration_range)
# Plot the measured data points and the polynomial curve
plt.scatter(duration, jitter, color='b', alpha=0.5, label='Measured Data')
plt.plot(duration_range, jitter_fit, color='r', label='Polynomial Fit (Degree 2)')
plt.xlabel('Sleep Duration (s)')
plt.ylabel('Jitter (ns)')
plt.title('Polynomial Relationship between Sleep Duration and Jitter')
plt.legend()
plt.show()
2. Create a dict with 1 million integer keys, each with 64 bytes of random values.
import random
import secrets
my_dict = {}
for i in range(1000000):
# Generate a random 64-byte value as bytes
random_value = secrets.token_bytes(64)
# Convert the bytes value to hexadecimal representation
hex_value = random_value.hex()
# Add the key-value pair to the dictionary
my_dict[i] = hex_value
print("Dictionary created with 1 million integer keys.")
3. Now that we know how to precisely time how long it takes for Python to do something, measure how long it takes to look up 1,000, 10,000, and 100,000 random integer keys, and repeat each experiment 100 times. Does the amount of time per key lookup change?
def measure_time(num_lookups):
total_time = 0
for i in range(100):
keys = random.sample(range(1000000), num_lookups)
start_time = time.perf_counter()
for key in keys:
value = my_dict[key]
end_time = time.perf_counter()
total_time += end_time - start_time
return total_time / 100
# Measure time taken for 1,000 key lookups
time_1000 = measure_time(1000)
print(f"Average time taken for 1,000 key lookups: {time_1000:.9f} seconds")
# Measure time taken for 10,000 key lookups
time_10000 = measure_time(10000)
print(f"Average time taken for 10,000 key lookups: {time_10000:.9f} seconds")
# Measure time taken for 100,000 key lookups
time_100000 = measure_time(100000)
print(f"Average time taken for 100,000 key lookups: {time_100000:.9f} seconds")
Average time taken for 1,000 key lookups: 0.000496019 seconds Average time taken for 10,000 key lookups: 0.004768387 seconds Average time taken for 100,000 key lookups: 0.055429382 seconds
Obviously, the average time becomes longer when looking up more keys in a dic. The reason for this fact should relate to the nature of dictionary data structure in Python as it is implemented as a hash table, which is an unordered collection of key and value pairs. As more keys need to be looked up, the hash collisions may increase that cause the average time to become longer.
4. The ABC module can be used to create so-called virtual base classes, similar to the Simulator.py file from day 4. Look around you, and find two related objects. Create a virtual base class by inheriting from the ABC module and using the @abstractmethod and @property decorators to define the shared methods and properties of the class, and non-abstract methods and properties which are the same for the two objects.
Just use the pets "Cat" and "Dog" as an example, and the class FunnyPets is defined to inherit from ABC.
from abc import ABC, abstractmethod
class FunnyPets(ABC):
@abstractmethod
def make_sound(self):
pass
@abstractmethod
def play(self):
pass
@property
def color(self):
return "Multicolor"
@property
def size(self):
return "Small"
def common_snack(self):
return "This is a common snack for Cat and Dog objects"
5. Create concrete classes which inherit from your virtual base class from the previous task, and define the non-abstract methods and properties which are different for each of the two objects. I'm deliberately omitting an example here to incentivize you to read the documentation on the ABC module: https://docs.python.org/3/library/abc.html#module-abc
class Cat(FunnyPets):
def make_sound(self):
return "Meow!"
def play(self):
return "Cat is playing with a little mouse toy."
@property
def color(self):
return "Tabby"
@property
def size(self):
return "Small"
def unique_snack(self):
return "This is a dehydrated fish for Cat object"
class Dog(FunnyPets):
def make_sound(self):
return "Woof!"
def play(self):
return "Dog is playing fetch with a frisbee."
@property
def color(self):
return "Gray & white"
@property
def size(self):
return "Small, but larger than cat"
def unique_snack(self):
return "This is a bone for Dog object"
6. What happens when you try to call an abstract method, or access an abstract property in the base class?
It reports a TypeError saying "can't instantiate abstract class FunnyPets with abstract methods". To solve this issue, we need to create instances of Cat and Dog first and then call the overridden methods. For example, Alice is the cat living in my apartment and Bibi is my friend's dog, then I can get their sounds like:
Alice = Cat()
Bibi = Dog()
print(cat.make_sound()) # Output: "Meow"
print(dog.make_sound()) # Output: "Woof"