Fastest way to find all elements that maximize / minimize a function in a Python list

Question

Let's use a simple example: say I have a list of lists

ll = [[1, 2], [1, 3], [2, 3], [1, 2, 3], [2, 3, 4]]

and I want to find all longest lists, which means all lists that maximize the len function. Of course we can do

def func(x):
    return len(x)
maxlen = func(max(ll, key=lambda x: func(x)))
res = [l for l in ll if func(l) == maxlen]
print(res)

Output

[[1, 2, 3], [2, 3, 4]]

But I wonder if there are more efficient way to do this, especially when the function is very expensive or the list is very long. Any suggestions?

this is `O(n)`, can't get any better. There might be a little faster alternative, like you don't need the `func(x)`, just replace it straight up with `len(x)`, but other than that, I don't think so. — Mahrkeenerh, Oct 21 '21 at 12:58
You have to analyze each element in the list to be sure you don't skip a potential maximum_element, so as @Mahrkeenerh said it cannot be better than `O(n)` — Romibuzi, Oct 21 '21 at 13:01
Constants are ignored within O notation. You could make it a little faster if you build your output list while finding the max value, but that's pretty much the same — Mahrkeenerh, Oct 21 '21 at 13:02
@Mahrkeenerh But still, I computed the function for each elements twice. Is there anyway to only compute once? — Shaun Han, Oct 21 '21 at 13:06
as suggested in the answers below, yes - build your list while finding the max element, or cache the results, so even if it is expensive, the second pass will be a LOT faster. — Mahrkeenerh, Oct 21 '21 at 13:07
https://stackoverflow.com/questions/3989016/how-to-find-all-positions-of-the-maximum-value-in-a-list The first answer is wrong but there are a lot of other interesting answers there — Dani Mesejo, Oct 21 '21 at 13:10

score 3 · Accepted Answer · edited Oct 21 '21 at 14:39

3

From a computer science/algorithms perspective, this is a very classical "reduce" problem.

so, pseudocode. It's honestly very straightforward.

metric():= a mapping from elements to non-negative numbers

winner = []
maxmetric = 0

for element in ll:
  if metric(element) larger than maxmetric:
    winner = [ element ]
    maxmetric = metric(element)
  else if metric(element) equal to maxmetric:
    append element to winner

edited Oct 21 '21 at 14:39

Shaun Han

2,676
2
9
29

answered Oct 21 '21 at 13:01

Marcus Müller

34,677
4
53
94

2

An even more generalist solution is to set `maxmetric = metric(first element of ll)`, just in case the metric is able to return negative numbers. – jfaccioni Oct 21 '21 at 13:05
that depends on *how* expensive that metric is, but yeah, that's one way of doing it. (metrics in the math sense of the word: non-negative by definition) – Marcus Müller Oct 21 '21 at 13:05

Daweo · Answer 2 · 2021-10-21T13:12:09.773

when the function is very expensive

Note that you do compute func(x) for each element twice, first there

maxlen = func(max(ll, key=lambda x: func(x)))

then there

res = [l for l in ll if func(l) == maxlen]

so it would be beneficial to store what was already computed. functools.lru_cache allow that easily just replace

def func(x):
    return len(x)

using

import functools
@functools.lru_cache(maxsize=None)
def func(x):
    return len(x)

However, beware as due to way how data are stored argument(s) must be hashable, so in your example you would first need convert list e.g. to tuples i.e.

ll = [(1, 2), (1, 3), (2, 3), (1, 2, 3), (2, 3, 4)]

See descripiton in docs for further discussion

I'mahdi · Answer 3 · 2021-10-21T13:15:00.410

Is not OK use dictionary like below, (this is O(n))

ll = [[1, 2], [1, 3], [2, 3], [1, 2, 3], [2, 3, 4]]

from collections import defaultdict
dct = defaultdict(list)

for l in ll:
    dct[len(l)].append(l)
    
dct[max(dct)]

Output:

[[1, 2, 3], [2, 3, 4]]


>>> dct
defaultdict(list, {2: [[1, 2], [1, 3], [2, 3]], 3: [[1, 2, 3], [2, 3, 4]]})

OR use setdefault and without defaultdict like below:

ll = [[1, 2], [1, 3], [2, 3], [1, 2, 3], [2, 3, 4]]

dct = {}
for l in ll:
    dct.setdefault(len(l), []).append(l)

Output:

>>> dct
{2: [[1, 2], [1, 3], [2, 3]], 3: [[1, 2, 3], [2, 3, 4]]}

Fastest way to find all elements that maximize / minimize a function in a Python list

3 Answers3