Filtering a list of tuples

Question

I have a list of tuples which may vary in size quite significantly. Typical number of tuples in the list would be somewhere around 100.000. I am trying to perform a down-selection on these tuples to end up with a more workable amount of them.

Each tuple contains (among other insignificant for this example data) an integer and 3 floats. These are of interest to me (shown bold below, positions 0, 2, 3, 4).

Example:

(100213, 'foo',-23.412, -277.11, 12.567, 12.24, 23.25, 150.14, 'bar', 'foobar')

And the criterion to implement is the following in pseudocode:

Assume tuples i and j:

if i[2] < j[2] and i[3] < j[3] and abs(i[4]) > abs(j[2]) then j leaves the list.

I wrote a couple algorithms for the task, timed them and improved them and finally I arrived here:

def clean3(lst):
    lst = sorted(lst, key=lambda x: abs(x[4]), reverse=True)  # the abs comparison is taken care off.
    remove = set()  # for quicker membership checks
    for i, forces_i in enumerate(lst[:-1]):
        if forces_i not in remove:  # the current entry might have already been removed
            for forces_j in lst[i+1:]:  # forward check only - progressive gains
                if forces_j not in remove: # the current entry might have already been removed
                    if all(forces_i[x] < forces_j[x] for x in range(2, 4)):  # check with `all` now possible
                        remove.add(forces_j)
    return list(set(lst) - remove)

To my eyes, this looks as streamlined as it could be, but:

1. Can it be further improved, and if yes, how?
2. Would an entirely different approach be better here?

Answer 1

The pattern for i in range(n): for j in range(i+1, n): ... is better handled using itertools.combinations:

from itertools import combinations


def clean3(lst):
    lst = sorted(lst, key=lambda x: abs(x[4]), reverse=True) # the abs comparison is taken care off.
    remove = set() # for quicker membership checks
    for forces_i, forces_j in combinations(lst, 2):
        if forces_j not in remove: # the current entry might have already been removed
            if all(forces_i[x] < forces_j[x] for x in range(2, 4)):
                remove.add(forces_j)
    return list(set(lst) - remove)

I also removed the test for forces_i in removed since I feel you could have cases where it would fail to remove some forces_j. But if I'm wrong it's very easy to put back on the same line than the test for forces_j.