Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Finding index of maximum element from list

Let v be a list of numbers

v = [3,5,2,4,8,6,1]

Why the following code to find the max element and its index gives an error ? ('int' object is not subscriptable)

reduce(lambda x,y: max(x[1],y[1]), enumerate(v))

P.S. I know there are other ways to do it, like the one below but I want to understand why the previous one does not work.

max(enumerate(v), key= lambda x: x[1])

Epilogue

Simeon pointed out that my code was really wrong cause lambda should have returned a tuple, not a number. Understanding this, my code could be easily fixed in the following way:

reduce(lambda x,y: x[1]<y[1] and y or x, enumerate(v))

which is, by the way, about 30% slower than

max(enumerate(v), key= lambda x: x[1])
like image 979
mmj Avatar asked Mar 31 '12 23:03

mmj


2 Answers

You're asking why the following does not work:

reduce(lambda x,y: max(x[1],y[1]), enumerate(v))

Let's see: your input is enumerate(v) which iterates over the following elements:

[(0, 3), (1, 5), (2, 2), (3, 4), (4, 8), (5, 6), (6, 1)]

You intend to reduce these elements with the function lambda x,y: max(x[1],y[1]). According to the docs, reduce takes a function as input that is applied to two element of the iterable. That means it reduces two elements and returns a value, which is one of the arguments of the next call to reduce.

That means x and y are tuples. For the above to work, the return value of the lambda function needs to be a tuple again because it's used again in the next reduction. But you are returning an integer, the result of max. That's why you're getting an error: "'int' object is not subscriptable" because x[1] does not work when x is an integer.

like image 198
Simeon Visser Avatar answered Oct 15 '22 05:10

Simeon Visser


How reduce works:

# type annotations:
# reduce(lambda X,X:X, [X,X..]) -> X

#        SAME  <-- result
#          ↗ ↖
#      SAME   SAME]
#        ↗ ↖
#    SAME   SAME,
#      ↗ ↖
# [SAME,  SAME,

>>> reduce(lambda a,b:[a,b], [1,2,3,4])
[[[1, 2], 3], 4]

This is how reduce with a seed (a.k.a. fold-left) works:

# type annotations:
# reduce(lambda REDU,ELEM:REDU, [ELEM,ELEM..], seed=REDU) -> REDU

#          REDU  <-- result
#            ↗ ↖
#        REDU   ELEM]
#          ↗ ↖
#      REDU   ELEM,
#        ↗ ↖
#    REDU   ELEM,
#      ↗ ↖
#  REDU  [ELEM,

>>> reduce(lambda a,b:[a,b], [1,2,3,4], 'seed')
[[[['seed', 1], 2], 3], 4]

You want:

maxValue,maxIndex = reduce(
    lambda p1,p2: max(p1,p2), 
    ((x,i) for i,x in enumerate(yourList))
)

The important thing to notice about reduce is the types. * When you use reduce(...) with a seed value (known as fold in other languages), the return type will be the seed's type. * When you use reduce normally, it ignores the seed element. This works great if all elements of your list are the same type (for example, you can reduce(operator.mul, [1,2,3]) or reduce(operator.add, [1,2,3]) just fine, because the reduced output type (int) is the same as the unreduced input type (two ints)). However the return type will be the same as the list's element's type.

If your elements are of different types, you need to use reduce(...) in fold-mode (i.e. with a seed with the right semantics). (The alternative is to special-case your lambda (very ugly).)

More explicitly, your intended return type is a tuple (the max element and its index, or the reverse). However your reduction function is of type tuple,tuple -> int. This cannot work because it violates the contract that reduce demands of your function.

like image 41
ninjagecko Avatar answered Oct 15 '22 06:10

ninjagecko