How do I pass the random list generated in the get_me_random_list() function in my main() function?

Question

I am trying to generate 100 separate lists of 500 positive integers and run each algorithm on the 100 lists. This is meant to represent a worst-case analysis, so I am searching for an element I know will not be in the lists (-1).

The main() function is meant to be used to print the results i.e. "Sequential Search took xx seconds to run, on average."

I have tried passing the get_me_random_list function as a parameter for the algorithm functions, but that was unsuccessful.

def main():
    sequential_search(a_list, -1)
    ordered_sequential_search(a_list, -1)
    binary_search_iterative(a_list, -1)
    binary_search_recursive(a_list, 1)

def get_me_random_list():
    a_list = []
    for i in range(100):
        a_list.append(random.sample(range(1,500), 100))
    return a_list

def sequential_search(a_list,item):
    start = time.time()
    pos = 0
    found = False

    while pos < len(a_list) and not found:
        if a_list[pos] == item:
            found = True
        else:
            pos = pos + 1
    end = time.time()
    return found
    print(f"Total runtime of the sequential search is {end - begin}")


def ordered_sequential_search(a_list,item):
    start = time.time()
    pos = 0
    found = False
    stop = False

    while pos < len(a_list) and not found and not stop:
        if a_list[pos] == item:
            found = True
        else:
            if a_list[pos] > item:
                stop = True
            else:
                pos = pos + 1
    end = time.time()
    return found
    print(f"Total runtime of the ordered sequential search is {end - begin}")


def binary_search_iterative(a_list,item):
    start = time.time()
    first = 0
    last = len(a_list) - 1
    found = False

    while first <= last and not found:
        midpoint = (first + last) // 2
        if a_list[midpoint] == item:
            found = True
        else:
            if item < a_list[midpoint]:
                last = midpoint - 1
            else:
                first = midpoint + 1
    end = time.time()
    return found
    print(f"Total runtime of the binary search iterative is {end - begin}")


def binary_search_recursive(a_list,item):
    start = time.time()
    if len(a_list) == 0:
        return False
    else:
        midpoint = len(a_list) // 2
    if a_list[midpoint] == item:
        return True
    else:
        if item < a_list[midpoint]:
            return binary_search(a_list[:midpoint], item)
        else:
            return binary_search(a_list[midpoint + 1:], item)
    end = time.time()
    return found
    print(f"Total runtime of the binary search recursive is {end - begin}")

if __name__ == "__main__":
    main()

ddejohn · Answer 1 · 2022-02-23T00:21:46.573

I'll suggest two solutions.

Solution 1

Remove the main() function altogether, then in the if __name__ == "__main__" block, do:

if __name__ == "__main__":
    a_list = get_me_random_list()
    sequential_search(a_list, -1)
    ordered_sequential_search(a_list, -1)
    binary_search_iterative(a_list, -1)
    binary_search_recursive(a_list, 1)

Solution 2

Alternatively, make it so that main() takes a_list as a parameter, then generate a_list in the if __name__ == "__main__" block and pass it to main():

def main(a_list):
   ...


if __name__ == "__main__":
    a_list = get_me_random_list()
    main(a_list)

Notes

Note that there are other issues with your code that my answer does not attempt to fix. For instance, all your functions follow this pattern:

    # rest of function body
    end = time.time()
    return found
    print(f"Total runtime of the binary search recursive is {end - begin}")

return tells Python to immediately return the value; the print() statement will never run
All your start times are called start, but you use begin in all your time differences ({end - begin})
Your binary_search_recursive calls an undefined function, binary_search
You attempt illegal operations between lists and integers in every function because a_list is a multi-dimensional list (a list of lists of ints, specifically)

Was it intentional to make a_list a 2D array?

Suggestions

I recommend learning about and using a decorator function for timing your functions. If you're interested in more stringent, robust profiling however, time.time() doesn't really do a great job. It's okay for a decent approximation of your performance. I suggest reading this thread, and looking at the timeit module, which is part of the standard library.

How do I pass the random list generated in the get_me_random_list() function in my main() function?

1 Answers1

Solution 1

Solution 2

Notes

Suggestions