1

If a have a list like:

l = [1,2,3,4,5]

and I want to have at the end

min = 1   
max = 5

WITHOUT min(l) and max(l).

2
  • 2
    is there a valid reason for not using min and max?? Commented Jun 5, 2013 at 10:58
  • 1
    can you tell why you don't want to use min(l)/max(l)? because if I were to answer your question here, I'd give you an algorithmic approach pretty close to what min() and max() already does. Commented Jun 5, 2013 at 11:01

8 Answers 8

8

If you are trying to avoid using two loops, hoping a single loop will be faster, you need to reconsider. Calling two O(N) functions still gives you a O(N) algorithm, all you do is double the constant per-iteration cost. A single Python loop with comparisons can't do better than O(N) either (unless your data is already sorted), and interpreting bytecode for each iteration has a sizeable constant cost too. Which approach has the higher constant cost can only be determined by timing your runs.

To do this in a single loop, iterate over the list and test each item against the minimum and maximum found so far. float('inf') and float('-inf') (infinity and negative infinity) are good starting points to simplify the logic:

minimum = float('inf')
maximum = float('-inf')
for item in l:
    if item < minimum:
        minimum = item
    if item > maximum:
        maximum = item

Alternatively, start with the first element and only loop over the rest. Turn the list into an iterable first, store the first element as the result-to-date, and then loop over the rest:

iterl = iter(l)
minimum = maximum = next(iterl)
for item in iterl:
    if item < minimum:
        minimum = item
    if item > maximum:
        maximum = item

Don't use sorting. Python's Tim Sort implementation is a O(N log N) algorithm, which can be expected to be slower than a straight-up O(N) approach.

Timing comparisons with a larger, random list:

>>> from random import shuffle
>>> l = list(range(1000))
>>> shuffle(l)
>>> from timeit import timeit
>>> def straight_min_max(l):
...     return min(l), max(l)
... 
>>> def sorted_min_max(l):
...     s = sorted(l)
...     return s[0], s[-1]
... 
>>> def looping(l):
...     l = iter(l)
...     min = max = next(l)
...     for i in l:
...         if i < min: min = i
...         if i > max: max = i
...     return min, max
... 
>>> timeit('f(l)', 'from __main__ import straight_min_max as f, l', number=10000)
0.5266690254211426
>>> timeit('f(l)', 'from __main__ import sorted_min_max as f, l', number=10000)
2.162343978881836
>>> timeit('f(l)', 'from __main__ import looping as f, l', number=10000)
1.1799919605255127

So even for lists of 1000 elements, the min() and max() functions are fastest. Sorting is slowest here. The sorting version can be faster if you allow for in-place sorting, but then you'd need to generate a new random list for each timed run as well.

Moving to a million items (and only 10 tests per timed run), we see:

>>> l = list(range(1000000))
>>> shuffle(l)
>>> timeit('f(l)', 'from __main__ import straight_min_max as f, l', number=10)
1.6176080703735352
>>> timeit('f(l)', 'from __main__ import sorted_min_max as f, l', number=10)
6.310506105422974
>>> timeit('f(l)', 'from __main__ import looping as f, l', number=10)
1.7502741813659668

Last but not least, using a million items and l.sort() instead of sorted():

>>> def sort_min_max(l):
...     l.sort()
...     return l[0], l[-1]
... 
>>> timeit('f(l[:])', 'from __main__ import straight_min_max as f, l', number=10)
1.8858389854431152
>>> timeit('f(l[:])', 'from __main__ import sort_min_max as f, l', number=10)
8.408858060836792
>>> timeit('f(l[:])', 'from __main__ import looping as f, l', number=10)
2.003532886505127

Note the l[:]; we give each test run a copy of the list.

Conclusion: even for large lists, you are better off using the min() and max() functions anyway, it is hard to beat the low per-iteration cost of a good C loop. But if you have to forgo those functions, the straight loop is the next better option.

Sign up to request clarification or add additional context in comments.

9 Comments

you should have better given him hints instead of giving him the answer, stackoverflow is not for doing assignments for the students! :-s (though your idea of using float's inf is pretty neat ;-) )
No, Stack Overflow is for answering questions. The OP never asked for hints and we are not here to police homework policies. If I were the professor, I would ask pointed questions about the code in my answer if it was posted as a homework answer to see if the student understands what it does exactly.
In this situation I'd use the iterable = iter(l); minimum = maximum = next(iterable) "pattern". It has the added advantage that it works with every sequence, while l[0] works only with indexed sequences.
@Bakuriu: +++ Out of caffeine error, redo from start +++. Of course, better idea, added.
ok, as you wish. I won't troll about this here, as it's already been done on meta, where it leads to my point. But as you give two different neat ways to implement it, if the OP did not learn something, future readers of the questions will, so forget about my comment. :-)
|
3

For finding max:

print reduce(lambda x,y: x if x>y else y, map(int,raw_input().split()))

For finding min:

print reduce(lambda x,y: x if x<y else y, map(int,raw_input().split()))

Comments

1

Loop through all the elements in the list with the for loop. Set the variable storing the max/min value to the fist element in the list to start with. Otherwise, you could end up with invalid values.

max_v=l[0]
for i in l:
    if i>max_v:
        max_v=i

min_v=l[0]
for i in l:
    if l<min_v:
        min_v=i

2 Comments

