Parallel Computing, Hashmaps
Example 1:
A particular computer has two identical processors which can run in parallel. Each process must be executed on a single processor and each processor can only run one process at a time.
The table below lists the amount of time it takes to execute each of the processes on a single computer. None of the processes are dependent on any of the others.
What is the minimum amount of time (approximate) to execute all three processes when the two processors are run in parallel?
| Process | Execution Time on Either Processor |
|---|---|
| X | 50 seconds |
| Y | 10 seconds |
| Z | 30 seconds |
Answer: 50 seconds.
Example 2:
A computer has two duplicate processors that are able to run in parallel. The table below shows the amount of time it takes each processor to execute each of two processes. Neither of the processes is dependent on the other.
| Process | Execution Time on Either |
|---|---|
| A | 25 seconds |
| B | 45 seconds |
What is the difference in execution time between running the two processes in parallel in place of running one after the other on a single processor?
Sequential = 70 seconds
Parallel = 25 seconds
Difference = 45 seconds
# mapping to square each number in a list of numbers #
import multiprocessing
def square(num):
return num ** 2
if __name__ == '__main__':
nums = [1, 2, 3, 4, 5]
pool = multiprocessing.Pool(processes=4)
squares = [result for result in pool.map(square, nums)]
print(f"Original List: {nums}")
print(f"Squares: {squares}")
xeem = {
"artist_name": "Lil' Xeem",
"real_name": "Azeem Khan",
"explicit": True,
"genres": ["Hip-Hop", "R&B"],
"platforms": ["Spotify", "Soundcloud", "Apple Music", "Amazon Music", "Deezer", "YouTube Music"],
"recent_tracks": {
1: "Lil Bish",
2: "romantic homicide",
3: "Go",
4: "Solo",
5: "Runnin'",
6: "Matte Black",
7: "Real",
8: "tbh",
9: "Don't Know Why",
10: "Not Gang"
}
}
stingr = {
"artist_name": "Stingr",
"real_name": "Paaras Mandar Vikas Dnyaneshwar Purohit",
"explicit": False,
"genres": ["Hip-Hop", "Rap", "R&B", "Pop", "Rock"],
"recent_tracks" : {
1: "Chillin' & Groovin'",
2: "Lenses",
3: "Hey, It's Me From High School",
4: "Run Away",
5: "Loco Tres",
6: "Thought So",
7: "ROCKIN DESIGNER",
8: "My Problems",
9: "Butterfly Doors",
10: "Real Wildin'",
}
}
print(xeem.get('recent_tracks'))
print(stingr['recent_tracks'])
print(xeem.get('recent_tracks')[10])
print(stingr['recent_tracks'][10])
stingr["features"] = set(['GTRARI', 'Beware', 'BOB Ramaz', 'ABH', 'Evvan', 'Beware'])
# In the above code, the feature "Beware" is repeated twice. The set() method, however
# removes the duplicate
xeem["features"] = set(["Copaine", "djphatjive", "Foley", "Foley", "Copaine"])
# In the above code, the features "Copaine" and "Foley" are repeated twice. The set() method,
# however, removes the duplicate
print(stingr["features"])
print(xeem["features"])
for k,v in stingr.items():
print(str(k) + ": " + str(v))
for k,v in xeem.items():
print(str(k) + ": " + str(v))
def search():
artist = ""
which_artist = input("Which artist would you like to know about, Stingr or Lil Xeem?")
if which_artist.lower() == "stingr":
artist = stingr
elif which_artist.lower() == "lil xeem":
artist = xeem
else:
print("Invalid Search")
search = input("What would you like to know about " + str(which_artist).capitalize() + "?")
if artist.get(search.lower()) == None:
print("Invalid Search")
else:
print(artist.get(search.lower()))
search()
Extra: APCSA Skits in This Week's Hacks
I had the opportunity this friday to see the Algo-Rhythmic performances by the APCSA classes. In these algo-rhythms, APCSA students used fictional scenarios to depict different sorting algorithms.
Two of these skits stuck with me:
- Attendance. A teacher's students are all out of order, and he needs to use an algorithm to sort the students by ID number. The teacher uses the Bogosort algorithm, which is one of the most inefficient sorting algorithms, to shuffle the students' order until they are sorted from least to greatest ID number.
- Turtles. A zookeeper has to do about the same thing, but this time, with the ID of turtles in a zoo. The zookeeper uses selection sort to find the least ID number, set that as the minimum, sort accordingly, find the second least ID number, and repeat until all the numbers are sorted.
As I watched the two performances, I thought about how they relate to what we learned in this week's hacks. Below is an example of how Bogosort can be combined with what we learned in parallel programming and hashing/collisions (Note that as Bogosort is very inefficient, with the time complexity being O(n!), I had to interrupt the program multiple times as it took too long):
import random
import multiprocessing as mp
def is_sorted(lst):
"""
Checks if the given list is sorted in non-descending order.
"""
return all(lst[i] <= lst[i+1] for i in range(len(lst)-1))
def bogosort(lst, num_procs):
"""
Sorts the given list using the Bogosort algorithm in parallel.
num_procs: The number of processes to use for sorting.
"""
pool = mp.Pool(processes=num_procs)
while not is_sorted(lst):
chunks = [lst[i:i+len(lst)//num_procs] for i in range(0, len(lst), len(lst)//num_procs)]
results = pool.map_async(sort_chunk, chunks)
lst = [item for sublist in results.get() for item in sublist]
pool.close()
pool.join()
return lst
def sort_chunk(lst):
"""
Sorts a chunk of the given list using the Bogosort algorithm.
"""
while not is_sorted(lst):
random.shuffle(lst)
return lst
if __name__ == '__main__':
lst = [random.randint(1, 100) for _ in range(3)]
print('Unsorted list:', lst)
sorted_lst = bogosort(lst, 2)
print('Sorted list:', sorted_lst)
Below is an example of how selection sort can be combined with what we learned about parallel programming and hashing/collisions:
import random
def selection_sort_dict(dictionary):
"""
Sorts the values in the given dictionary using the selection sort algorithm.
"""
keys = list(dictionary.keys())
for i in range(len(keys)):
min_val = dictionary[keys[i]]
min_key = keys[i]
for j in range(i+1, len(keys)):
if dictionary[keys[j]] < min_val:
min_val = dictionary[keys[j]]
min_key = keys[j]
if min_key != keys[i]:
dictionary[keys[i]], dictionary[min_key] = dictionary[min_key], dictionary[keys[i]]
return dictionary
if __name__ == '__main__':
# Example usage:
my_dict = {key: random.randint(1, 100) for key in range(10)}
print('Unsorted dictionary:', my_dict)
sorted_dict = selection_sort_dict(my_dict)
print('Sorted dictionary:', sorted_dict)