prob_search.py

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