Instantly share code, notes, and snippets.

Embed
What would you like to do?
"""
Implements linear search and probabilistic search to analyse time complexity.
"""
import random
from matplotlib import pyplot as plt
def linear_search(value, list):
"""
Searches the index of the value in the list.
Returns the number of iterations.
"""
for index, val in enumerate(list):
if value == val:
return index
return index
def prob_search(value, l):
"""
Searches a value in a list using a probabilistic search.
Returns the number of iterations.
"""
indexes = list(range(len(l)))
random.shuffle(indexes)
for iteration, index in enumerate(indexes):
if l[index] == value:
return iteration
return iteration
def compare_methods(size, n=100):
"""
Returns the average number of iterations for each method to find
a random value in a random list.
"""
values_linear = []
values_prob = []
for _ in range(n):
# Random list
list = random.sample(range(size * 2), size)
# Random value from list
value = random.choice(list)
values_linear.append(linear_search(value, list))
values_prob.append(prob_search(value, list))
return (
sum(values_linear) / len(values_linear),
sum(values_prob) / len(values_prob)
)
def plot_time_complexity(a=10, b=100, step=10, n=100):
"""
Plots time complexity comparison of both search methods for lists with size
between 'a' and 'b'. Each value is an average of 'n' algorithm runs.
"""
values = [(size, compare_methods(size, n)) for size in range(a, b, step)]
steps = [value[0] for value in values]
values_linear = [value[1][0] for value in values]
values_prob = [value[1][1] for value in values]
plt.plot(steps, values_linear, 'b-', label='Linear search')
plt.plot(steps, values_prob, 'r-', label='Probabilistic search')
plt.title('Average number of iterations by list size')
plt.xlabel('List size')
plt.ylabel('Num. iterations')
plt.legend(loc='upper left')
plt.show()
if __name__ == '__main__':
plot_time_complexity(10, 1000, 10)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment