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