TL;DR
Use collections.defaultdict
is the fastest alternative and arguably the most pythonic:
from collections import defaultdict
sample_list = [(5, 16, 2), (5, 10, 3), (5, 8, 1), (21, 24, 1)]
d = defaultdict(lambda: (0, 0, float("-inf")))
for e in sample_list:
first, _, last = e
if d[first][2] < last:
d[first] = e
res = [*d.values()]
print(res)
Output
[(5, 10, 3), (21, 24, 1)]
This is a single pass O(n)
which is not only asymptotically optimal but also performant in practice.
Detailed Explanation
Performance
To show that is performant one could design an experiment considering the two main variables of the problem, the number of unique keys (values in the firs position of the tuple) and the length of the input list and the following alternatives approaches:
def defaultdict_max_approach(lst):
d = defaultdict(lambda: (0, 0, float("-inf")))
for e in lst:
first, _, last = e
if d[first][2] < last:
d[first] = e
return [*d.values()]
def dict_max_approach(lst):
# https://stackoverflow.com/a/69025193/4001592
d = {}
for tpl in lst:
first, *_, last = tpl
if first not in d or last > d[first][-1]:
d[first] = tpl
return [*d.values()]
def groupby_max_approach(lst):
# https://stackoverflow.com/a/69025193/4001592
return [max(g, key=ig(-1)) for _, g in groupby(sorted(lst), key=ig(0))]
As shown in the plots below the approach using defaultdict is the most performant method for a varying number of unique keys (500, 1000, 5000, 10000) and also for collections up to 1000000 elements (note that the x axis in is in thousands).
The above experiments are in concordance with experiments done by others (1, 2). The code for reproducing the experiments can be found here.
Pythonic
Stating that is the most pythonic is subjective, but here are the main arguments in favor:
Is a well known Python idiom
Using a defaultdict for grouping a sequence key-value pairs, and aggregating afterwards, is a well known Python idiom.
Read the defaultdict examples in the Python documentation.
In the PyCon 2013 talk Transforming Code into Beautiful, Idiomatic Python by Raymond Hettinger also says that using defaultdict for such operations is the better way.
Is compliant with the Zen of Python
In the Zen of Python it can be read that
Flat is better than nested.
Sparse is better than dense.
Using a defaultdict is as flat as using a plain dict only a for-loop
and a simple if
statement. In the case of defaultdict the if condition is even simpler.
Both solutions are sparser than using itertools.groupby
, notice this approach also involves calling sorted
, itemgetter
and max
all inside a list comprehension.
Original Answer
You could use a collections.defaultdict
to group tuples that have the same first element and then take the maximum of each group based on the third:
from collections import defaultdict
sample_list = [(5,16,2),(5,10,3),(5,8,1),(21,24,1)]
d = defaultdict(list)
for e in sample_list:
d[e[0]].append(e)
res = [max(val, key=lambda x: x[2]) for val in d.values()]
print(res)
Output
[(5, 10, 3), (21, 24, 1)]
This approach is O(n)
.