I wanted to know if it would be more efficient, when searching for both a minimum and a maximum value in a list, to perform both tests in a single loop rather than making calls to both the min function and the the max function. The basis for this question was that if the min and max functions ran in O(n) time then, all else being equal, combining them into a single step should cut processing time in half. Apparently, all else is not equal; running both the min and max functions is faster than looping over all of the values once. The detailed results are listed below.

In addition to manually iterating over the the list of items I also used xrange() to access the list items by position, which was even slower. Changing the for loop to a while loop with an external variable was a little over 50% slower than the for loops. I also attempted to sort the list and pick of the first and last elements. That yielded the worst results.

The takeaway seems to be that attempting to manually write algorithms in Python is likely to yield worse results than just using the built-in functions.

List Length min/max while loop min/max xrange loop min/max for loop built-in min then max built-in sort
99 0.1798 0.1206 0.0689 0.0568 0.1420
999 1.7151 1.0623 0.6015 0.4339 2.2071
9999 16.6212 10.0163 5.8651 4.2295 27.6747
import random
import time
from datetime import date


class TestMinMax(object):
    LIST_LENGTH = 8
    TEST_ITTERATIONS = 999999

    def __init__(self):
        self.hours_list = []
        for x in xrange(0, self.LIST_LENGTH):
            self.hours_list.append(self.random_date())

    def random_date(self):
        TEST_YEAR = 2016
        start_date = date(day=1, month=1, year=TEST_YEAR).toordinal()
        end_date = date(day=31, month=12, year=TEST_YEAR).toordinal()
        random_day = date.fromordinal(random.randint(start_date, end_date))
        return random_day

    def get_date_min_and_max(self, hours_list):
        date_min = date.max
        date_max = date.min
        for hours in hours_list:
            if hours < date_min:
                date_min = hours
            if hours > date_max:
                date_max = hours

        if date_min == date.max or date_max == date.min:
            return (None, None)

        return (date_min, date_max)

    def get_date_min_and_max_xrange(self, hours_list):
        date_min = date.max
        date_max = date.min
        for x in xrange(1, len(hours_list)):
            if hours_list[x] < date_min:
                date_min = hours_list[x]
            if hours_list[x] > date_max:
                date_max = hours_list[x]

        if date_min == date.max or date_max == date.min:
            return (None, None)

        return (date_min, date_max)

    def get_date_min_and_max_builtin(self, hours_list):
        if not hours_list:
            return (None, None)

        date_min = min(hours_list)
        date_max = max(hours_list)

        return (date_min, date_max)

    def get_date_min_and_max_sort(self, hours_list):
        if not hours_list:
            return (None, None)

        hours_list_sorted = sorted(hours_list)
        date_min = hours_list_sorted[0]
        date_max = hours_list_sorted[-1]

        return (date_min, date_max)

    def n_min_max(self):
        for x in xrange(1, self.TEST_ITTERATIONS):
            self.get_date_min_and_max(self.hours_list)

    def n_min_max_xrange(self):
        for x in xrange(1, self.TEST_ITTERATIONS):
            self.get_date_min_and_max_xrange(self.hours_list)

    def n_min_max_builtin(self):
        for x in xrange(1, self.TEST_ITTERATIONS):
            self.get_date_min_and_max_builtin(self.hours_list)

    def n_min_max_sort(self):
        for x in xrange(1, self.TEST_ITTERATIONS):
            self.get_date_min_and_max_sort(self.hours_list)

    def test_min_max(self):
        start = time.time()
        self.n_min_max()
        end = time.time()
        time_elapsed = end - start
        print("min/max loop:          %s" % time_elapsed)

    def test_min_max_xrange(self):
        start = time.time()
        self.n_min_max_xrange()
        end = time.time()
        time_elapsed = end - start
        print("min/max xrange loop:   %s" % time_elapsed)

    def test_min_max_builtin(self):
        start = time.time()
        self.n_min_max_builtin()
        end = time.time()
        time_elapsed = end - start
        print("built-in min then max: %s" % time_elapsed)

    def test_min_max_sort(self):
        start = time.time()
        self.n_min_max_sort()
        end = time.time()
        time_elapsed = end - start
        print("built-in sort:         %s" % time_elapsed)

    def test(self):
        self.test_min_max()
        self.test_min_max_xrange()
        self.test_min_max_builtin()
        self.test_min_max_sort()

if __name__ == '__main__':
    tester = TestMinMax()
    tester.test()

Tags: Python minimum maximum

Published: 2016-05-03