Why the double loop? You can avoid looping twice here.
True, but I think it's clearer from an educational viewpoint.
1

well, as this is an assignment, I won't give you any code, you have to figure it out yourself. But basically, you loop over the list, create two variables iMin and iMax for example, and for each value compare iMin and iMax to that value and assign a new variable iBuf to that one.

2 Comments

Those names seems too java-ish or whatever language uses camelCase + prepending the type, which I believe is totally ugly and misleading in this example(where the function will work with any type that supports comparison).
I'm talking in general algorithm, not specific python, and I used i for meaning index, not integers. I neither like camelCase in python, btw.
1

Homework questions with weird restrictions demand cheat answers

>>> l = [1,2,3,4,5]
>>> sorted(l)[::len(l)-1]
[1, 5]

Comments

0

The fastest approach I can think of would be to sort the original list and then pick the first and last elements. This avoids looping multiple times, but it does destroy the original structure of your list. This can be solved by simply copying the list and sorting only the copied list. I was curious if this was slower than just using max() and min() with this quick example script:

import time

l = [1,2,4,5,3]

print "Run 1"
t1 = time.time()
print "Min =", min(l)
print "Max =", max(l)
print "time =", time.time() - t1
print ""
print "l =", l
print ""


l = [1,2,4,5,3]
l1 = list(l)

print "Run 2"
t1 = time.time()
l1.sort()
print "Min =", l1[0]
print "Max =", l1[-1]
print "time =", time.time() - t1
print ""
print "l =", l
print "l1 =", l1
print ""


l = [1,2,4,5,3]

print "Run 3"
minimum = float('inf')
maximum = float('-inf')
for item in l:
    if item < minimum:
        minimum = item
    if item > maximum:
        maximum = item
print "Min =", minimum
print "Max =", maximum
print "time =", time.time() - t1
print ""
print "l =", l

Surprisingly, the second approach is faster by about 10ms on my computer. Not sure how effective this would be with very large list, but this approach is faster for at least the example list you provided.

I added @Martijn Pieters's simple loop algorithm to my timing script. (As timing would be the only important parameter worth exploring in this question.) My results are:

Run 1: 0.0199999809265s
Run 2: 0.00999999046326s
Run 3: 0.0299999713898s

Edit: Inclusion of timeit module for timing.

import timeit
from random import shuffle

l = range(10000)
shuffle(l)

def Run_1():
    #print "Min =", min(l)
    #print "Max =", max(l)
    return min(l), max(l)

def Run_2():
    l1 = list(l)
    l1.sort()
    #print "Min =", l1[0]
    #print "Max =", l1[-1]
    return l1[0], l1[-1]


def Run_3():
    minimum = float('inf')
    maximum = float('-inf')
    for item in l:
        if item < minimum:
            minimum = item
        if item > maximum:
            maximum = item
    #print "Min =", minimum
    #print "Max =", maximum
    return minimum, maximum


if __name__ == '__main__':
    num_runs = 10000
    print "Run 1"
    run1 = timeit.Timer(Run_1)
    time_run1 = run1.repeat(3, num_runs)
    print ""
    print "Run 2"
    run2 = timeit.Timer(Run_2)
    time_run2 = run2.repeat(3,num_runs)
    print ""
    print "Run 3"
    run3 = timeit.Timer(Run_3)
    time_run3 = run3.repeat(3,num_runs)
    print ""

    print "Run 1"
    for each_time in time_run1:
        print "time =", each_time
    print ""
    print "Run 2"
    for each_time in time_run2:
        print "time =", each_time
    print ""
    print "Run 3"
    for each_time in time_run3:
        print "time =", each_time
    print ""

My results are:

Run 1
time = 3.42100585452
time = 3.39309908229
time = 3.47903182233

Run 2
time = 26.5261287922
time = 26.2023346397
time = 26.7324208568

Run 3
time = 3.29800945144
time = 3.25067545773
time = 3.29783778232

sort algorithm is very slow for large arrays.

3 Comments

You need to use the timeit module to eliminate variance (CPU scheduling, swapping, etc.); it'll also pick the correct timer for your platform (most accurate option).
And a simple loop is O(n) complexity, sorting is O(n log n); it may be that constant costs of a python for loop is higher than the C code constant costs for sorting, which is why a short list may be faster when sorted, but for large lists, the loop will win, given a large enough list.
And a last data point: use a properly randomized list to test sort() against a straight loop or both a min() and max() call; the sorting algorithm (TimSort) is optimized for partially-sorted data; your input sample is mostly sorted (only 3 is out of place).
0
>>> L = [1,2,3,4,5]
>>> reduce(lambda x, y: x if x<y else y, L)
1
>>> reduce(lambda x, y: x if x>y else y, L)
5

Another way

>>> it = iter(L)
>>> mn = mx = next(it)
>>> for i in it:
...  if i<mn:mn=i
...  if i>mx:mx=i
... 
>>> mn
1
>>> mx
5

Comments

0

If you only require one looping through the list, you could use reduce a (not so) creative way. The helper function could have been reduced as a lambda but I don't do it for sake of readability:

>>> def f(solutions, item):
...     return (item if item < solutions[0] else solutions[0],
...             item if item > solutions[1] else solutions[1])
... 

>>> L = [i for i in range(5)]
>>> functools.reduce(f, L, (L[0],L[0]))
(0, 4)

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.