Remove tuples from list that have duplicate key element

Question

I'm working on a reference implementing of a thinning mechanism comparable to that duplicati that removes backups depending on age. Going back in time, it establishes a minimum time difference between backups in growing time frames. This algorithm is controlled by a retention policy written in a mini language :,:,...,:

For example, "1D:3h,1W:1D,3M:1W" means

keep one backup every 3 hours for one day
... every day for one week
... every week for a 3 months
remove all that are older

Due to the incremental process,^[1] "programs" in this mini language can be "optimized":

"4W:2D,4W:1D" into "4W:2D" applying rule #1 x:a,x:b => x:a
"2W:2D,4W:2D" into "4W:2D" applying rule #2 a:x,b:x => max(a,b):x
"2W:2D,4W:1D" into "4W:2D" applying rule #3 a:x,b:y => max(a,b):x (if x >= y)

Rule #3 is about consecutive time frames (a < b) with a more restrictive limit (x) applied first. The limits are absolute distances, not frequencies, so (x > y) means that x is more restrictive than y.

Normalizing:

As illustrated in rule #1, only the first of two same-frame thinning levels are applied. I chose to take the one with the least restrictive limit. So a pre-processing to the thinning strategy can be done that reduces the sorted list of pairs (frame, limit) to those of each frame with the lowest limit (I replaced time deltas by numbers):

user_input = [(30, 3), (20, 4), (20, 5), (10, 1), (10, 2)]
expected_output = [(10, 1), (20, 4), (30, 3)]

This is what I have so far:

def normalized(thinning):
    thinning = sorted(thinning)
    deduped = []
    key = None
    for t in thinning:
        if t[0] != key:
            deduped.append(t)
            key = t[0]
    thinning = deduped
    return thinning

Is there an obvious way that would lead to a more compact (maybe less procedural) version?

^[1] At the beginning of the process all backups are collected in a to-do list. This list is sorted anti-chronological. Now the thinning strategy is applied time frame for time frame (smallest first): each time frame selects (and removes) timestamps from the to-do list.

user_9698684 · Answer

You can use itertools.groupby here:

from itertools import groupby
from operator import itemgetter

[next(v) for _,v in groupby(sorted(user_input), key=itemgetter(0))]
# [(10, 1), (20, 4), (30, 3)]

Remove tuples from list that have duplicate key element

Normalizing:

1 Answers